ランダウの記号

ランダウの記号（ランダウのきごう、英: Landau symbol）は、関数の極限における値の変化度合いに、おおよその評価を与えるための記法である。

ランダウの漸近記法 (asymptotic notation)、ランダウ記法 (Landau notation) あるいは主要な記号として O （オーもしくはオミクロン Ο。数字の0ではない）を用いることから（ランダウの）O-記法、ランダウのオミクロンなどともいう。

記号 O は「程度」の意味のオーダー（Order）から。

なおここでいうランダウはエドムント・ランダウの事であり、『理論物理学教程』の著者であるレフ・ランダウとは別人である。

ランダウの記号は数学や計算機科学をはじめとした様々な分野で用いられる。

概要

ランダウの記号

[math]f(x)=O(g(x))[/math]

は変数 x を極限に飛ばした時の関数 f の振る舞い（漸近的挙動）を、別の関数 g を目安にして記述する目的で用いられる。

たとえば f(x) = 3x² + 4x − 5 において x を ∞ に飛ばした時の f の挙動を考えると、x が十分大きいところでは第一項がその他の項に比べて極端に大きく、二項目以降はいわば「誤差」にすぎなくなる。したがって f の挙動は「定数×x ²」とほぼ等しくなる。ランダウの O-記法を用いる事でこの事実を

[math]f(x)=O(x^2)[/math]

と書き表す事ができる。

このように g は f よりも簡単な関数（上の例では x²）が用いられる事が多い。

また前述の関数 f は二次関数であるので、x が十分大きいところでは x³ よりはるかに小さい。ランダウの o-記法を用いる事でこの事実を

[math]f(x)=o(x^3)[/math]

と書き表す事ができる。

上では x を ∞ に飛ばした時の挙動を例にとって説明したが、何らかの定数に近づけたり −∞ に飛ばした時の挙動も同様にランダウ記号で書き表せる。x をどこに飛ばしたときの話であるのかは文脈から判断するよりないが、どこに飛ばしたかを明示する為に、

[math]f(x)=O(x^2) \; \text{ as } x\to\infty[/math]

のように書き表す事もできる。

f(x) = O(g(x)), f(x) = o(g(x)) (x → ∞) はそれぞれ

• [math]\lim_{x\to\infty} \left|\frac{f(x)}{g(x)}\right| [/math]　が存在する場合、その値が有限であること（一般の場合は後述）
• [math]\lim_{x\to\infty} \left| \frac{f(x)}{g(x)} \right| =0[/math]

を表す。（厳密にはε-δ論法で定義する。）

ランダウ記法は様々な分野で有益であり、たとえば指数関数を3次までテイラー展開したものは

[math]\mathrm{e}^x=1+x+\frac{x^2}{2!}+\frac{x^3}{3!}+O(x^4)\quad\text{ as } x\to 0[/math]

と書き表せる。

記号 O とo は通常、関数の収束や発散の漸近的な上界を記述する為に用いられる。同様に漸近的な下界を記述する為にΩ, ωという類似記法が用いられ、上下両方を記述する為にΘ という記法を用いる。

ただし、Ω、ω、Θは主に計算機科学で用いられる記法であり、数学では O と o をこれらの意味に流用する事が多い（どの意味で用いているのかは文脈から判断）。

厳密な定義

十分大きい全ての実数 x に対し定義されている実数値関数 f(x) と g(x) に対し、

[math]f(x)=O(g(x)) \quad\text{ as } x\to\infty[/math]

を

[math]{}^\exists x_0, {}^\exists M\gt 0 \quad \text{ s.t. }\quad x\gt x_0 \Rightarrow |f(x)|\lt M|g(x)|[/math]

と定義し、「f(x) が x → ∞ のとき オーダーO(g(x)) である」と呼ぶ。

また、a を実数とするとき、aの近傍付近で定義された実数値関数f(x) と g(x) に対し、

[math]f(x)=O(g(x))\qquad\hbox{as}\ x\to a[/math]

を

