本記事は数学の徹底解説シリーズに含まれます。
初学者の分かりやすさを優先するため，多少正確でない表現が混在することがあります。もし致命的な間違いがあればご指摘いただけると助かります。
意味
ランダウの記号は，ある関数の漸近的なふるまいを評価する際に利用されます。ざっくりとした意味は以下です。ただし，$T(n)$は計算量を表します。
| $T(n)$の評価 | 意味 |
| $O(f(n))$ | $T(n)$は$f(n)$と同じか小さい |
| $\Omega(f(n))$ | $T(n)$は$f(n)$と同じか大きい |
| $\Theta(f(n))$ | $T(n)$は$f(n)$と同じ |
| $o(f(n))$ | $T(n)$は$f(n)$より小さい |
| $\omega(f(n))$ | $T(n)$は$f(n)$より大きい |
これらの記法を総称してランダウの記号と呼びます。特にビッグオー$O$はオーダー記法とも呼ばれ，アルゴリズムの計算量の評価などに利用されます。
漸近的な上界：ビッグオー記法
ある$c>0$と自然数$n_0$が存在して，全ての$n\geq n_0$に対して
T(n) \leq cf(n)
\end{align}
が成り立つとき，計算量$T(n)$は$O(f(n))$と表記される。
「計算量$T(n)$はビッグオー$f(n)$である」や「計算量$T(n)$はオーダー$f(n)$である」と読みます。漸近的上界は「$T(n)$は$f(n)$と同じか小さい」という意味です。
漸近的な下界：ビッグオメガ記法
ある$c>0$と自然数$n_0$が存在して，全ての$n\geq n_0$に対して
T(n) \geq cf(n)
\end{align}
が成り立つとき，計算量$T(n)$は$\Omega(f(n))$と表記される。
「計算量$T(n)$はビッグオメガ$f(n)$である」と読みます。漸近的下界は「$T(n)$は$f(n)$と同じか大きい」という意味です。
漸近的にタイトな限界：ビッグシータ記法
ある$c_{0}>0$，$c_{1}>0$と自然数$n_{0}$が存在して，全ての$n\geq n_{0}$に対して
c_{0}f(n) \leq T(n) \leq c_{1}f(n)
\end{align}
が成り立つとき，計算量$T(n)$は$\Theta(f(n))$と表記される。
「計算量$T(n)$はビッグシータ$f(n)$である」と読みます。漸近的にタイトな限界は「$T(n)$は理想状態でも最悪状態でも$f(n)$と同じ」という意味です。
漸近的にタイトでない上界：スモールオー記法
任意の$c>0$に対し，ある自然数$n_{0}$が存在して，全ての$n\geq n_{0}$に対して
T(n) < cf(n)
\end{align}
が成り立つとき，計算量$T(n)$は$o(f(n))$と表記される。
「計算量$T(n)$はスモールオー$f(n)$である」と読みます。漸近的にタイトでない上界は「$T(n)$は$f(n)$より小さい」という意味です。
漸近的にタイトでない下界：スモールオメガ記法
任意の$c>0$に対し，ある自然数$n_{0}$が存在して，全ての$n\geq n_{0}$に対して
T(n) > cf(n)
\end{align}
が成り立つとき，計算量$T(n)$は$\omega (f(n))$と表記される。
「計算量$T(n)$はスモールオメガ$f(n)$である」と読みます。漸近的にタイトでない下界は「$T(n)$は$f(n)$より大きい」という意味です。
コメント