ランダウの記号

ランダウの記号（ランダウのきごう、英: Landau symbol）は、主に関数の極限における漸近的な挙動を比較するときに用いられる記法である。

ランダウの漸近記法 (asymptotic notation)、ランダウ記法 (Landau notation) あるいは主要な記号として O （数字の0ではない）を用いることから（バッハマン-ランダウの）O-記法 (Bachmann-Landau O-notation^[1])、ランダウのオミクロンなどともいう。

記号 O はドイツ語のOrdnungの頭字にちなむ^[2]。

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

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

概要

ランダウの記号

f(x)=O(g(x))

は、x が充分大きいとき関数 f が関数 g に比例もしくはそれ以下におさえられることを示す。

たとえば二次関数 3x² + 4x + 10 が x を限りなく大きくしたときどのように増大するかを考えると、変数 x が 2 より大きければ第一項 3x² が他の項より大きく、さらに大きくなるほど支配的になることがわかる。漸近解析をする上では定数倍のような詳細は必要としないことが多く、O-記法を用いると、必要な情報を

3x^{2}+4x+10=O(x^{2})

と端的に表すことができる。

このように関数 g としては関数 f よりも単純なもの（上の例では x²）が通常用いられる。（#一般的なオーダー参照。）

一方、ランダウの記号

f(x)=o(g(x))

は関数 f がおおよそ関数 g 未満であることを示している。

たとえば x が十分大きいとき 3x² + 4x + 10 は x³ と比べると小さくなり、o-記法を用いると、これを

3x^{2}+4x+10=o(x^{3})

と表すことができる。（ただし、o-記法よりも O-記法の方が多くの場合好ましいと考えられている^[3]^[4]。）

これまでは変数を限りなく大きくしたときを例に説明してきたが、他にも変数を限りなく小さくしたときや、定数に限りなく近づけたときの漸近挙動も同様にランダウ記法で表すことができる。どの意味で記号が用いられているのかを

f(x)=O(g(x))\quad (x\to \infty )

のように明示する書き方もある。

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

$\lim _{x\to \infty }\left|{\frac {f(x)}{g(x)}}\right|$ 　が存在する場合には、その値が有限（0 も含む）であること（一般の場合は後述）。極限が存在しない場合、即ち振動する場合でも該当することはあることには注意されたい。
$\lim _{x\to \infty }\left|{\frac {f(x)}{g(x)}}\right|=0$

を表す。（厳密にはε-δ論法で定義する。）特に f(x) = o(1) は lim f(x) = 0 と同値である。

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

\mathrm {e} ^{x}=1+x+{\frac {x^{2}}{2!}}+{\frac {x^{3}}{3!}}+O(x^{4})\quad (x\to 0)

と書き表せる。

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

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

厳密な定義

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

f(x)=O(g(x))\quad (x\to \infty )

を

{}^{\exists }x_{0},{}^{\exists }M>0\quad {\text{ s.t. }}\quad {}^{\forall }x\;[x>x_{0}\Rightarrow |f(x)|\leq M|g(x)|]

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

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

f(x)=O(g(x))\quad (x\to a)

を

{}^{\exists }\delta >0,{}^{\exists }M>0\quad {\text{ s.t. }}\quad {}^{\forall }x\;[0<|x-a|<\delta \Rightarrow |f(x)|\leq M|g(x)|]

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

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

\varlimsup _{x\to a}\left|{\frac {f(x)}{g(x)}}\right|<\infty

が満たされることと同値である（a が∞の場合も同様）。特に f(x) = O(1) は、近傍において f(x) が有界であることと同値である。

記法の問題

上で定義された

f(x)=O(g(x))

という記法は広く用いられている確立した慣習ではあるが紛らわしい記法の濫用で、二つの関数が等しいという意味ではない。

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

O(x)=O(x^{2})

　であるが、　

O(x^{2})\neq O(x)

　である。

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

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

f\in O(g)

ないし、

f(x)\leq O(g(x))

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

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

