$\mathbb{N}\to \mathbb{R}_{\geq 0}$ という形をした関数の評価をする
liminf, limsup でオーダー記法を定義
- O: 上から抑える
- $f \in O(g)$ $\iff$ $\displaystyle \limsup_{n\to \infty} \frac{f(n)}{g(n)} < \infty$
- Ω: 下から抑える
- $f \in \Omega(g)$ $\iff$ $\displaystyle \liminf_{n\to \infty} \frac{f(n)}{g(n)} >0$
- Θ: 上と下から抑える
- $f \in \Theta(g)$ $\iff$ $\displaystyle 0 < \liminf_{n\to \infty} \frac{f(n)}{g(n)} \leq \limsup_{n\to \infty} \frac{f(n)}{g(n)} < \infty$
関数に前順序を入れてオーダー記法を定義
$f, g \colon \mathbb{N}\to \mathbb{R}_{\geq 0}$ に対して、
$f \leq g \iff \exists k >0,\ \exists n_0 \in \mathbb{N},\ \forall n \geq n_0,\ f(n) \leq k\cdot g(n)$
と定義する ($\exists k$ は 「k を十分大きく取れば」という気持ち）
この順序は前順序になっている。
オーダーは以下のように言い換えられる。
- $f\in O(g) \iff f\leq g$
- $f\in \Omega(g) \iff f\geq g$
- $f \in \Theta(g) \iff f \leq g \texttt{ かつ } g \leq f$
オーダー記法の例
- $\displaystyle f(n) = \begin{cases} n^2 & (n \texttt{ is even})\\ n^3 & (\texttt{otherwise})\end{cases}$ のとき
$f(n) = O(n^3),\ f(n) = \Omega(n^2)$
- f(n) は Θ(多項式)の形では表せない
- O は最悪ケースを記述できる
- 任意の比較ソートの最悪計算量は $\Omega(n \log n)$
- 最善を尽くしても $n \log n$ ということ
メモ