漸近的記法

二分探索は線形探索より「速い」と言いたい。しかしどのハードウェアで？どのコンパイラ設定で？どのサイズの入力で？マシン・言語・定数倍によらない比較をするには、増加率を精密に記述する言語が必要だ — それが漸近的記法（asymptotic notation）だ。

このチェックポイントでは 3 つの中心的な記法 — $O$、$\Omega$、$\Theta$ — を基礎から定義し、絶対的な性能ではなくスケーリング挙動の形によってアルゴリズムを分類する方法を示す。

中心的なアイデア：関数を界で挟む

$T(n)$ をサイズ $n$ の入力に対してアルゴリズムが実行する操作数とする。$T(n)$ の正確な式を知ることはほとんどない — マシンや実装によって異なる定数倍に依存するためだ。一方で決定できるのは $T$ の形だ：$n$、$n^2$、$\log n$、$2^n$ のように増えるか。

漸近的記法はこの形を、少なくとも十分大きな $n$ に対して $T(n)$ を上から、下から、あるいはその両方から界で挟む（bound）より単純な関数 $g(n)$ は何かを問うことで捉える。

「十分大きな $n$ に対して」という表現が本質的だ。定数倍が支配する小さな入力についての主張ではない。$n \to \infty$ のときに何が起きるかを述べており、それが長期的なスケーラビリティを決める。

ビッグ O：上界

ビッグ O 記法（big-O notation）は関数が最終的に別の関数の定数倍で上から界された（bounded above）ことを表す。

定義。 $f(n) = O(g(n))$ であるとは、定数 $c > 0$ と $n_0 \geq 0$ が存在して

$$f(n) \leq c \cdot g(n) \quad \text{for all } n \geq n_0 \tag{1}$$

が成り立つことだ。

平易に言えば：$f$ は定数倍の差を除いて $g$ 以上には速く増えない。定数 $c$ と $n_0$ は証人として機能する — 小さい必要はなく、存在すればよい。

例。 $3n^2 + 5n + 1 = O(n^2)$ を示す。

$n \geq n_0$ のすべての $n$ に対して $3n^2 + 5n + 1 \leq c \cdot n^2$ を満たす $c$ と $n_0$ が必要だ。$n \geq 1$ のとき $5n$ と $1$ はどちらも $n^2$ 以下なので：

$$3n^2 + 5n + 1 \leq 3n^2 + 5n^2 + n^2 = 9n^2.$$

$c = 9$、$n_0 = 1$ で定義を満たす。よって $3n^2 + 5n + 1 = O(n^2)$。

一つ注意点：$3n^2 + 5n + 1 = O(n^3)$ も定義上は正しい — $n^3$ も上界だ。しかし $O(n^2)$ が最もタイトな上界であり、常にそれを報告する価値がある。

ビッグ Ω：下界

ビッグ Ω 記法（big-Ω notation）はビッグ O の鏡像だ：関数が別の関数の定数倍で下から界されることを表す。

定義。 $f(n) = \Omega(g(n))$ であるとは、定数 $c > 0$ と $n_0 \geq 0$ が存在して

$$f(n) \geq c \cdot g(n) \quad \text{for all } n \geq n_0 \tag{2}$$

が成り立つことだ。

平易に言えば：$f$ は定数倍の差を除いて $g$ 以上の速さで増える。

例。 $3n^2 + 5n + 1 = \Omega(n^2)$ を示す。

すべての $n \geq 0$ に対して $3n^2 + 5n + 1 \geq 3n^2$。$c = 3$、$n_0 = 0$ で定義を満たす。

ビッグ Ω はアルゴリズムの下界を表現するのに使われる：「この問題のアルゴリズムは最低でも $\Omega(n \log n)$ 回の比較を必要とする」とは、比較モデルで $n \log n$ より速いソートは不可能を意味する。

ビッグ Θ：タイト境界

関数が同時に $O(g)$ かつ $\Omega(g)$ のとき、$g$ の定数倍で上下両方から界される — 定数倍の差を除いて $g$ とまったく同じ速さで増える。

定義。 $f(n) = \Theta(g(n))$ であるとは

$$f(n) = O(g(n)) \quad \text{and} \quad f(n) = \Omega(g(n)) \tag{3}$$

が成り立つことだ。

同値な形として、定数 $c_1, c_2 > 0$ と $n_0 \geq 0$ が存在して

$$c_1 \cdot g(n) \leq f(n) \leq c_2 \cdot g(n) \quad \text{for all } n \geq n_0.$$

例。 先の 2 つの証明を合わせると $3n^2 + 5n + 1 = \Theta(n^2)$。

