オーダー記法(ランダウの記号)の定義と大雑把な意味

オーダー記法(ランダウの記号)は,無限大でのふるまいや 00 付近でのふるまいを大雑把に評価するのに用いられる。

オーダー記法の基本的な考え方

無限大や 00 付近でのふるまいを,以下の2つの考え方に従って大雑把に評価します。

  1. 影響力が一番強い項以外無視する
  2. 定数倍の差は無視する(係数は書かない)

例えば,n3+nn^3+n はルール1により nn\to\infty では n3n^3 と同じくらい,2nlogn2n\log n はルール2により nn\to\infty では nlognn\log n と同じくらい,と考えます。

以下では,無限大でのふるまいについて詳しく解説します(00 付近でのふるまいは最後に少しだけ)。

無限大でのふるまい(計算量理論)

主にアルゴリズムの計算量評価に用いられる記号です。

三種類の記号について,表記・大雑把な意味(重要)・きちんとした定義・具体例を解説します。

  • ビッグオー(重要)

表記: f(n)=O(g(n))f(n)=O(g(n))

意味: f(n)f(n) の発散のスピードは 早くても g(n)g(n) と同じくらい

定義:ある n0,Cn_0,C が存在して n>n0n > n_0 なら f(n)Cg(n)|f(n)| \leq C|g(n)|

例: 4n3+1=O(n3)4n^3+1=O(n^3)4n3+1=O(n4)4n^3+1=O(n^4)

注:例の二つ目の評価は一つ目の評価より弱い無意味なものですが,間違いではありません。

  • ビッグオメガ

表記: f(n)=Ω(g(n))f(n)=\Omega (g(n))

意味: f(n)f(n) の発散のスピードは 遅くても g(n)g(n) と同じくらい

定義:ある n0,Cn_0,C が存在して n>n0n > n_0 なら f(n)Cg(n)|f(n)| \geq C|g(n)|

例: 4n3+1=Ω(n3)4n^3+1=\Omega(n^3)4n3+1=Ω(n2)4n^3+1=\Omega(n^2)

  • ビッグシータ

表記: f(n)=Θ(g(n))f(n)=\Theta (g(n))

意味: f(n)f(n)だいたい g(n)g(n) と同じスピードで発散する

定義:ある n0,C1,C2n_0,C_1,C_2 が存在して n>n0n > n_0 なら C1g(n)f(n)C2g(n)C_1|g(n)| \leq |f(n)| \leq C_2|g(n)|

例: 4n3=Θ(n3)4n^3=\Theta(n^3)2n+3n=Θ(3n)2n+3^n=\Theta(3^n)

注:ビッグオーをビッグシータの意味で使うことも多いので注意が必要です。

よく登場するオーダー

アルゴリズムの計算量は少ない(発散が遅い)方が当然嬉しいです。よく登場するオーダーを嬉しい順に並べてみました。

(多項式オーダーの世界)

O(1)O(1)O(logn)O(\log n)O(n)O(n)O(nloglogn)O(n\log\log n)O(nlogn)O(n\log n)O(n2)O(n^2)O(n3)O(n^3)O(n100)O(n^{100})

ーーー越えられない壁ーーー

O(2n)O(2^{\sqrt{n}})O(2n)O(2^n)O(n!)O(n!)

00 付近でのふるまい

例えば,テイラー展開の剰余項について議論するときなどに登場します。

  • ビッグオー

表記: O(f(x))O(f(x))

意味: x0x\to 0 のとき 00 に近づくスピードが f(x)f(x) と同じくらい(または f(x)f(x) よりはやい)

ex=1+x+x22+O(x3)e^x=1+x+\dfrac{x^2}{2}+O(x^3)

これは,ex(1+x+x22)x3\dfrac{e^x-(1+x+\frac{x^2}{2})}{x^3} の絶対値が(x=0x=0 の近くで)定数で上からおさえられることを表しています。

  • スモールオー

表記: o(f(x))o(f(x))

意味: x0x\to 0 のとき 00 に近づくスピードが f(x)f(x) よりもはやい

cosx=1x22+o(x3)\cos x=1-\dfrac{x^2}{2}+o(x^3)

これは limx0cosx(1x22)x3=0\displaystyle\lim_{x\to 0}\dfrac{\cos x-(1-\frac{x^2}{2})}{x^3}=0 を表しています。

定数倍の差を無視するなんて器が大きいですね。