ランダウの記号 (英:Landau symbol) は関数の値の増え方について、おおよその評価を与えるための記法である。O記法ともいう。Paul Bachmannによって発明され、エドムント・ランダウが広めた。

解析学では誤差項を記述するためによく使われる。また、計算理論では計算量を評価するために一般的に用いられる。

O, o, Θ, Ω, ∼の記号がある。

以下の説明に於いて、f(x), g(x)は実数から正の実数への関数とする。注意深く 0 を除くようにすれば任意の実変数実数値関数に一般化できるが、実用上は、十分先では符号の変化がないような関数についてこれらの記法を使うことが多い。

O記号

---

記号 O は、実数値(非負)関数の値の増え方を上から評価するために用いられ、 関数f(x)が関数g(x)の定数倍よりは小さい事を意味する。

アルゴリズムの計算量をおおまかに評価するために使われたり、誤差項の評価に使われる。

直感的には

$\backslash lim\_\{x\backslash to\backslash infty\}\; \backslash frac\{f(x)\}\{g(x)\}$

が発散しないときf(x) = O(g(x))と書く。

しかし$\backslash frac\{f(x)\}\{g(x)\}$はg(x)が0になる場合にはうまく定義できないので、より厳密には以下が成立する事をもって f(x) = O(g(x))を定義する：

ある定数$x\_0$、cが存在して$x>x\_0\; \backslash \; \backslash Rightarrow\backslash \; f(x)\; \backslash le\; cg(x)$

数学では後述する$\backslash Theta$記法の代わりにO記法を用いる事も多いが、計算機科学では両者を区別する。

なおO記法はOrder の頭文字をとったものであり，本来は立体のＯ（オー）を用いるのが歴史的に正しいが，近年は斜体を用いる人の方が増え，どちらが正しいのか不明瞭になりつつある．

o記号

---

f(x)がg(x)と比べて無視できるほど小さいときに$f(x)=o(g(x))$と書く。

直感的には

$\backslash lim\_\{x\backslash to\backslash infty\}\; \backslash frac\{f(x)\}\{g(x)\}\; =\; 0$

であるとき、f(x) = o(g(x))と書く。

しかし$g(x)=0$となる場合には上式ではうまく定義できないので、 より厳密には以下を持って定義する：

任意の$\backslash varepsilon>0$に対し、ある$x\_0$が存在して、全ての$x>x\_0$に対し$f(x)\backslash le\backslash varepsilon\; g(x)$が成立する。

f(x) = o(g(x))である事をf(x)はg(x)と比べて無視できるほど小さいという。 なお、計算幾何学では「無視できるほど小さい」という言葉をnegligibleの意味でも用いるので注意が必要である。

o記号をランダウのオミクロン記法ともいう。(つまり、「o」は「オー」ではなく「オミクロン」)。

Ω記号

---

$g(x)=O(f(x))$であるときに、$f(x)=\backslash Omega(g(x))$と書く。

Θ記号

---

関数fとgとの差が定数倍程度におさまるとき、$f(x)=\backslash Theta(g(x))$と書く。

すなわち、$f(x)=O(g(x))$かつ$f(x)=\backslash Omega(g(x))$であるときに$f(x)=\backslash Theta(g(x))$と書く。

$f(x)=\backslash Theta(g(x))$である事を$f(x)\backslash simeq\; g(x)$とも書く。 関係「$\backslash simeq$」は同値関係である。

なお、「$\backslash simeq$」という記号は他にも様々な意味に用いるので注意が必要である。

ω記号

---

$g(x)=o(f(x))$であるとき、$f(x)=\backslash omega(g(x))$と書く。

記法について

---

O記法、$\backslash Omega$記法、$\backslash Theta$をそれぞれ 「$f(x)\; \backslash le\; O(g(x))$」、「$f(x)\; \backslash ge\; O(g(x))$」、「$f(x)\; =\; O(g(x))$」と書く流儀も存在する。

例

---

• リーマン予想が正しければ、x以下の素数の個数π(x)は次のように評価できる（素数定理も参照）。

  $\backslash pi(x)\; =\; \backslash int\_2^x\backslash frac\{dt\}\{\backslash log\; t\}\; +\; O(\backslash sqrt\{x\}\backslash log\; x)$

• バブルソートの時間的計算量を考えると、n個の要素からなる列をソートするのに掛かる時間はO(n²)である。クイックソートを使えば、平均計算時間をO(n log n)に改善できる。

• $n$次正方行列の固有値を求めるアルゴリズムは、少なくともその行列に含まれる$n^2$個の要素を読み取らなければならない。従って、固有値を求めるアルゴリズムの時間的計算量の下界は$\backslash Omega\; (n^2)$である。すなわち、どんなに良いアルゴリズムであったとしても、一般に固有値を計算するのに掛かる時間が$n^2$のオーダーを下回ることはない。

数学の表記法

Landau-Symbole | Landau notation | Notations de Landau