オーダー評価

概要

時間計算量を表す関数 $T(x)$ のオーダーが関数 $f(x)$ を用いて $T(x) = O(f(x))$ で表せるとは，ある自然数 $N_0$ と正の実数 $c$ があって，$N_0$ 以上の任意の自然数 $N$ について，次が成り立つとき言う: $\displaystyle |T(N)| \leq c \cdot |f(N)|$

各種定義

時間計算量関数: $T(x)$ グラフ表示グラフ非表示

オーダー表現用の関数: $f(x)$ グラフ表示グラフ非表示

関数 $c \cdot f(x)$ の定数: $c$ グラフ表示グラフ非表示

定数: $N_0$ グラフ表示グラフ非表示

関数$f(x)$による関数$T(x)$のオーダー評価の成否の簡易チェック

定数$\,c\,$の値を ???? とし，定数$\,N_0\,$の値を ???? とする．
このとき，$N_0\,$以上の任意の$\,N\,$について$\,|T(N)| \leq c \cdot |f(N)|\,$が…… 「????」
- （☝ 本当はここの不等式が成り立つかをちゃんと証明しないとダメ）
よって，$T(N) = O(f(N))$が…… 「????」

グラフ