ランダウの記号

ランダウの記号（ランダウのきごう、Landau symbol）は、関数極限における漸近挙動、すなわち値の変動のおおよその評価を与えるための記法である。ポール・バッハマンによって発明され、エドムント・ランダウが広めた。誤解されがちであるが『理論物理学教程』の著者であるレフ・ランダウとは別人である。ランダウの漸近記法(asymptotic notation)、ランダウ記法 (Landau notation) あるいは主要な記号として O を用いることから（ランダウの）O-記法などともいう。

概要

変数の無限大あるいは無限小の変動に対する関数の挙動を、ある程度わかりやすい別の関数を目安にして記述する目的で用いられる。解析学では誤差項を記述するためによく使われる。また、離散的な値をとる変数を持つ関数（数列とみなして差し支えない）を考えることで数列の離散的な挙動も記述できる。特に計算理論では計算量を評価するために一般的に用いられる。

記号 O は通常、関数の大きさを上からの漸近的な上界を別のわかりやすい関数によって記述するために用いられる。同様に上界や下界あるいはその両側からの評価を様々に与えることで、o, Ω, ω, Θ といった類似記法が定義される。O-記法を簡略的に流用して漸近的 tight bound（比が有限かつ有界、この場合下限が0であることも発散に含む）を記述することも一般に行われるが、もっと正確に漸近的に漸近的 tight bound であることを明示するならば Θ-記法を用いる。

O-記法は大きく二つの分野で用いられる。数学では、無限級数（とくに漸近級数）を打ち切ったときの剰余項の特徴づけなどに使われる。また計算機科学ではアルゴリズムの計算量の解析に用いられる。

この記法はドイツの数論家であるポール・バッハマンによって1894年に彼の著書『解析数論』(Analytische Zahlentheorie) の第二巻で初めて導入された（1892年に著された第一巻では用いられていない）。この記法が一般に広まるのは、別のドイツ人数論家であるエドムント・ランダウの仕事によるもので、ランダウの記号と呼ばれるゆえんである。「程度」（オーダー）を意味するこの O はもとは大文字のオミクロンであったが、今日では形の似たラテンアルファベットの大文字オーと同一視され、オーも用いられる。しかし、数字の 0 では決してない。

この記法には二つ、形式的には近いが確かに異なる用法がある。無限大に関する漸近挙動と無限小に関する漸近挙動である。この差異は原理的なものではなくあくまで応用上のもので、「O-記法」の定義は、関数に対して引数の極限をとる際の行き先の違いを除いて、どちらの場合も同じものである。

無限大における漸近挙動

O-記法はアルゴリズムの効率を解析するのに有用である。たとえば、あるサイズ n の問題を解くのに掛かる時間あるいは手順数が T(n) = 4n² − 2n + 2 と求まったとき、n を次第に大きくしていくと n² の項ばかり効いてくるようになり他の項はほとんど無視できるようになる（n = 500 としてみると、4n² の項は 2n の項の実に1000倍であり、後者を無視しても式に与える影響は計算量を考える上でほとんど無視できる程度である）。さらに、n³ や 2ⁿ といった他のオーダーの式と比較する分には係数も無関係になる。たとえ T(n) = 1,000,000n² だったとしても、U(n) = n³ であれば、T(1,000,000) = 1,000,000³ = U(1,000,000) だから、n が 1,000,000 を超えて大きくなれば常に後者のほうが大きいことになる。

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

と表して、このアルゴリズムの計算量は「n² のオーダーである」と言い表す。

無限小に対する漸近挙動

O-記法は数学的な関数の近似における誤差項の記述にも使われる。例えば

<math>e^x=1+x+\frac{x^2}{2}+O(x^3)\qquad\hbox{as}\ x\to 0</math>

なる式は、x が0の付近で　e^x − (1 + x + x²/2) という差（誤差）の絶対値が |x|³ のある定数倍で押さえられることを意味する。

厳密な定義

f(x) と g(x) は実数からなるある集合上で定義されているとするとき、「f(x) が x → ∞ のとき O(g(x)) 程度である」ということを

<math>{}^\exists x_0, {}^\exists M>0 \quad \text{ s.t. }\quad x>x_0 \Rightarrow |f(x)|<M|g(x)|</math>

となることとして定める。また、ある実数 a の付近での挙動を記述するならば「f(x) が x → a のとき O(g(x)) のオーダーである」ということを

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

であることと定める。a の十分近くで　g(x) が 0 の値をとらないならこれらの定義を上極限を使って統一的に記述できる。つまり「f(x) が x → a のとき O(g(x)) の程度である」とは

<math>\varlimsup_{x\to a} \left|\frac{f(x)}{g(x)}\right| < \infty</math>

が満たされることである。

数学では、無限大の近くや a の近くという二種類の漸近挙動を両方考えるが、計算量理論では無限大での漸近挙動がもっぱら扱われる。もっといえば、正値関数のみを扱うことも多く、その場合絶対値記号すら忘れてよい。

記法の問題

