ビッグオー記法
$\mathcal{O}$記法は漸近的上界を意味する。
$
\mathcal{O(g(n))} = {f(n) : ある正定数cとn_0が存在して、すべてのn \ge n_0 に対して0 \le f(n) \le cg(n)を満たす }
$
ビッグオメガ記法
$\Omega$記法は漸近的下界を意味する。
$
\Omega (g(n)) = {f(n) : ある正定数cとn_0が存在して、すべてのn \ge n_0 に対して0 \le cg(n) \le f(n)を満たす }
$
ビッグシータ記法
$\Theta$記法は漸近的にタイトな限界を表現する。
$
\Theta (g(n)) = {f(n) : ある正定数c_1,c_2,n_0が存在して、すべてのn \ge n_0 に対して0 \le c_1g(n) \le f(n) \le c_2g(n)を満たす }
$
$\mathcal{O},\Omega,\Theta$記法の定義から以下の定理が成り立つ。
$
任意に選んだ2つの関数をf(n)とg(n)とする。
\
f(n) = \Theta(g(n))であるための必要十分条件は、
\
f(n) = \mathcal{O(g(n))}かつ f(n) = \Omega(g(n))
$
スモールオー記法
$\mathcal{o}$記法は漸近的にタイトではない上界を与える。
$
\mathcal{o(g(n))} = {f(n) : 任意の正定数c > 0 に対して、 ある正定数n_0が存在して、すべてのn \ge n_0 に対して0 \le f(n) \le cg(n)を満たす }
$
直感的には$n$が増加するに従って、$f(n)$は$g(n)$と比較して無視できるようになる。
つまり、
$
\lim_{n \to \infty} \frac{f(n)}{g(n)} = 0
$
となる。
スモールオメガ記法
$\omega$記法は漸近的にタイトでない下界を与える。
$
\omega (g(n)) = {f(n) : 任意の正定数c > 0 に対して、ある正定数n_0が存在して、すべてのn \ge n_0 に対して0 \le cg(n) \le f(n)を満たす }
$
$n$が増加するに従って、$f(n)$は$g(n)$と比較して大きくなるようになる。
つまり、
$
\lim_{n \to \infty} \frac{f(n)}{g(n)} = \infty
$
となる。