$\Theta$ 境界を持つとき、増加率が完全に定まっている。片側から界されているだけでなく両側からピン留めされている。

極限を使った記法の判定

極限に慣れているなら、実用的な近道がある。正の関数 $f$ と $g$ に対して次を計算する：

$$L = \lim_{n \to \infty} \frac{f(n)}{g(n)}.$$

$L$ の値が関係を直接教えてくれる：

$L$	関係	意味
$L = 0$	$f = o(g)$	$f$ は $g$ より厳密に遅く増える
$0 < L < \infty$	$f = \Theta(g)$	$f$ と $g$ は同じ速さで増える
$L = \infty$	$f = \omega(g)$	$f$ は $g$ より厳密に速く増える

小文字の記法 $o$（スモール o）と $\omega$（スモールオメガ）は $O$ と $\Omega$ の厳密版だ：$f = o(g)$ は比 $f/g \to 0$ を意味し、$f = O(g)$ は比が有界であることしか要求しない。$o$ の関係はすべて対応する $O$ の関係を含意するが、逆は成り立たない。

例。 $\log n = O(n)$ か？

$$\lim_{n \to \infty} \frac{\log n}{n} = 0,$$

よって $\log n = o(n)$ であり $\log n = O(n)$ が含意される。実際 $\log n$ は $n$ より厳密に遅く増える。

例。 $n^2 = O(n \log n)$ か？

$$\lim_{n \to \infty} \frac{n^2}{n \log n} = \lim_{n \to \infty} \frac{n}{\log n} = \infty,$$

よって $n^2 = \omega(n \log n)$ — 厳密に速く増える。よって $n^2 \neq O(n \log n)$。

よく見る増加率

以下に最も頻繁に登場するクラスを遅い順から速い順に並べる：

記法	名前	例
$O(1)$	定数	インデックスによる配列アクセス
$O(\log n)$	対数	二分探索
$O(n)$	線形	リストを一度スキャン
$O(n \log n)$	線形対数	マージソート
$O(n^2)$	二乗	全ペアの比較
$O(n^3)$	三乗	素朴な行列積
$O(2^n)$	指数	全部分集合の力任せ探索
$O(n!)$	階乗	全順列の力任せ探索

これらのクラスは $o$ の関係のもとで厳密な階層をなす：

$$O(1) \subsetneq O(\log n) \subsetneq O(n) \subsetneq O(n \log n) \subsetneq O(n^2) \subsetneq O(2^n) \subsetneq O(n!).$$

$O(n \log n)$ の実行時間を持つアルゴリズムは、定数倍に関わらず十分大きな入力に対して常に $O(n^2)$ のアルゴリズムより高速だ。

よくある誤解

「ビッグ O は正確な実行時間を与える。」 そうではない。$O(n^2)$ は実行時間が何らかの定数 $c$ に対して $c \cdot n^2$ で界されることを言うだけで、$c$ の大きさについては何も言わない。$10^9 \cdot n^2$ 回の操作を行うアルゴリズムも $n^2$ 回のアルゴリズムも $O(n^2)$ だ。ビッグ O は形を表し、大きさは表さない。

「ビッグ O が最小のアルゴリズムが実際には常に最速だ。」 小さな入力ではそうならない。前者の定数倍がずっと大きい場合、$O(n \log n)$ アルゴリズムは小さな $n$ では $O(n^2)$ アルゴリズムより遅いこともある。漸近解析は大きな $n$ の挙動を述べるもので、小さな入力には実測が必要だ。

「$f = O(g)$ は $f \approx g$ を意味する。」 違う。$O$ は上界を表し、近似的な等号ではない。定数関数は $O(n^{100})$ だが、それはほとんど何も教えてくれない。常に確立できる最もタイトな界を報告すること。

まとめ

• ビッグ O （$f = O(g)$）：$f$ は最終的にある定数 $c$ に対して $c \cdot g$ で上から界される — 「$f$ は $g$ 以上には速く増えない。」
• ビッグ Ω （$f = \Omega(g)$）：$f$ は最終的に $c \cdot g$ で下から界される — 「$f$ は $g$ と少なくとも同じ速さで増える。」
• ビッグ Θ （$f = \Theta(g)$）：両方の界が成り立つ — 「$f$ と $g$ は定数倍を除いて同じ速さで増える。」
• 極限 $\lim_{n \to \infty} f(n) / g(n)$ が関係を直接教える：$0$ は $o$、有限正は $\Theta$、$\infty$ は $\omega$。
• 増加率の階層（遅い順）：$O(1),\; O(\log n),\; O(n),\; O(n \log n),\; O(n^2),\; O(2^n),\; O(n!)$。
• ビッグ O は増加率の上界であり、近似でも定数倍の情報も与えない。