[math]{}^\exists \delta\gt 0, {}^\exists M\gt 0 \quad \text{ s.t. }\quad |x-a|\lt \delta \Rightarrow |f(x)|\lt M|g(x)|[/math]

で定義し、「f(x) が x → a のとき オーダーO(g(x)) である」と呼ぶ。

なお、a の十分近くで　g(x) が 0 の値をとらない場合、[math]f(x)=O(g(x))[/math]は

[math]\varlimsup_{x\to a} \left|\frac{f(x)}{g(x)}\right| \lt \infty[/math]

が満たされることと同値である（a が∞の場合も同様）。

記法の問題

上で定義された

[math]f(x)=O(g(x))[/math]

という記法は少し紛らわしい記法の濫用で、二つの関数が等しいという意味ではない。

この記法の濫用は、等号の両辺にO -記法が登場した際に問題となり、例えばx →∞のとき、

　[math]O(x) = O(x^2)[/math] 　であるが、　[math]O(x^2)\ne O(x)[/math]　である。

すなわち、両辺にO -記法が登場した場合には、直観的には十分大きなx で左辺/右辺が定数未満になる事を意味する。

こうした記法上の問題を回避する為に、

[math]f \in O(g)[/math]

ないし、

[math]f(x) \le O(g(x))[/math]

と書く流儀もある。前者の場合、「O(g)」 は g の定数倍によって押さえられる関数全体からなる集合であるとみなしていることになる。

より複雑な使い方としては、O( ) が等式の異なる場所に複数、もちろん両辺にわたって複数回現れるというものがある。例えば、以下は n → ∞ で正しい内容を記述している。

[math]\begin{align}&(n+1)^2 = n^2 + O(n),\\ &(n+O(n^{1/2}))(n + O(\log\,n))^2 = n^3 + O(n^{5/2}),\\ & n^{O(1)} = O(e^n).\end{align}[/math]

これらの式の意味は、次のように解釈する：

左辺の O() を満たす「任意の」関数に対して、右辺の O() を満たす「ある」関数を適切に選べば、それらの関数を代入した等式の両辺が等しいようにできる。

例えば三つの目の式は、

任意の関数 f(n) = O(1) に対し、g(n) = O(eⁿ) を満たすgを適切に選べば[math]n^{f(n)} \le g(n)[/math]が成立する

事を意味する。

二つの目の式のように左辺に複数のO()がある場合は、それらすべてに対して上述のルールを適応する。したがって二つの目の式は、

任意の関数[math]f_1(n) = O(n^{1/2})\, [/math]、[math]f_2(n) = O(O(\log\,n))\, [/math]に対し、[math]g(n) = O(n^{5/2})\, [/math]を満たすgを適切に選べば[math](n+f_1(n))(n + f_2(n))^2 \le n^3 + g(n)[/math]が成立する

事を意味する。

性質

積

[math]f_1(n) f_2(n) = O(g_1(n)g_2(n))[/math]

和

[math]O(f(n)) + O(g(n)) = O(\max \lbrace |f(n)|,|g(n)| \rbrace)[/math]

定数倍

[math]O(k g(n)) = O(g(n)),\quad k \ne 0[/math]

以下の性質も重要である。

• [math]o(f) + o(f) \subseteq o(f)[/math]
• [math]o(f) o(g) \subseteq o(fg)[/math]
• [math]o(o(f)) \subseteq o(f)[/math]
• [math]o(f) \subset O(f)[/math]

多変数の場合

漸近記法は多変数になっても有効である。たとえば

[math]f(n,m) = n^2 + m^3 + O(n+m) \quad(\mbox{as } n,m\to\infty)[/math]

という言及が示唆するのは、定数 C, N で

[math]\forall n, m\gt N: |g(n,m)| \le C(n+m)[/math]

を満たすものの存在である。ここで g(n, m) は

[math]f(n,m) = n^2 + m^3 + g(n,m)[/math]

で定められるものである。混乱を避けるためには、動かす変数は常に明示する必要がある。つまり