上で定義された「f(x) が O(g(x)) の程度である」という言及はしばしば "f(x) = O(g(x))" と記される。これは少し紛らわしい記法の濫用で、二つの関数が等しいという意味ではないし、O(g(x)) があるせいで対称性も持たない。

たとえば　<math>O(x) = O(x^2)</math> 　であるが、　<math>O(x^2)\ne O(x)</math>　である。

この理由から、集合の記法を用いて f ∈ O(g) と書く流儀もある。この場合、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ⁿ) なるもののうちに、n^f(n) = g(n) を満たすものを選びうる」となる。上記の集合記法ならば、「左辺で表される関数のクラスは右辺で表される関数のクラスの部分集合になる」という意味に取れる。

一般的なオーダー

以下に、アルゴリズムの（計算量の）解析の際によく使われるO-記法関数の種類を示す。（定数オーダー以外の）全ての関数はnの増加に従って無限大に発散するので、表は発散速度の遅い順に並べてある。また、cは任意の定数である。関数名については、ここで示した以外の名称で呼ばれることもある。

記法	名称	アルゴリズムの例
<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(\left(\log n\right)^c\right)</math>	対数多項式 (polylogarithmic)	AKS素数判定法による自然数nの素数判定（nは入力サイズではない）
<math>O\left({n^c}\right), 0<c<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), c>1</math>	多項式関数 (polynomial, algebraicとも)	ワーシャル-フロイド法
<math>O\left({c^n}\right)=2^{O(n)}</math>	指数関数 (exponential, geometricとも)	（現在最も速い）巡回セールスマン問題の（厳密解の）解法
<math>O\left(n!\right)</math>	階乗関数 (factorial, combinatorialとも)	2つの論理式の同型判定[1]、巡回セールス問題などのNP完全問題の全探索による解法
<math>O\left(2^{c^n}\right)</math>	二重指数関数 (double exponential)	AC単一化子の完備集合の探索[2]

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

例

次の多項式関数を考える

<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² のオーダーを下回るアルゴリズムは存在しない。

性質

関数 f(n) が他の関数の有限和で表せるとき(多項式であるとき)、その内最も発散速度の速い関数が f(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>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>

その他の有用な関係式は以下の#その他の漸近記法で記す。

その他の漸近記法

O-記法は関数比較のための漸近記法として最も一般に用いられるものであるが、多くの場合に漸近的な両側有界性を表すために Θ に置き換えられる。ここではランダウの記号として知られるいくつかの異なる記法を記す。

記法	意味	定義	ε-δ記法による言い換え
<math>f(n) \in O(g(n))</math>	漸近的に上に有界	\frac{f(n)}{g(n)}\right\| < \infty</math>	∃M > 0, ∃x₀ such that \|f(x)\| ≤ M\|g(x)\| for all x > x₀.
<math>f(n) \in \Omega(g(n))</math>	漸近的に下に有界	\frac{f(n)}{g(n)}\right\| > 0 </math>	∃M > 0, ∃x₀ such that \|f(x)\| ≥ M\|g(x)\| for all x > x₀.
<math>f(n) \in \Theta(g(n))</math>	漸近的に両側に有界で、上下界が一致	\frac{f(n)}{g(n)}\right\| \\ &\quad \leq \varlimsup_{n \to \infty} \left\|\frac{f(n)}{g(n)}\right\|< \infty \end{align}</math>	f(n) ∈ O(g(n)) かつ f(n) ∈ Ω(g(n))
<math>f(n) \in o(g(n))</math>	漸近的に消える	\frac{f(n)}{g(n)}\right\| = 0</math>	∀M > 0, ∃x₀ such that \|f(x)\| < M\|g(x)\| for all x > x₀.
<math>f(n) \in \omega(g(n))</math>	漸近支配的	\frac{f(n)}{g(n)}\right\| = \infty</math>	∀M > 0, ∃x₀ such that \|f(x)\| > M\|g(x)\| for all x > x₀.

ここでの記号 o はギリシャ文字のオミクロンであるが、「小文字のオー」と呼ぶこともしばしばである。

f(n) = o(g(n)) であるという関係を、「f(n) はスモール・オーのオーダーで g(n)」などという。これは直感的には、g(n) は f(n) よりもずっと早く発散するということを意味している。もちろん数学的に厳密に言えば、f(n)/g(n) が極限で 0 に収束するという意味である。例えば、

<math>2n = o(n^2),</math>
<math>2n^2 \ne o(n^2)</math>

などとなる。Θ-記法と Ω-記法は計算機科学でよく用いられる記法であり、ο-記法は数学ではよく目にするが計算機科学ではそれほどは見かけない。ω-記法を用いることはまれである。

また、計算機科学では記号 Õ を

<math>f(n) = \tilde{O} (g(n))</math>

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

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

<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>N: |g(n,m)| \le C(n+m)</math>

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

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

<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>

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

一般化と関連用法

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

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

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

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

参考文献

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.
テンプレート:Cite book 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.

脚注