2015/08/02

オーダー記法の定義と大雑把な意味

分野: その他  レベル: 大学数学

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

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

無限大や $0$ 付近でのふるまいを以下の二つの考え方に従って大雑把に評価しようという発想です。

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

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

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

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

主にアルゴリズムの計算量評価に用いられる記号です。
三種類の記号について,表記,大雑把な意味(重要),きちんとした定義,具体例を解説します。


ビッグオー(重要)
表記:$f(n)=O(g(n))$
意味:$f(n)$ の発散のスピードは早くても $g(n)$ と同じくらい
定義:ある $n_0,C$ が存在して $n > n_0$ なら $|f(n)| \leq C|g(n)|$
例:$4n^3+1=O(n^3)$,$4n^3+1=O(n^4)$

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


ビッグオメガ
表記:$f(n)=\Omega (g(n))$
意味:$f(n)$ の発散のスピードは遅くても $g(n)$ と同じくらい
定義:ある $n_0,C$ が存在して $n > n_0$ なら $|f(n)| \geq C|g(n)|$
例:$4n^3+1=\Omega(n^3)$,$4n^3+1=\Omega(n^2)$


ビッグシータ
表記:$f(n)=\Theta (g(n))$
意味:$f(n)$ はだいたい $g(n)$ と同じスピードで発散する
定義:ある $n_0,C_1,C_2$ が存在して $n > n_0$ なら $C_1|g(n)| \leq |f(n)| \leq C_2|g(n)|$
例:$4n^3=\Theta(n^3)$,$2n+3^n=\Theta(3^n)$

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

よく登場するオーダー

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

(多項式オーダーの世界)
$O(1)$,$O(\log n)$,$O(n)$,$O(n\log\log n)$,$O(n\log n)$,$O(n^2)$,$O(n^3)$,$O(n^{100})$
ーーー越えられない壁ーーー
$O(2^{\sqrt{n}})$,$O(2^n)$,$O(n!)$

$0$ 付近でのふるまい

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


ビッグオー
表記:$O(f(x))$
意味:$x\to 0$ のとき $0$ に近づくスピードが $f(x)$ と同じくらい(または $f(x)$ よりはやい)

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


スモールオー
表記:$o(f(x))$
意味:$x\to 0$ のとき $0$ に近づくスピードが $f(x)$ よりもはやい

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

定数倍の差を無視するだなんて器が大きいですね。
分野: その他  レベル: 大学数学