[math]f(n,m) = O(n^m) \quad (\mbox{as } n,m\to\infty)[/math]

という言明は、次の

[math]\forall m: f(n,m) = O(n^m) \quad (\mbox{as } n\to\infty)[/math]

とは明確に異なる言明である。

その他の漸近記法

O-記法と関連がある、Ω-記法、ω-記法、Θ-記法を導入する。

Ω-記法とω-記法はそれぞれ、O-記法とo-記法の定義で大小を反転させる事により得られる。Θ-記法Θ(g)は O(g) と Ω(g) を両方満たすことを意味する。

ただし、Ω-記法に関しては、この記法を初めて導入したハーディーとリトルウッドは今日のそれとは若干異なった意味に用いていたので、あわせてそれも記す。(以下の表の「HLの定義」の部分)。

今日の定義との違いの要点をかいつまんでいえば、今日の定義ではΩ-記法は前述のようにO-記法の定義の大小反転だが、ハーディー達の定義ではΩ(g)はo(g)を満たさない事として定義していた。

両者の定義は性質のよい関数、例えば多項式に対しては同値だが、極限に近づく際に振動するような関数に関しては必ずしも同値ではない。

記法	意味	インフォーマルな定義：十分大きい n に対して……	ε-δ記法による正式な定義
[math]f(n) \in O(g(n))[/math]	[math]f[/math] は漸近的に（定数倍を除いて）[math]g[/math] によって上からおさえられる	ある正数 k に対して [math]|f(n)| \leq k\cdot g(n)[/math]	[math]\exists k\gt 0 \; \exists n_0 \; \forall n\gt n_0 \; |f(n)| \leq k\cdot |g(n)|[/math] or [math] \exists k\gt 0 \; \exists n_0 \; \forall n\gt n_0 \; f(n) \leq k\cdot g(n)[/math]
[math]f(n) \in \Omega(g(n))[/math]	2つの定義： HLの定義： [math]f[/math] は漸近的に [math]g[/math] によって支配されない 今日の定義： [math]f[/math] は漸近的に [math]g[/math] によって下からおさえられる	HLの定義： 無限に多くの n の値とある正数 k に対して [math]f(n) \geq k\cdot g(n)[/math] 今日の定義： ある正数 k に対して[math]f(n) \geq k\cdot g(n)[/math]	HLの定義： [math]\exists k\gt 0 \; \forall n_0 \; \exists n\gt n_0 \; f(n) \geq k\cdot g(n)[/math] 今日の定義： [math]\exists k\gt 0 \; \exists n_0 \; \forall n\gt n_0 \; f(n) \geq k\cdot g(n)[/math]
[math]f(n) \in \Theta(g(n))[/math]	[math]f[/math] は漸近的に [math]g[/math] によって上と下両方からおさえられる	ある正数 k1, k2 に対して [math]k_1\cdot g(n) \leq f(n) \leq k_2\cdot g(n)[/math]	[math]\exists k_1\gt 0 \; \exists k_2\gt 0 \; \exists n_0 \; \forall n\gt n_0[/math] [math]k_1\cdot g(n) \leq f(n) \leq k_2\cdot g(n)[/math]
[math]f(n) \in o(g(n))[/math]	[math]f[/math] は漸近的に [math]g[/math] によって支配される	任意の正数 [math]k[/math] を固定するごとに [math]|f(n)| \le k\cdot|g(n)|[/math]	[math]\forall k\gt 0 \; \exists n_0 \; \forall n\gt n_0 \; |f(n)| \le k\cdot |g(n)|[/math]
[math]f(n) \in \omega(g(n))[/math]	[math]f[/math] は漸近的に [math]g[/math] を支配する	任意の正数 [math]k[/math] を固定するごとに [math]|f(n)| \ge k\cdot|g(n)|[/math]	[math]\forall k\gt 0 \; \exists n_0 \; \forall n\gt n_0 \ |f(n)| \ge k\cdot |g(n)|[/math]
[math]f(n)\sim g(n)\![/math]	[math]f[/math] は漸近的に [math]g[/math] に等しい	[math]f(n)/g(n) \to 1[/math]	[math]\forall \varepsilon\gt 0\;\exists n_0\;\forall n\gt n_0\;\left|{f(n) \over g(n)}-1\right|\lt \varepsilon[/math]