{\begin{aligned}&(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{aligned}}

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

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

例えば三つの目の式は、

任意の関数 f(n) = O(1) に対し、g(n) = O(eⁿ) を満たすgを適切に選べば

n^{f(n)}\leq g(n)

が成立する

事を意味する。

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

任意の関数

f_{1}(n)=O(n^{1/2})\,

、

f_{2}(n)=O(O(\log \,n))\,

に対し、

g(n)=O(n^{5/2})\,

を満たすgを適切に選べば

(n+f_{1}(n))(n+f_{2}(n))^{2}\leq n^{3}+g(n)

が成立する

事を意味する。

性質

O-記法は次の性質を満たす。o-記法も同様の性質を満たす。

推移律: $f(n)=O(g(n)),\ g(n)=O(h(n))\implies f(n)=O(h(n)).$
和: $O(f(n))+O(f(n))=O(f(n)).$
積: $O(f(n))O(g(n))=O(f(n)g(n)),\qquad f(n)O(g(n))=O(f(n)g(n)).$
定数倍: $O(cf(n))=O(f(n))\quad (c\neq 0).$
冪等性: $O(O(f(n)))=O(f(n)).$

また p(n) と q(n) をゼロでない n の多項式とすると

{\begin{aligned}&p(n)=O(q(n))&&\iff &&\deg p(n)\leq \deg q(n)\\&p(n)=o(q(n))&&\iff &&\deg p(n)<\deg q(n)\end{aligned}}

が成り立つ。

多変数の場合

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

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

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

\forall n,m>N:|g(n,m)|\leq C(n+m)

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

f(n,m)=n^{2}+m^{3}+g(n,m)

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

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

という言明は、次の

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

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

その他の漸近記法

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

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

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

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

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

記法	意味	インフォーマルな定義	形式的定義
$f(n)\in O(g(n))$ $f(n)=O(g(n))$ $f(n)\preceq g(n)$ $f(n)\ll g(n)$	$f$ は漸近的に（定数倍を除いて） $g$ によって上からおさえられる	ある正数 k に対して、十分大きい n で $\|f(n)\|\leq k\cdot g(n)$	$\exists k>0\;\exists n_{0}\;\forall n>n_{0}\;\|f(n)\|\leq k\cdot \|g(n)\|$ or $\exists k>0\;\exists n_{0}\;\forall n>n_{0}\;f(n)\leq k\cdot g(n)$
$f(n)\in \Omega (g(n))$ $f(n)=\Omega (g(n))$ $f(n)\succeq g(n)$ $f(n)\gg g(n)$	2つの定義： HLの定義： $f$ は漸近的に $g$ によって支配されない今日の定義： $f$ は漸近的に $g$ によって下からおさえられる	HLの定義：無限に多くの n の値とある正数 k に対して $\|f(n)\|\geq k\cdot g(n)$ 今日の定義：ある正数 k に対して、十分大きい n で $\|f(n)\|\geq k\cdot g(n)$	HLの定義： $\exists k>0\;\forall n_{0}\;\exists n>n_{0}\;f(n)\geq k\cdot g(n)$ 今日の定義： $\exists k>0\;\exists n_{0}\;\forall n>n_{0}\;f(n)\geq k\cdot g(n)$
$f(n)\in \Theta (g(n))$ $f(n)=\Theta (g(n))$ $f(n)\asymp g(n)$	$f$ は漸近的に $g$ によって上と下両方からおさえられる	ある正数 k₁, k₂ に対して、十分大きい n で $k_{1}\cdot g(n)\leq \|f(n)\|\leq k_{2}\cdot g(n)$	$\exists k_{1}>0\;\exists k_{2}>0\;\exists n_{0}\;\forall n>n_{0}$ $k_{1}\cdot g(n)\leq f(n)\leq k_{2}\cdot g(n)$
$f(n)\in o(g(n))$ $f(n)=o(g(n))$ $f(n)\prec g(n)$	$f$ は漸近的に $g$ によって支配される	任意の正数 $k$ を固定するごとに、十分大きい n を取ると $\|f(n)\|\leq k\cdot \|g(n)\|$	$\forall k>0\;\exists n_{0}\;\forall n>n_{0}\;\|f(n)\|\leq k\cdot \|g(n)\|$
$f(n)\in \omega (g(n))$ $f(n)=\omega (g(n))$ $f(n)\succ g(n)$	$f$ は漸近的に $g$ を支配する	任意の正数 $k$ を固定するごとに、十分大きい n を取ると $\|f(n)\|\geq k\cdot \|g(n)\|$	$\forall k>0\;\exists n_{0}\;\forall n>n_{0}\ \|f(n)\|\geq k\cdot \|g(n)\|$
$f(n)\sim g(n)\!$	$f$ は漸近的に $g$ に等しい	$f(n)/g(n)\to 1$	$\forall \varepsilon >0\;\exists n_{0}\;\forall n>n_{0}\;\left\|{f(n) \over g(n)}-1\right\|<\varepsilon$

また、計算機科学では

f(n)={\tilde {O}}(g(n))

を

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

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

一般化と関連用法

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

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

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

f\sim g\iff (f-g)=o(g)

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

一般的なオーダー

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

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

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

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

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

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

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

歴史

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

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

またヴィノグラードフ（英語版）は $f=O(g)$ と $f\ll g$ を同じ意味で用いている^[7]^[8]。

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

具体例

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

f(n)=9\log n+5(\log n)^{3}+3n^{2}+2n^{3}\in O(n^{3}).

例での場合、係数を無視して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 の場合を除く）。

例

次の多項式関数を考える

{\begin{aligned}f(x)&=6x^{4}-2x^{3}+5,\\g(x)&=x^{4}.\end{aligned}}

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

{\begin{aligned}|6x^{4}-2x^{3}+5|&\leq 6x^{4}+2x^{3}+5\\&\leq 6x^{4}+2x^{4}+5x^{4}\\&\leq 13x^{4}\\&\leq 13|x^{4}|\end{aligned}}

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

リーマン予想が正しければ、x 以下の素数の個数 π(x) は次のように
$\pi (x)=\int _{2}^{x}{\frac {dt}{\log t}}+O({\sqrt {x}}\,\log x)$
と評価できる（素数定理も参照）。
バブルソートの時間的計算量を考えると、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-記法では

T(n)\in O(n^{2})

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

脚注

参考文献

日本数学会編『岩波数学辞典』（第4版）岩波書店、2007年。ISBN 978-4-00-080309-0。
de Bruijn, N. G. (1981). Asymptotic Methods in Analysis. Dover. ISBN 0-486-64221-6. Zbl 0556.41021
Graham, R. L.; Knuth, D. E.; Patashnik, O. (1994). Concrete Mathematics (Second ed.). Addison-Wesley. ISBN 0-201-55802-5
Marian Slodicka & Sandy Van Wontergem. Mathematical Analysis I. University of Ghent, 2004.
Donald Knuth (Apr.–June 1976). “Big Omicron and big Omega and big Theta”. ACM SIGACT News 8 (2): 18–24. doi:10.1145/1008328.1008329.
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.

概要