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

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

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!)$

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

• ビッグオー

表記： $O(f(x))$

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

• スモールオー

表記： $o(f(x))$

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