『アルゴリズムイントロダクション第4版』の第3章で大事なとこだけまとめました。(ΘOΩ)　←顔みたいでかわいいね。

アルゴリズムの実行時間と漸近記法

アルゴリズムの効率性を評価し、入力サイズが増加した際のスケーラビリティを把握するために、実行時間の増加のオーダー（漸近的効率）を分析する。これには、係数や低次の項を無視し、入力サイズ $n$ が十分に大きい場合における実行時間の振る舞いに焦点を当てる 漸近記法 が用いられる。

Θ記法 (漸近的にタイトな限界)

$\Theta$記法は、関数の増加率が上と下の両方から定数倍の範囲で抑えられる、漸近的にタイトな限界 (asymptotically tight bound) を示す。

直感的な意味: 関数の増加率が、ある関数の増加率と「正確に同じ」であること。
定義: 正定数 $c_1$, $c_2$, $n_0$ が存在し、すべての $n \geq n_0$ に対して $$c_1 \cdot g(n) \leq f(n) \leq c_2 \cdot g(n)$$ が成り立つ場合、$f(n) = \Theta(g(n))$ となる。
性質: $f(n) = O(g(n))$ かつ $f(n) = \Omega(g(n))$ であることと、$f(n) = \Theta(g(n))$ は同値である。

例: 挿入ソートの最悪実行時間は $\Theta(n^2)$ である。これは、実行時間が $n^2$ の定数倍で上から抑えられ（$O(n^2)$）、かつ下からも抑えられる（$\Omega(n^2)$）ことを意味する。

$O$記法は、関数の増加率が、ある関数を超えないことを示す 漸近的上界 (asymptotic upper bound) を特徴づける。

直感的な意味: 関数の増加率が、ある関数の増加率「以下」であること。
定義: 正定数 $c$, $n_0$ が存在し、すべての $n \geq n_0$ に対して $$0 \leq f(n) \leq c \cdot g(n)$$ が成り立つ場合、$f(n) = O(g(n))$ となる。

例: $2n$ は $O(n^2)$ であるが、この限界はタイトではない。挿入ソートの実行時間は、どんな入力に対しても $O(n^2)$ であると言える。

$\Omega$記法は、関数の増加率が、ある関数の増加率以上であることを示す 漸近的下界 (asymptotic lower bound) を特徴づける。

直感的な意味: 関数の増加率が、ある関数の増加率「以上」であること。
定義: 正定数 $c$, $n_0$ が存在し、すべての $n \geq n_0$ に対して $$0 \leq c \cdot g(n) \leq f(n)$$ が成り立つ場合、$f(n) = \Omega(g(n))$ となる。

例: 挿入ソートの実行時間は、どんな入力に対しても $\Omega(n)$ であると言える。最良の場合 $\Theta(n)$ なので。

3つの漸近記法比較図

$O$記法や$\Omega$記法が示す限界が、漸近的にタイトではないことを明示するために使われる。

$f(n)$ が $g(n)$ と比較して無視できるほど小さくなることを示す。

定義: 任意の正定数 $c$ に対して、ある $n_0$ が存在し、すべての $n \geq n_0$ で $0 \leq f(n) < c \cdot g(n)$ が成立する。
極限による定義: $$\lim_{n \to \infty} \frac{f(n)}{g(n)} = 0$$
例: $2n = o(n^2)$

$f(n)$ が $g(n)$ と比較して限りなく大きくなることを示す。

定義: 任意の正定数 $c$ に対して、ある $n_0$ が存在し、すべての $n \geq n_0$ で $f(n) > c \cdot g(n)$ が成立する。
極限による定義: $$\lim_{n \to \infty} \frac{f(n)}{g(n)} = \infty$$
例: $n^2/2 = \omega(n)$

実数の比較と同様に、漸近記法にもいくつかの性質がある。

また、$\Theta$, $O$, $\Omega$, $o$, $\omega$ すべてに推移性がある。例えば $f(n) = O(g(n))$ かつ $g(n) = O(h(n))$ ならば $f(n) = O(h(n))$ である。