また、計算機科学では

[math]f(n) = \tilde{O} (g(n))[/math]

を

[math]\exists k \quad \text{ s.t. }\quad f(n) = O(g(n) \log^k(g(n))[/math]

の意味で用いる。対数因子を無視すればこれは本質的には O-記法である。この記法は "nit-picking" のクラスを記述するのにしばしば用いられる。これは log^k(n) が任意の定数 k と正の定数 ε に対して常に ο(n^ε) となるからである。

一般化と関連用法

関数のとりうる値は、絶対値をノルムに取り替えるだけでそのまま任意のノルム線型空間の元に一般化できる。f や g は同じ空間に値を取る必要はない。g のとる値は任意の位相群の元にすることも可能である。

「極限操作」"x → x₀" は、勝手なフィルター基の導入によって f と g の有向点族として一般化される。

o-記法は微分の定義や、極めて一般の空間における微分可能性を定義するのに有効である。また、関数の漸近同値を

[math] f\sim g \iff (f-g) = o(g) [/math]

と定めることができる。これは同値関係であり、上述の f が Θ(g) 程度であるという関係よりもなお強い制限を表す記法になっている。f と g が正値実数値関数なら lim f/g = 1 なる関係式に簡略化できる。例えば、2x は Θ(x) のオーダーだが、 2x − x は o(x) のオーダーでない。

一般的なオーダー

計算機科学、特に計算量理論、アルゴリズム論、暗号理論では、アルゴリズムの計算時間を評価するのに O-記法を頻繁に用いる。

アルゴリズムの計算量の評価よく使われるO-記法関数の種類を示す。

これらの中でも特に重要なものには、個別の名称がついている(多項式時間など)。

以下、 nはアルゴリズムに入力されるデータのビット数を表す。

注意しなければならないのは、アルゴリズムに整数 N を入力するときである。N のビット数 n はおよそ log₂ N なので、例えば「多項式時間」といったとき、これはN の多項式ではなく n の多項式を表す。

記法	名称	アルゴリズムの例
[math]O\left(1\right)[/math]	定数時間 (Constant time)	（整数の）偶奇判別
[math]O\left(\log^* n\right)[/math]	反復対数 (iterated logarithmic)	Hopcroft, Ullmanによる素集合データ構造における探索アルゴリズム
[math]O\left(\log n\right)[/math]	対数 (logarithmic)	ソート済み配列における二分探索
[math]O\left({n^c}\right), 0\lt \exist c\lt 1[/math]	分数指数関数 (fractional power)	kd木上の探索
[math]O\left(n\right)[/math]	線形関数 (linear)	非ソート配列上の探索、離散ウェーブレット変換
[math]O\left(n\log n\right)[/math]	準線形、線形対数 (linearithmic, loglinear, or quasilinear)	ヒープソート、高速フーリエ変換
[math]O\left({n^2}\right)[/math]	二乗時間 (quadratic)	挿入ソート、離散フーリエ変換
[math]O\left({n^c}\right), \exist c\ge 1[/math]	多項式時間	ワーシャル-フロイド法
[math]O{(2^n)}[/math]	指数時間 (exponential, geometricとも)	（現在最も速い）巡回セールスマン問題の（厳密解の）解法
[math]O\left(n!\right)[/math]	階乗関数 (factorial, combinatorialとも)	2つの論理式の同型判定[1]、巡回セールス問題などのNP完全問題の全探索による解法
[math]O\left(2^{c^n}\right) \exist c\gt 0 [/math]	二重指数時間	AC単一化子の完備集合の探索[2]

一般的ではないが、更に発散速度の速い関数も存在する（アッカーマン関数 A(m, n) など）。逆に更に発散速度の遅い関数として、逆関数である逆アッカーマン関数 α(n) などもあり、実際にあるアルゴリズムの計算量の見積りとして出現する。この関数は上界こそないものの、非常に発散速度が遅いために実用的には定数と見なされる (α(3) = 1, α(7) = 2, α(61) = 3, [math]\alpha(2^{2^{2^{65536}}} - 3) = 4[/math], ...)。

歴史

O-記法はドイツの数論家であるポール・バッハマンによって1894年に彼の著書『解析数論』(Analytische Zahlentheorie) の第二巻で初めて導入された（1892年に著された第一巻では用いられていない）。これに触発されてエドムント・ランダウが1909年にo-記法を発明した。

なお、ハーディとリトルウッドもランダウの記号[math] f=O(g)\, [/math]に相当するものを別の記号[math] f\preceq g\, [/math]で表現している。彼らはΩ-記法も現在と近い意味で用いており、今日の言葉でいえば、彼らのΩはo(g)でない事を表している。

ドナルド・クヌースは、計算機科学の世界にO-記法を導入し、Ω-記法やΘ-記法も再導入した。

具体例

関数 f(n) が他の関数の有限和で表せるとき(多項式であるとき)、その内最も発散速度の速い関数が f(n) のオーダーを決定づける。以下にその例を挙げる。

[math]f(n) = 9 \log n + 5 (\log n)^3 + 3n^2 + 2n^3 \in O(n^3).[/math]

例での場合、係数を無視してnに関する項を見ると、log n、(log n)³、n²、n³の4つが存在し、このうちn³が最も発散が速い。そのため、他のnに関する項に関わらず、オーダーはO(n³)とする。

特に、関数が n の多項式でおさえられるならば、n が無限大に発散するに従ってより低いオーダーの項まで無視できるようになる。

O(n^c) と O(cⁿ) は全く異なる。前者の定数 cがどれほど大きかろうと、後者の方がずっとずっと速く発散する。どのような定数 c に対しても n^cより速く発散する関数は超多項式 (superpolynomial) と呼ばれる。また、どのような定数 c に対しても cⁿ よりも遅く発散する関数は準指数関数 (subexponential) と呼ばれる。アルゴリズムの計算量が超多項式かつ準指数関数であることもあり得る。例えば、現在知られている内で最も早い因数分解のアルゴリズムもこれに含まれる。

O(log n) と O(log(n^c)) は全く等価である。なぜならば、log(n^c) = c log n より2つの指数関数は定数係数のみが異なり、これは big O-記法では無視されるからである。同様に異なる底を持つ対数関数も等価であるが、一方、異なる底を持つ指数関数は等価ではない。これはよくある勘違いである。例えば、2ⁿ と 3ⁿ は同じオーダーではない。

入力サイズの単位の変更は、アルゴリズムの計算量を変えるかもしれないしそうでないかもしれない。単位を変更するということは、関数に現れる全ての n にある定数を掛けることと同じである。例えば、アルゴリズムが n² のオーダーで動くとき、n を cn で置き換えれば計算量は c²n² となり、big O-記法では c² は無視されるので計算量は変化しない (c²n² ∈ O(n²))。しかし例えば 2ⁿ のオーダーで動くアルゴリズムでは、n を cn で置き換えると計算量は 2^cn = (2^c)ⁿ となる。これは 2ⁿ とは等しくない（もちろん、c = 1 の場合を除く）。

例

次の多項式関数を考える

[math]\begin{align} f(x) & = 6x^4 -2x^3 +5, \\ g(x) & = x^4.\end{align}[/math]

このとき、f(x) のオーダーは O(g(x)) または O(x⁴) である。実際、オーダーの定義からこれはある定数 Cと x₀ が存在して、x₀ < x なる任意の x に対し |f(x)| ≤ C |g(x)| が成り立つことを意味するが、x > 1 において

[math]\begin{align} |6x^4 - 2x^3 + 5| & \le 6x^4 + 2x^3 + 5\\ & \le 6x^4 + 2x^4 + 5x^4\\ & \le 13x^4\\ & \le 13 |x^4| \end{align}[/math]

であるから、C = 13, x₀ = 1 とおけばよい。

• リーマン予想が正しければ、x 以下の素数の個数 π(x) は次のように
  [math]\pi(x) = \int_2^x\frac{dt}{\log t} + O(\sqrt{x}\,\log x)[/math]
  と評価できる（素数定理も参照）。
• バブルソートの時間的計算量を考えると、n 個の要素からなる列をソートするのに掛かる時間はO(n²) である。クイックソートを使えば、平均計算時間を O(n log n) に改善できる（但し最悪時にはO(n²)）。
• n 次正方行列の固有値を求めるアルゴリズムは、少なくともその行列に含まれる n² 個の要素を読み取らなければならない。従って、固有値を求めるアルゴリズムの時間的計算量の下界は Ω(n²) である。

すなわち、一般的な行列に対してその固有値を計算するのに掛かる時間が n² のオーダーを下回るアルゴリズムは存在しない。

無限大における漸近挙動と計算量の見積り

O-記法はアルゴリズムの効率を解析するのに有用である。たとえば、あるサイズ n の問題(例えば処理すべきデータが n 個あるなど)を解くのに掛かる時間あるいは手順数が T(n) = 4n² − 2n + 2 である場合を考える。

このとき、n を次第に大きくしていくと、 T(n) に対して n² の項の影響が支配的になり、他の項はほとんど無視できるようになる（たとえば n = 500 としてみると、4n² の項は 2n の項の実に1000倍であり、後者を無視しても式に与える影響は、計算量を考える上でほとんど無視できる）。

さらに、n³ や 2ⁿ といった他のオーダーの式と比較する分には係数も無関係になる（たとえば T(n) = 1,000,000n² のように係数が大きい関数と、それより指数が1大きい U(n) = n³ を比較する。仮に n = 1,000,000 としてみると T(1,000,000) = 1,000,000×1,000,000² = 1,000,000³ = U(1,000,000) だから、n > 1,000,000 の場合は常に U(n) > T(n) である。）。

こうして残る影響をすくい上げて、O-記法では

[math]T(n)\in O(n^2)[/math]

と書いて、「n² のオーダーである」と言い、これによってこのアルゴリズムの時間あるいは手順数T(n) の増加具合が n² に支配されることを表現する。

参考文献

• Marian Slodicka & Sandy Van Wontergem. Mathematical Analysis I. University of Ghent, 2004.
• Donald Knuth. Big Omicron and big Omega and big Theta, ACM SIGACT News, Volume 8, Issue 2, 1976.
• Donald Knuth. The Art of Computer Programming, Volume 1: Fundamental Algorithms, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89683-4. Section 1.2.11: Asymptotic Representations, pp.107–123.
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 3.1: Asymptotic notation, pp.41–50.
• Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X.  Pages 226–228 of section 7.1: Measuring complexity.
• Jeremy Avigad, Kevin Donnelly. Formalizing O notation in Isabelle/HOL
• Paul E. Black, "big-O notation", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 11 March 2005. Retrieved December 16, 2006.
• Paul E. Black, "little-o notation", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 17 December 2004. Retrieved December 16, 2006.
• Paul E. Black, "Ω", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 17 December 2004. Retrieved December 16, 2006.
• Paul E. Black, "ω", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 29 November 2004. Retrieved December 16, 2006.
• Paul E. Black, "Θ", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 17 December 2004. Retrieved December 16, 2006.

関連項目

• 漸近展開 - テーラーの公式の一般化である関数の近似
• 漸近最適 - 考えている問題の下界となる定数の範囲内に上界が漸近的に収まるようなアルゴリズムを記述する際にしばしば用いられる用語
• ハーディー記法 - 別の漸近記法
• ナックビンの定理 - 有界な複素解析関数について、積分変換の収束域について述べるためのもの