【徹底解説】ランダウの記号の定義

本記事は数学の徹底解説シリーズに含まれます。

初学者の分かりやすさを優先するため,多少正確でない表現が混在することがあります。もし致命的な間違いがあればご指摘いただけると助かります。

目次

意味

ランダウの記号は,ある関数の漸近的なふるまいを評価する際に利用されます。ざっくりとした意味は以下です。ただし,$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$に対して

\begin{align}
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$に対して

\begin{align}
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}$に対して

\begin{align}
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}$に対して

\begin{align}
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}$に対して

\begin{align}
T(n) > cf(n)
\end{align}

が成り立つとき,計算量$T(n)$は$\omega (f(n))$と表記される。

「計算量$T(n)$はスモールオメガ$f(n)$である」と読みます。漸近的にタイトでない下界は「$T(n)$は$f(n)$より大きい」という意味です。

参考

シェアはこちらからお願いします!

コメント

コメントする

※ Please enter your comments in Japanese to distinguish from spam.

目次