講義/漸近記法

関数の極限での大きさを表現する方法 (asymptotic notation)．よくアルゴリズムの性能を入力の大きさに対する関数として表現して比較する時に用いられるが，応用はそれに限られているわけではない．

以下では， $f(n)$ , $g(n)$ を正実数上の関数とする．

1 O記法 (オー記法)

直感的には，関数 $f$ が関数 $g$ よりも増え方が小さい，すなわち $(\exists c)(\forall n) \frac{f(n)}{g(n)} < c$ であるとき， $f(n) = O(g(n))$ と言う．

厳密には $g(n)$ が 0 になる場合を考慮して， $(\exists c, N > 0) (\forall n \ge N) f(n) < c g(n)$ であるとき， $f(n) = O(g(n))$ と言う．

$f(n)=O(g(n))$ は「 $f(n)$ は $g(n)$ のオーダーである」と読んだりする．

明らかに $f(n)=O(g(n))$ かつ $g(n)=O(h(n))$ ならば $f(n)=O(h(n))$ である．例えば $O(n)$ の関数は $O(n^2)$ でもある．

逆に，直感的には関数 $f$ が関数 $g$ よりも増え方が大きいとき，すなわち $(\exists c, N > 0) (\forall n \le N) f(n) > c g(n)$ であるとき， $f(n) = \Omega(g(n))$ と言う．

$f$ と $g$ の増え方は同じ（定数倍以下）のとき，すなわち， $f(n) = O(g(n))$ かつ $f(n) = \Omega(g(n))$ であるとき， $f(n) = \Theta(g(n))$ と言う．

$f$ の大きさは $g$ の大きさに比べれば無視できる，すなわち $\lim_{n \rightarrow \infty} f(n)/g(n) = 0$ であるとき， $f(n) = o(g(n))$ と言う．またこのとき， $g(n) = \omega(f(n))$ とも言う．