計算量と O 記法：アルゴリズムの速さを入力サイズの関数で測る

0. この記事の要点

• 計算量とは「入力サイズ $n$ に対して実行される基本演算の回数」であり、秒で測った実行時間そのものではありません。この抽象化によって、機種・言語・コンパイラに依存しない比較ができます。
• $f(n) = O(g(n))$ は「ある定数 $c > 0$ と $n_0$ が存在して、$n \ge n_0$ を満たすすべての $n$ で $f(n) \le c\,g(n)$」という主張です。$O(g)$ は関数の集合であり、等号は慣用的な略記にすぎません。
• 増大度には $1 \prec \log n \prec n^{\varepsilon} \prec n \prec n\log n \prec n^2 \prec 2^n \prec n!$ という階層があります。これは感覚ではなく、極限として証明できる定理です。
• 入力サイズを 2 倍にすると、$\Theta(n^2)$ のアルゴリズムは 4 倍、$\Theta(2^n)$ のアルゴリズムは「それまでの全計算量ぶん」時間が増えます。計算機を 1000 倍速くしても、$\Theta(2^n)$ で扱える $n$ は約 10 しか増えません。
• 分割統治法の漸化式 $T(n) = a\,T(n/b) + f(n)$ は、マスター定理によって機械的にオーダーが決まります。
• 「多項式時間で解けるか、指数時間しか知られていないか」という境界が、計算機科学最大の未解決問題である P≠NP 予想の中心にあります。

1. 動機：なぜ「秒」ではなく「増大度」で測るのか

二つのプログラム A と B のどちらが速いかを知りたいとします。素朴な方法は、実際に走らせて秒数を比べることです。しかしこの方法には決定的な弱点があります。測定したのは「その入力・その計算機・そのコンパイラ・そのときのキャッシュ状態」での速さであって、明日別の環境で同じ順位になる保証がないのです。

もっと悪いことに、小さな入力での測定は大きな入力での挙動をまったく予言しません。要素数 $n$ の配列を整列する二つのアルゴリズムを考えます。挿入ソートは最悪の場合およそ $n^2/2$ 回の比較を行い、マージソートはおよそ $n\log_2 n$ 回の比較を行います。$n = 10$ なら前者は 45 回、後者は 33 回で、ほとんど差がありません。ところが $n = 10^6$ では前者が $5 \times 10^{11}$ 回、後者が $2 \times 10^7$ 回となり、比は約 25000 倍に開きます。1 秒間に $10^9$ 回の基本演算をこなす計算機なら、後者は 0.02 秒、前者は 8 分以上かかります。

ここで効いているのは実装の巧拙ではなく、$n$ が増えたときに演算回数がどう増えるかという構造です。ハードウェアの改良やコードの最適化がもたらすのは、たいていの場合「定数倍の高速化」です。一方アルゴリズムの選択は、$n^2$ を $n\log n$ に変えるという、定数倍では埋まらない差をもたらします。

そこで私たちは、演算回数を $n$ の関数として捉え、定数倍と有限個の例外を無視した「増大度」だけを見ることにします。この粗さこそが、環境に依存しない普遍的な比較を可能にします。以下ではまず何を数えるのかを決め（§2）、次に増大度の比較を厳密な言葉にし（§3）、その階層を証明し（§4）、実際のスケールで何が起きるかを見ます（§5）。

2. 準備：計算モデルと計算量

2.1. 何を 1 ステップと数えるか

「基本演算の回数」を数えるには、何が基本演算なのかを先に決めなければなりません。標準的に用いられるのが一様コスト RAM モデル（uniform-cost random access machine）です。

定義 2.1（一様コスト RAM モデル）

計算機は、番地 $0, 1, 2, \ldots$ で添字づけられた記憶セルの列と、有限個のレジスタを持つとする。次の各操作を基本演算と呼び、いずれも 1 単位時間で実行されるものとする。

1. 定数、レジスタ、および番地を指定した記憶セルからの読み出しと書き込み
2. 整数・実数の加減乗除と比較
3. 条件分岐と無条件分岐

さらに、1 個の記憶セルには $O(\log n)$ ビットの語（$n$ は入力サイズ）が格納できるものとする。

最後の条件は見落とされがちですが本質的です。語長を $O(\log n)$ ビットに制限しておかないと、1 個のセルに入力全体を詰め込んで多倍長演算を 1 ステップで済ませる、という現実離れしたアルゴリズムが許されてしまいます。逆にこの制限のもとでは、$n$ 個の要素に添字を振るのに必要な $\log_2 n$ ビットはちょうど 1 語に収まり、配列の添字計算が 1 ステップで行えるという、実際の計算機に近い設定になります。

注意 2.2

一様コストモデルでは、$k$ 桁の整数どうしの乗算も 1 ステップと数えます。暗号や計算機代数のように巨大整数を扱う場面ではこの仮定は成り立たず、ビット数に比例したコストを課す対数コストモデルを使います。どのモデルで測っているかを明示しないと、計算量の主張は意味を持ちません。

2.2. 時間計算量と空間計算量

定義 2.3（最悪時間計算量・空間計算量）

アルゴリズム $A$ と入力 $x$ に対し、$A$ が $x$ 上で停止するまでに実行する基本演算の回数を $t_A(x)$、書き込みまたは読み出しを行った記憶セルの総数を $s_A(x)$ と書く。入力 $x$ のサイズ $|x|$ を、$x$ を表現するのに要する語数と定める。このとき

$$T_A(n) = \max_{|x| = n} t_A(x), \qquad S_A(n) = \max_{|x| = n} s_A(x)$$

をそれぞれ $A$ の最悪時間計算量、最悪空間計算量と呼ぶ。

$\max$ を取っている点に注意してください。時間計算量は「サイズ $n$ の入力のうち最も不利なもの」に対する値です。したがって $T_A(n)$ は、$n$ さえ決まればどんな入力でも保証される上限になります。

時間と空間は独立ではありません。次の命題は、空間の方が時間より「安い」資源であることを述べています。

命題 2.4（空間は時間で抑えられる）

アルゴリズム $A$ が、1 回の基本演算で高々 $\kappa$ 個の記憶セルにアクセスするとする（定義 2.1 のモデルではつねに $\kappa \le 3$ と取れる）。このとき、すべての $n$ に対して

$$S_A(n) \le n + \kappa\, T_A(n)$$

が成り立つ。とくに $T_A(n) \ge n$ ならば $S_A(n) = O(T_A(n))$ である。

証明（命題 2.4）

サイズ $n$ の入力 $x$ を固定します。$A$ がアクセスするセルは、入力を格納した $n$ 個のセルか、実行中にアクセスされたセルのいずれかです。仮定より 1 ステップでアクセスされるセルは高々 $\kappa$ 個なので、$t_A(x)$ ステップ全体でアクセスされるセルは高々 $\kappa\,t_A(x)$ 個です。よって $s_A(x) \le n + \kappa\, t_A(x) \le n + \kappa\,T_A(n)$ となり、$|x| = n$ について最大を取れば第 1 の主張を得ます。

$T_A(n) \ge n$ のときは $n + \kappa T_A(n) \le (1+\kappa) T_A(n)$ なので、定義 3.1 の定数を $c = 1 + \kappa$、$n_0 = 1$ と取れば $S_A(n) = O(T_A(n))$ です。

∎

逆は成り立ちません。空間 $O(1)$ で時間 $\Theta(2^n)$ のアルゴリズムはいくらでも作れます。「メモリは使い回せるが、時間は使い回せない」という非対称性がここに現れています。

2.3. 数え上げの実例

例 2.5（挿入ソートの比較回数を最後まで数える）

長さ $n$ の配列を昇順に並べ替える挿入ソートを考えます。

def insertion_sort(a):
    for i in range(1, len(a)):
        key = a[i]
        j = i - 1
        while j >= 0 and a[j] > key:
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = key
    return a

要素どうしの比較 a[j] > key が何回評価されるかを数えます。外側のループ変数 $i$ を固定すると、内側の while は $j = i-1, i-2, \ldots$ と減らしながら回ります。j >= 0 が偽になった時点で短絡評価により比較は行われないので、比較回数は $j$ が $0$ 以上である間の回数、すなわち高々 $i$ 回です。この上限は、入力が狭義単調減少列 $a = (n, n-1, \ldots, 1)$ のときちょうど達成されます。実際このとき key はつねに $a[0..i-1]$ のどの要素よりも小さいので、while は $j = -1$ になるまで回り、比較は $j = i-1, \ldots, 0$ の $i$ 回です。したがって最悪比較回数は

$$\sum_{i=1}^{n-1} i = \frac{n(n-1)}{2}$$

です。同じ入力に対する代入回数は、$i$ ごとに $a[j+1] = a[j]$ が $i$ 回、key の読み書きが 2 回なので $\sum_{i=1}^{n-1}(i+2) = \frac{n(n-1)}{2} + 2(n-1)$ 回です。基本演算の総数はループ制御を含めても定数倍しか変わらないので、$T(n) = \Theta(n^2)$ となります（$\Theta$ の意味は 定義 3.1 で与えます）。

一方、使う記憶領域は入力の配列に加えて i, j, key の 3 語だけなので、追加空間は $\Theta(1)$ です。

注意 2.6

最悪計算量のほかに、入力の確率分布を仮定して期待値を取る平均計算量、最も有利な入力での最良計算量も定義できます。挿入ソート（例 2.5） の最良計算量は、すでに整列済みの入力に対して比較 $n-1$ 回、すなわち $\Theta(n)$ です。クイックソートは最悪 $\Theta(n^2)$ でありながら、ランダムな順列上の平均は $\Theta(n\log n)$ であり（定理 5.5［ソートアルゴリズム］）、実用上はこの平均が効きます。詳しくは ソートアルゴリズム を参照してください。断りがない限り、本記事の計算量はすべて最悪計算量です。

3. O 記法・Ω 記法・Θ 記法

3.1. 定義

以下、$f, g$ は $\mathbb{N} = \{1, 2, \ldots\}$ 上で定義された非負実数値関数とします。

定義 3.1（O 記法・Ω 記法・Θ 記法）

関数 $g$ に対し、関数の集合 $O(g)$, $\Omega(g)$, $\Theta(g)$ を次で定める。

$$\begin{aligned} O(g) &= \{\, f \;:\; \exists c > 0,\ \exists n_0 \in \mathbb{N},\ \forall n \ge n_0,\ f(n) \le c\,g(n) \,\} \\ \Omega(g) &= \{\, f \;:\; \exists c > 0,\ \exists n_0 \in \mathbb{N},\ \forall n \ge n_0,\ f(n) \ge c\,g(n) \,\} \\ \Theta(g) &= O(g) \cap \Omega(g) \end{aligned}$$

$f \in O(g)$ を慣用的に $f(n) = O(g(n))$ とも書き、「$f$ は高々 $g$ のオーダーである」と読む。

定義の量化子の順序が要です。$c$ と $n_0$ は $n$ より先に選ばれます。つまり「$n$ ごとに都合のよい $c$ を選ぶ」ことは許されません。この順序を破ると、任意の $f, g$（$g > 0$）について $f \in O(g)$ が成り立ってしまい、記法は無意味になります。

flowchart LR
A["定数 c と n0 を先に選ぶ"] --> B["以後どんな n でも"] --> C["n が n0 以上なら f(n) は c·g(n) 以下"]

O 記法の定義が主張していること

$o$ 記法と $\omega$ 記法は、量化子を一つ強めたものです。

定義 3.2（o 記法・ω 記法）

$$\begin{aligned} o(g) &= \{\, f \;:\; \forall c > 0,\ \exists n_0 \in \mathbb{N},\ \forall n \ge n_0,\ f(n) \le c\,g(n) \,\} \\ \omega(g) &= \{\, f \;:\; \forall c > 0,\ \exists n_0 \in \mathbb{N},\ \forall n \ge n_0,\ f(n) \ge c\,g(n) \,\} \end{aligned}$$

$f \in o(g)$ のとき「$f$ は $g$ より真に小さいオーダーである」と読む。

$O$ では「ある $c$ について」だった箇所が $o$ では「すべての $c$ について」に変わっています。$c$ をいくらでも小さく取れるということは、$f/g$ が $0$ に近づくということです。これを正確にしたのが次の命題です。

3.2. 判定法と計算則

命題 3.3（極限による判定法）

$g(n) > 0$ が十分大きなすべての $n$ で成り立つとし、極限 $L = \lim_{n \to \infty} f(n)/g(n)$ が（$+\infty$ を含めて）存在するとする。このとき

1. $0 \le L < \infty$ ならば $f \in O(g)$。
2. $0 < L < \infty$ ならば $f \in \Theta(g)$。
3. $L = 0$ ならば $f \in o(g)$。
4. $L = \infty$ ならば $f \in \omega(g)$、かつ $g \in o(f)$。

証明（命題 3.3）

1. $L < \infty$ なので、収束の定義で $\varepsilon = 1$ と取ると、ある $n_1$ が存在して $n \ge n_1$ のとき $f(n)/g(n) < L + 1$ です。両辺に $g(n) > 0$ を掛けて $f(n) \le (L+1)\,g(n)$ を得ます。定義 3.1 で $c = L+1 > 0$、$n_0 = n_1$ と取ればよいので $f \in O(g)$ です。

2. さらに $L > 0$ とします。$\varepsilon = L/2 > 0$ と取ると、ある $n_2$ が存在して $n \ge n_2$ のとき $f(n)/g(n) > L - L/2 = L/2$、すなわち $f(n) \ge (L/2)\,g(n)$ です。よって $c = L/2$、$n_0 = n_2$ で $f \in \Omega(g)$ となり、1 と合わせて $f \in \Theta(g)$ です。

3. $L = 0$ とします。任意に $c > 0$ を与えると、収束の定義で $\varepsilon = c$ と取れば、ある $n_0$ が存在して $n \ge n_0$ のとき $f(n)/g(n) < c$、すなわち $f(n) \le c\,g(n)$ です。$c$ は任意だったので 定義 3.2 により $f \in o(g)$ です。

4. $L = \infty$ とします。任意の $c > 0$ に対し、発散の定義から、ある $n_0$ が存在して $n \ge n_0$ のとき $f(n)/g(n) > c$、すなわち $f(n) \ge c\,g(n)$ です。よって $f \in \omega(g)$ です。同じ不等式を $g(n) \le (1/c) f(n)$ と読み替え、$c' = 1/c$ が $c$ とともに任意の正数を動くことに注意すれば $g \in o(f)$ を得ます。

∎

極限が存在しない場合はこの判定法は使えません。それでも $O$ 記法自体は意味を持ちます（演習 8.4 を参照）。

命題 3.4（O 記法の計算則）

$f, f_1, f_2, g, g_1, g_2, h$ を非負実数値関数とする。次が成り立つ。

1. （反射律）$f \in O(f)$。
2. （推移律）$f \in O(g)$ かつ $g \in O(h)$ ならば $f \in O(h)$。
3. （定数倍）$\lambda > 0$ かつ $f \in O(g)$ ならば $\lambda f \in O(g)$。
4. （和）$f_1 \in O(g_1)$ かつ $f_2 \in O(g_2)$ ならば $f_1 + f_2 \in O(\max(g_1, g_2))$。ここで $\max(g_1,g_2)$ は各点ごとの最大値を取る関数である。
5. （積）$f_1 \in O(g_1)$ かつ $f_2 \in O(g_2)$ ならば $f_1 f_2 \in O(g_1 g_2)$。

証明（命題 3.4）

1. $c = 1$、$n_0 = 1$ とすれば、すべての $n \ge 1$ で $f(n) \le 1 \cdot f(n)$ です。

2. 仮定より、$c_1 > 0, n_1$ があって $n \ge n_1$ で $f(n) \le c_1 g(n)$、また $c_2 > 0, n_2$ があって $n \ge n_2$ で $g(n) \le c_2 h(n)$ です。$n \ge \max(n_1, n_2)$ のとき、第 1 の不等式に第 2 の不等式を代入して $f(n) \le c_1 g(n) \le c_1 c_2 h(n)$ を得ます（$c_1 > 0$ なので不等号の向きは保たれます）。$c = c_1 c_2$、$n_0 = \max(n_1,n_2)$ と取ればよいのです。

3. $n \ge n_0$ で $f(n) \le c\,g(n)$ なら、両辺に $\lambda > 0$ を掛けて $\lambda f(n) \le \lambda c\,g(n)$ です。定数を $\lambda c$ に取り替えます。

4. $n \ge \max(n_1,n_2)$ のとき、$g_i \le \max(g_1,g_2)$ を使って

$$f_1(n) + f_2(n) \le c_1 g_1(n) + c_2 g_2(n) \le (c_1 + c_2)\max(g_1(n), g_2(n))$$

です。定数を $c_1 + c_2$ と取ります。

5. $n \ge \max(n_1,n_2)$ のとき、$f_1, f_2, g_1, g_2 \ge 0$ なので不等式どうしを掛けてよく、$f_1(n) f_2(n) \le c_1 c_2\, g_1(n) g_2(n)$ です。

∎

計算則 4 は実務でいちばん使う道具です。「前処理に $O(n\log n)$、本体に $O(n^2)$ かかるアルゴリズムは全体で $O(n^2)$」という日常的な推論は、この規則の適用にほかなりません。

命題 3.5（多項式のオーダー）

$d \ge 0$ を整数、$a_0, \ldots, a_d$ を実数、$a_d > 0$ とし、$p(n) = \sum_{i=0}^{d} a_i n^i$ が十分大きなすべての $n$ で非負であるとする。このとき $p \in \Theta(n^d)$ である。

証明（命題 3.5）

まず上からの評価です。$A = \sum_{i=0}^{d} |a_i|$ とおくと、$n \ge 1$ のとき $n^i \le n^d$（$0 \le i \le d$）なので

$$p(n) \le \sum_{i=0}^{d} |a_i|\, n^i \le \Big(\sum_{i=0}^{d} |a_i|\Big) n^d = A\,n^d .$$

よって $c = A$、$n_0 = 1$ として $p \in O(n^d)$ です。

次に下からの評価です。$B = \sum_{i=0}^{d-1} |a_i|$ とおきます（$d = 0$ のときは $B = 0$ で、以下は自明に成り立ちます）。$n \ge 1$ で

$$p(n) = n^d\Big(a_d + \sum_{i=0}^{d-1} a_i n^{i-d}\Big), \qquad \Big|\sum_{i=0}^{d-1} a_i n^{i-d}\Big| \le \sum_{i=0}^{d-1} |a_i|\, n^{i-d} \le \frac{B}{n}$$

が成り立ちます。最後の不等号では、$i \le d-1$ より $n^{i-d} \le n^{-1}$ を使いました。そこで $n_0 = \lceil 2B/a_d \rceil + 1$ と取ると、$n \ge n_0$ のとき $B/n \le a_d/2$ なので

$$p(n) \ge n^d\Big(a_d - \frac{a_d}{2}\Big) = \frac{a_d}{2}\, n^d$$

です。$c = a_d/2 > 0$ として $p \in \Omega(n^d)$ を得ます。両者を合わせて $p \in \Theta(n^d)$ です。

∎

3.3. 記法の落とし穴

注意 3.6

$f(n) = O(g(n))$ の等号は対称ではありません。$n = O(n^2)$ は正しい主張ですが、$O(n^2) = n$ とは書きません。この等号は左から右への「$\in$」または「$\subseteq$」だと思ってください。式の途中に現れる $O(\cdot)$ は「その条件を満たす何らかの関数」を表します。たとえば

$$\sum_{i=1}^{n} i = \frac{n^2}{2} + O(n)$$

は「左辺と $n^2/2$ の差が $O(n)$ に属する関数である」という意味です。この慣用は Knuth によって整理されました（参考文献 [2]）。

注意 3.7

$O$ 記法の中では対数の底を書かなくてかまいません。底の変換公式 $\log_a n = \log_b n / \log_b a$ から、$\log_a n$ と $\log_b n$ は正の定数倍しか違わないため、$\Theta(\log_a n) = \Theta(\log_b n)$ が成り立つからです。ただし $2^{\log_2 n} = n$ と $2^{\log_{10} n} = n^{0.301\ldots}$ のように、指数の肩に載せると底の違いは定数倍では済みません。$O$ の中の対数の底を省けるのは、対数が積の因子として現れているときだけです。

注意

$O$ 記法は定数因子を隠します。$\Theta(n\log n)$ のアルゴリズムでも定数が $1000$ なら、定数 $1$ の $\Theta(n^2)$ アルゴリズムに $n \le 10^4$ 程度までは負けます。実際、多くの標準ライブラリのソートは、要素数が数十個以下の部分配列では挿入ソートに切り替えます。漸近的な優劣と、目の前の $n$ での優劣は別の問題です。

4. 増大度の階層

「$\log n$ は $n$ よりずっと小さい」「指数関数は多項式よりずっと大きい」という感覚は、次の定理として厳密に述べられます。まず基本となる補題を証明します。

補題 4.1（指数は多項式に勝つ）

$c > 1$ と $k \ge 0$ を実数とする。このとき実変数の極限として

$$\lim_{x \to \infty} \frac{x^k}{c^{\,x}} = 0$$

が成り立つ。

証明（補題 4.1）

まず $x$ が自然数 $n$ を動く場合を示します。$c > 1$ より $h = c - 1 > 0$ と書けます。$m = \lceil k \rceil + 1$ とおくと $m > k$ です。二項定理から、$n \ge m$ のとき

$$c^{\,n} = (1+h)^n \ge \binom{n}{m} h^m = \frac{n(n-1)\cdots(n-m+1)}{m!}\,h^m \ge \frac{(n-m+1)^m}{m!}\,h^m$$

です（各因子 $n, n-1, \ldots, n-m+1$ が最小の $n-m+1$ 以上であることを使いました）。さらに $n \ge 2m$ なら $n - m + 1 > n - m \ge n/2$ なので

$$\frac{n^k}{c^{\,n}} \le \frac{m!\; n^k}{h^m (n/2)^m} = \frac{m!\,2^m}{h^m}\; n^{\,k-m} .$$

$m > k$ より指数 $k - m$ は負であり、右辺は $n \to \infty$ で $0$ に収束します。$n^k/c^n \ge 0$ なので、はさみうちにより $\lim_{n\to\infty} n^k/c^n = 0$ です。

次に実変数の場合です。$x \ge 1$ に対し $n = \lfloor x \rfloor + 1$ とおくと $x \le n$ かつ $n - 1 \le x$ なので、$k \ge 0$ と $c > 1$ より

$$\frac{x^k}{c^{\,x}} \le \frac{n^k}{c^{\,n-1}} = c\cdot\frac{n^k}{c^{\,n}} .$$

$x \to \infty$ のとき $n \to \infty$ であり、右辺は前段より $0$ に収束します。したがって $\lim_{x\to\infty} x^k/c^x = 0$ です。

∎

定理 4.2（増大度の階層）

$a > 0$, $\varepsilon > 0$, $k \ge 0$, $c > 1$ を任意の実数とする。このとき

$$(\log_2 n)^a \in o(n^{\varepsilon}), \qquad n^k \in o(c^{\,n}), \qquad c^{\,n} \in o(n!)$$

が成り立つ。とくに $\varepsilon = 1$、$a = 1$、$c = 2$ と取れば、$\log_2 n$、$n$、$2^n$、$n!$ はこの順に真に大きなオーダーである。

証明（定理 4.2）

第 1 の主張。 $t = \log_2 n$ とおくと $n = 2^t$ であり、$n \to \infty$ のとき $t \to \infty$ です。このとき

$$\frac{(\log_2 n)^a}{n^{\varepsilon}} = \frac{t^a}{2^{\varepsilon t}} = \frac{t^a}{(2^{\varepsilon})^{t}} .$$

$\varepsilon > 0$ より $2^{\varepsilon} > 1$ なので、補題 4.1 を $c = 2^{\varepsilon}$、$k = a$、$x = t$ として適用すると、この比は $0$ に収束します。命題 3.3 の 3 より $(\log_2 n)^a \in o(n^{\varepsilon})$ です。

第 2 の主張。 補題 4.1 をそのまま $x = n$ に適用すれば $n^k/c^n \to 0$ であり、再び 命題 3.3 の 3 から $n^k \in o(c^n)$ です。

第 3 の主張。 $m = \lceil 2c \rceil$ とおきます。$n > m$ のとき

$$\frac{c^{\,n}}{n!} = \frac{c^{\,m}}{m!}\prod_{j=m+1}^{n} \frac{c}{j}$$

と分解できます。$j \ge m+1 > 2c$ より各因子は $c/j < 1/2$ なので、積は $(1/2)^{\,n-m}$ 以下です。よって

$$0 \le \frac{c^{\,n}}{n!} \le \frac{c^{\,m}}{m!}\left(\frac{1}{2}\right)^{n-m}$$

であり、右辺は $n \to \infty$ で $0$ に収束します（$c$ と $m$ は $n$ に依存しない定数です）。はさみうちにより $c^n/n! \to 0$ となり、$c^n \in o(n!)$ です。

∎

第 1 の主張は、どんなに小さな $\varepsilon > 0$ を取っても、$(\log n)^{100}$ より $n^{\varepsilon}$ のほうが最終的には大きいと言っています。対数はそれほど遅く増えます。第 2 の主張は、$n^{1000}$ より $1.001^n$ のほうが最終的には大きいと言っています。指数はそれほど速く増えます。この二つが、次節で見る劇的な差の源です。

代表的な増大度（縦軸は 100 で打ち切り）

5. 主要な計算量クラスを読む

5.1. 2 倍則

各クラスの性格をつかむ最も手軽な方法は、「入力サイズを 2 倍にしたら実行時間がどうなるか」を見ることです。

命題 5.1（入力を 2 倍にしたときの比）

$\alpha > 0$、$\beta$ を定数、$k > 0$ を実数とする。次が成り立つ。

1. $T(n) = \alpha$ ならば $T(2n)/T(n) = 1$。
2. $T(n) = \alpha \log_2 n + \beta$ ならば $T(2n) - T(n) = \alpha$（比ではなく差が一定）。
3. $T(n) = \alpha n^{k}$ ならば $T(2n)/T(n) = 2^{k}$。
4. $T(n) = \alpha n \log_2 n$ ならば $T(2n)/T(n) = 2\left(1 + \dfrac{1}{\log_2 n}\right)$ であり、$n \to \infty$ で $2$ に収束する。
5. $T(n) = \alpha\, 2^{n}$ ならば $T(2n)/T(n) = 2^{n}$。

証明（命題 5.1）

いずれも代入して計算します。

1. $T(2n)/T(n) = \alpha/\alpha = 1$。
2. $T(2n) - T(n) = \alpha(\log_2 2n - \log_2 n) + (\beta - \beta) = \alpha \log_2 2 = \alpha$。
3. $T(2n)/T(n) = \alpha (2n)^k / (\alpha n^k) = 2^k n^k / n^k = 2^k$。
4. $T(2n)/T(n) = \dfrac{\alpha \cdot 2n \log_2 2n}{\alpha\, n \log_2 n} = 2\cdot\dfrac{\log_2 n + 1}{\log_2 n} = 2\left(1 + \dfrac{1}{\log_2 n}\right)$。$n \to \infty$ で $1/\log_2 n \to 0$ なので比は $2$ に収束します。
5. $T(2n)/T(n) = \alpha 2^{2n}/(\alpha 2^{n}) = 2^{2n-n} = 2^{n}$。

∎

主張 5 が指数時間の恐ろしさを端的に表しています。$n = 40$ の問題を解いたあと $n = 80$ に進むと、時間は $2^{40} \approx 1.1\times 10^{12}$ 倍になります。

注意 5.2

命題 5.1 は「ちょうど」その形の関数についての主張であり、$T \in \Theta(n)$ という条件だけからは $T(2n)/T(n) \to 2$ は導けません。反例として $T(n) = n\,(2 + \sin n)$ を取ると、$1 \le 2+\sin n \le 3$ より $T \in \Theta(n)$ ですが、$T(2n)/T(n) = 2(2+\sin 2n)/(2+\sin n)$ は $2/3$ 倍から $6$ 倍のあいだを振動し、収束しません。$\Theta$ は定数倍を捨てているので、比の極限までは決めないのです。

5.2. 数値で見る

例 5.3（実際の演算回数と実行時間）

1 秒間に $10^9$ 回の基本演算を行う計算機を仮定します。演算回数は次のとおりです。

$n$	$\log_2 n$	$n$	$n\log_2 n$	$n^2$	$2^n$
$10$	$3.3$	$10$	$33$	$10^{2}$	$1.0\times10^{3}$
$100$	$6.6$	$100$	$664$	$10^{4}$	$1.3\times10^{30}$
$10^{3}$	$10.0$	$10^{3}$	$1.0\times10^{4}$	$10^{6}$	天文学的
$10^{6}$	$19.9$	$10^{6}$	$2.0\times10^{7}$	$10^{12}$	天文学的
$10^{9}$	$29.9$	$10^{9}$	$3.0\times10^{10}$	$10^{18}$	天文学的

これを時間に直します。

$T(n)$	$n = 10^{6}$	$n = 10^{9}$
$n$	$0.001$ 秒	$1$ 秒
$n\log_2 n$	$0.02$ 秒	$30$ 秒
$n^2$	$17$ 分	$32$ 年

$n\log_2 n$ の欄を見てください。$n = 10^9$ でも $\log_2 n$ は $30$ にすぎないので、$n\log n$ は $n$ の高々 30 倍です。現実的な入力サイズの範囲では、$\Theta(n\log n)$ は $\Theta(n)$ とほとんど変わりません。 これが、比較ソートや高速フーリエ変換のような $\Theta(n\log n)$ アルゴリズムが「実質的に線形」と扱われる理由です。同じことは $\Theta(\log n)$ にも当てはまります。$n$ が $10$ から $10^9$ へと 1 億倍になっても、$\log_2 n$ は $3.3$ から $29.9$ へ 9 倍にしかなりません。二分探索が要素数によらず一瞬で終わるように見えるのはこのためです（定理 3.3［探索アルゴリズム］、探索アルゴリズム を参照）。

指数の側も見ておきます。$2^{50} \approx 1.1\times10^{15}$ 回は約 13 日、$2^{100} \approx 1.3\times10^{30}$ 回は約 $4\times10^{13}$ 年で、これは宇宙の年齢（約 $1.4\times10^{10}$ 年）のおよそ 2900 倍です。階乗はさらに速く、$20! \approx 2.4\times10^{18}$ は約 77 年に相当します。

5.3. 速い計算機では救えない

指数時間の本質的な困難は、次の比較で最もはっきりします。

例 5.4（計算機が 1000 倍速くなったら）

1 秒間に扱える最大の $n$ を、$10^9$ 演算/秒の計算機と $10^{12}$ 演算/秒の計算機で比べます。

$T(n)$	$10^{9}$ 演算/秒	$10^{12}$ 演算/秒	変化
$n$	$10^{9}$	$10^{12}$	$1000$ 倍
$n\log_2 n$	$4.0\times10^{7}$	$2.9\times10^{10}$	約 $730$ 倍
$n^2$	$3.2\times10^{4}$	$10^{6}$	約 $31.6$ 倍
$n^3$	$10^{3}$	$10^{4}$	$10$ 倍
$2^n$	$29$	$39$	$+10$

最下行を確かめます。$2^{n} = t$ を解くと $n = \log_2 t$ なので、$t$ が $1000$ 倍になったときの $n$ の増加は $\log_2 1000 = 9.97$、つまり約 10 です。これは計算機の速度によらない一般的な事実であり、$T(n) = \alpha\,c^{n}$ の形なら増加分は $\log_c 1000$ です。

$n^2$ の行では $\sqrt{1000} = 31.6$ 倍、$n^3$ の行では $1000^{1/3} = 10$ 倍というように、指数の逆数乗だけ改善します。一般に $T(n) = \alpha n^{k}$ なら、計算機が $s$ 倍速くなったとき扱える $n$ は $s^{1/k}$ 倍になります。

結論は明快です。多項式時間なら計算機の進歩が効きますが、指数時間ではほとんど効きません。 指数時間の壁を破るには、より良いアルゴリズムを見つけるしかないのです。

例 5.5（総当りから動的計画法へ）

$n$ 個の正整数 $w_1, \ldots, w_n$ と目標値 $W$ が与えられ、和がちょうど $W$ になる部分集合があるかを判定する問題（部分和問題）を考えます。すべての部分集合を列挙する総当りは $2^n$ 通りを調べるので $\Theta(2^n \cdot n)$ です。$n = 40$ なら $2^{40} \times 40 \approx 4.4\times10^{13}$ 演算、$10^9$ 演算/秒の計算機で約 12 時間かかります。

一方、$b[i][w]$ を「最初の $i$ 個から和 $w$ が作れるか」とする表を埋める動的計画法は $\Theta(nW)$ で済みます。$n = 40$、$W = 10^4$ なら $4\times10^5$ 演算、$0.0004$ 秒です。3000 万倍以上の高速化ですが、これは計算機を替えたのではなく、同じ部分和を何度も数え直すのをやめただけです（同じ形の漸化式とその計算量は 系 6.4［動的計画法］ で扱います。動的計画法 を参照）。

なお $\Theta(nW)$ は入力サイズの多項式ではありません。$W$ を表すのに必要なのは $\log_2 W$ ビットなので、$W$ は入力サイズについて指数的に大きくなりえます。このような計算量を擬多項式時間と呼びます。

5.4. データ構造の計算量

同じ操作でも、データ構造を変えれば計算量が変わります。代表的な構造の最悪計算量を並べます（$n$ は格納された要素数）。

操作	未整列の配列	整列済み配列	連結リスト	平衡二分探索木	ハッシュ表
値の検索	$\Theta(n)$	$\Theta(\log n)$	$\Theta(n)$	$\Theta(\log n)$	平均 $\Theta(1)$ / 最悪 $\Theta(n)$
挿入	$\Theta(1)$（末尾）	$\Theta(n)$	$\Theta(1)$（位置既知）	$\Theta(\log n)$	平均 $\Theta(1)$
削除	$\Theta(n)$（検索込み）	$\Theta(n)$	$\Theta(1)$（位置既知）	$\Theta(\log n)$	平均 $\Theta(1)$
最小値の取得	$\Theta(n)$	$\Theta(1)$	$\Theta(n)$	$\Theta(\log n)$	$\Theta(n)$

万能な構造はありません。整列済み配列は検索が速い代わりに挿入で全体をずらす必要があり、連結リストは挿入が速い代わりに $k$ 番目の要素に到達するのに $\Theta(k)$ かかります（命題 4.2［基本的なデータ構造］）。何を速くしたいかを決めてから構造を選ぶことになります。各構造の定義と、これらの計算量の証明は 基本的なデータ構造 で扱います。

注意 5.6

表の「未整列の配列への末尾挿入 $\Theta(1)$」は、容量が足りているときの話です。容量が尽きたら新しい領域を確保して全要素をコピーするので、その回だけは $\Theta(n)$ かかります。しかし容量を尽きるたびに 2 倍にする戦略を取ると、容量 $1$ から始めて $n$ 回挿入するまでにコピーが起きるのは要素数が $1, 2, 4, \ldots, 2^{k}$（$2^{k} < n$）のときだけで、総コピー回数は

$$1 + 2 + 4 + \cdots + 2^{k} = 2^{k+1} - 1 < 2n$$

です。$n$ 回の挿入の総コストが $O(n)$ なので、1 回あたりの平均は $O(1)$ です。このように操作列全体で均した計算量を償却計算量と呼びます（この評価を定理の形で述べたものが 定理 3.3［基本的なデータ構造］ です）。個々の操作の最悪計算量とは別の概念なので、区別してください。

6. 分割統治：漸化式からオーダーを出す

再帰的なアルゴリズムの計算量は漸化式として現れます。マージソートなら、長さ $n$ の配列を半分ずつに分けて再帰し、$\Theta(n)$ 時間で併合するので $T(n) = 2\,T(n/2) + \Theta(n)$ です（定理 4.2［ソートアルゴリズム］）。この形の漸化式は、次の定理で一気に解けます。

定理 6.1（マスター定理）

$a \ge 1$、$b > 1$ を実数、$d > 0$ を定数とし、$f$ を $b$ のべき乗の上で定義された正の値をとる関数とする。関数 $T$ が

$$T(1) = d, \qquad T(n) = a\,T(n/b) + f(n) \quad (n = b^{k},\ k \ge 1)$$

を満たすとする。$n$ は $b$ のべき乗の上を動くものとして、次が成り立つ。

1. ある $\varepsilon > 0$ について $f(n) = O\!\left(n^{\log_b a - \varepsilon}\right)$ ならば、$T(n) = \Theta\!\left(n^{\log_b a}\right)$。
2. $f(n) = \Theta\!\left(n^{\log_b a}\right)$ ならば、$T(n) = \Theta\!\left(n^{\log_b a}\log n\right)$。
3. ある $\varepsilon > 0$ について $f(n) = \Omega\!\left(n^{\log_b a + \varepsilon}\right)$ であり、かつある定数 $0 < c < 1$ が存在してすべての $k \ge 1$ で $a\,f(b^{k-1}) \le c\,f(b^{k})$（正則条件）が成り立つならば、$T(n) = \Theta(f(n))$。

証明（定理 6.1）

$n = b^{k}$ とします。漸化式を $k$ 回展開すると

$$T(n) = a^{k} T(1) + \sum_{j=0}^{k-1} a^{j} f\!\left(\frac{n}{b^{j}}\right)$$

です（$k$ についての帰納法：$k=0$ では両辺 $T(1)$ で一致し、$k$ で成り立つとして $T(b^{k+1}) = aT(b^{k}) + f(b^{k+1})$ に代入すれば $k+1$ でも成り立ちます）。ここで

$$a^{k} = a^{\log_b n} = \left(b^{\log_b a}\right)^{\log_b n} = \left(b^{\log_b n}\right)^{\log_b a} = n^{\log_b a}$$

なので、第 1 項は $d\,n^{\log_b a}$ です。$f > 0$ より、つねに $T(n) \ge d\,n^{\log_b a}$ が成り立ちます。あとは和 $\Sigma = \sum_{j=0}^{k-1} a^{j} f(n/b^{j})$ を評価します。

場合 1。 仮定より、ある $C > 0$ があって $f(m) \le C\,m^{\log_b a - \varepsilon}$（$m$ は十分大きい $b$ のべき乗）です。すると

$$\Sigma \le C \sum_{j=0}^{k-1} a^{j}\left(\frac{n}{b^{j}}\right)^{\log_b a - \varepsilon} = C\,n^{\log_b a - \varepsilon} \sum_{j=0}^{k-1} a^{j}\, b^{-j(\log_b a - \varepsilon)} .$$

ここで $b^{-j\log_b a} = a^{-j}$ なので $a^{j} b^{-j(\log_b a - \varepsilon)} = (b^{\varepsilon})^{j}$ となり、等比級数の公式から

$$\sum_{j=0}^{k-1} (b^{\varepsilon})^{j} = \frac{b^{\varepsilon k} - 1}{b^{\varepsilon} - 1} < \frac{n^{\varepsilon}}{b^{\varepsilon} - 1}$$

です（$b^{\varepsilon k} = (b^{k})^{\varepsilon} = n^{\varepsilon}$ を使いました）。よって $\Sigma < \dfrac{C}{b^{\varepsilon}-1}\,n^{\log_b a}$ であり、$T(n) = O(n^{\log_b a})$ です。下からの評価は上で述べた $T(n) \ge d\,n^{\log_b a}$ なので、合わせて $T(n) = \Theta(n^{\log_b a})$ を得ます。

場合 2。 仮定より $c_1 m^{\log_b a} \le f(m) \le c_2 m^{\log_b a}$ となる $c_1, c_2 > 0$ があります。$a^{j}(n/b^{j})^{\log_b a} = a^{j} n^{\log_b a} a^{-j} = n^{\log_b a}$ なので、和の各項は $c_1 n^{\log_b a}$ 以上 $c_2 n^{\log_b a}$ 以下です。項数は $k = \log_b n$ なので

$$c_1\,n^{\log_b a} \log_b n \le \Sigma \le c_2\,n^{\log_b a}\log_b n$$

です。$\log_b n$ と $\log n$ は正の定数倍しか違わない（注意 3.7）ので、$\Sigma = \Theta(n^{\log_b a}\log n)$ です。第 1 項 $d\,n^{\log_b a}$ はこれに吸収されるので $T(n) = \Theta(n^{\log_b a}\log n)$ です。

場合 3。 正則条件から、$j$ についての帰納法で $a^{j} f(n/b^{j}) \le c^{\,j} f(n)$ が示せます。実際 $j = 0$ では等号です。$j$ で成り立つとすると、正則条件を $n/b^{j}$ に適用して $a f(n/b^{j+1}) \le c f(n/b^{j})$ なので

$$a^{j+1} f(n/b^{j+1}) = a^{j}\cdot a f(n/b^{j+1}) \le a^{j}\, c\, f(n/b^{j}) \le c\cdot c^{\,j} f(n) = c^{\,j+1} f(n)$$

となります。したがって $0 < c < 1$ より

$$\Sigma \le f(n) \sum_{j=0}^{k-1} c^{\,j} < \frac{f(n)}{1-c} .$$

また仮定 $f(n) = \Omega(n^{\log_b a + \varepsilon})$ から、ある $c_3 > 0$ と十分大きな $n$ で $n^{\log_b a} \le \dfrac{f(n)}{c_3\,n^{\varepsilon}} \le \dfrac{f(n)}{c_3}$ が成り立つので、第 1 項も $O(f(n))$ です。よって $T(n) = O(f(n))$ です。一方、展開式で $j = 0$ の項を取れば $T(n) \ge f(n)$ なので $T(n) = \Omega(f(n))$ であり、$T(n) = \Theta(f(n))$ を得ます。

∎

注意 6.2

実際のアルゴリズムでは $n/b$ が整数とは限らず、漸化式は $T(n) = a\,T(\lfloor n/b\rfloor) + f(n)$ の形になります。この床関数つきの漸化式でも 定理 6.1 と同じ結論が成り立つことが知られており、証明は Cormen ほか（参考文献 [1]）の第 4 章にあります。また同書では正則条件を「十分大きなすべての $n$ で」という弱い形で述べています。この弱い形でも、条件が破れる項は高々 $\log_b n_0 + 1$ 個で、それぞれ $O(n^{\log_b a}) = O(f(n))$ なので結論は変わりません。マスター定理が使えない漸化式への対処法は Appendix で扱います。

例 6.3（マスター定理の適用）

(a) マージソート。 $T(n) = 2\,T(n/2) + \Theta(n)$ では $a = 2$, $b = 2$, $f(n) = \Theta(n)$ です。$\log_b a = \log_2 2 = 1$ なので $f(n) = \Theta(n^{1}) = \Theta(n^{\log_b a})$ となり、場合 2 に当てはまります。よって $T(n) = \Theta(n\log n)$ です。

(b) 二分探索。 $T(n) = T(n/2) + \Theta(1)$ では $a = 1$, $b = 2$, $f(n) = \Theta(1)$ です。$\log_2 1 = 0$ なので $n^{\log_b a} = n^{0} = 1$ であり、$f(n) = \Theta(1) = \Theta(n^{\log_b a})$ です。ふたたび場合 2 に当てはまり、$T(n) = \Theta(n^{0}\log n) = \Theta(\log n)$ です。

(c) Strassen の行列乗算。 $T(n) = 7\,T(n/2) + \Theta(n^{2})$ では $a = 7$, $b = 2$, $f(n) = \Theta(n^{2})$ です。$\log_2 7 = 2.8073\ldots$ なので、$\varepsilon = 0.5$ と取れば $n^{\log_2 7 - 0.5} = n^{2.307\ldots}$ であり、$n^{2} = O(n^{2.307\ldots})$ が成り立ちます。よって場合 1 に当てはまり、$T(n) = \Theta(n^{\log_2 7})$、とくに $T(n) = O(n^{2.808})$ です。素朴な三重ループの $\Theta(n^{3})$ より真に小さいオーダーです。

(d) 場合 3 の例。 $T(n) = 2\,T(n/2) + n^{2}$ では $\log_2 2 = 1$ で、$\varepsilon = 1$ として $n^{2} = \Omega(n^{1+1})$ です。正則条件は $2\,(n/2)^{2} = n^{2}/2 \le c\,n^{2}$ が $c = 1/2 < 1$ で成り立つので満たされます。よって $T(n) = \Theta(n^{2})$ で、再帰の最上段のコストだけで全体が決まります。

7. 多項式時間という境界線

ここまで見てきた $\Theta(n)$, $\Theta(n\log n)$, $\Theta(n^2)$, $\Theta(n^3)$ はいずれも「$n$ の多項式で抑えられる」という共通の性質を持ち、$\Theta(2^n)$, $\Theta(n!)$ は持ちません。例 5.4 が示したとおり、この境界は計算機の性能向上で動かせません。そこで次の定義が立てられます。

定義 7.1（多項式時間アルゴリズム）

アルゴリズム $A$ が多項式時間であるとは、ある定数 $k$ が存在して $T_A(n) = O(n^{k})$ が成り立つことをいう。

多項式時間を「効率的」の定義とする立場は Cobham と Edmonds に遡ります。この定義には $n^{100}$ も含まれてしまうという難点がありますが、次の 2 点で強い正当性を持ちます。第一に、多項式の集合は加法・乗法・合成について閉じているので、多項式時間アルゴリズムを部品として組み合わせても多項式時間のままです。第二に、この区別は計算モデルの細部に依存しません。RAM モデルとチューリング機械のあいだで計算量は多項式のずれしか生じないため、「多項式時間で解けるか」という問いはモデルを替えても答えが変わらないのです。

多項式時間で解ける判定問題の全体を $\mathrm{P}$、答えが「はい」のときにその証拠を多項式時間で検証できる判定問題の全体を $\mathrm{NP}$（定義 4.1［P≠NP 予想とは何か］）と書きます。$\mathrm{P} \subseteq \mathrm{NP}$ は定義からすぐ従いますが、逆向きの包含が成り立つかは 1971 年の問題提起以来未解決です。これが P≠NP 予想であり、部分和問題や巡回セールスマン問題を含む数千の問題が「$\mathrm{P} \ne \mathrm{NP}$ ならば多項式時間アルゴリズムを持たない」という形で結びついています。詳しくは P≠NP予想とは何か を参照してください。

計算量の記法を学ぶ意味はここにあります。$O$ 記法は個々のプログラムの速さを測る道具であると同時に、「何が計算できて何が計算できないか」を論じるための共通言語でもあるのです。

8. 演習

演習 8.1易

$f(n) = 3n^{2} + 5n\log_2 n + 100$ とする。$f \in \Theta(n^{2})$ であることを、定義 3.1 の定数 $c$ と $n_0$ を具体的に与えて示してください。

解答

上からの評価。 $n \ge 2$ のとき $\log_2 n \le n$ なので $5n\log_2 n \le 5n^{2}$ です。また $n \ge 10$ のとき $100 \le n^{2}$ です。よって $n \ge 10$ のとき

$$f(n) \le 3n^{2} + 5n^{2} + n^{2} = 9n^{2}$$

となり、$c_2 = 9$、$n_0 = 10$ として $f \in O(n^{2})$ です。

下からの評価。 $5n\log_2 n \ge 0$（$n \ge 1$）と $100 > 0$ より、すべての $n \ge 1$ で $f(n) \ge 3n^{2}$ です。よって $c_1 = 3$、$n_0 = 1$ として $f \in \Omega(n^{2})$ です。

両者を合わせ、$c_1 = 3$, $c_2 = 9$, $n_0 = 10$ で $f \in \Theta(n^{2})$ です。なお $\log_2 n \le n$（$n \ge 1$）は、定理 4.2 の第 1 主張から $\log_2 n \in o(n)$ が従うことでも保証されますが、ここでは $n \ge 2$ で $2^{n} \ge n$（$n$ についての帰納法：$2^{2} = 4 \ge 2$ で、$2^{n} \ge n$ なら $2^{n+1} = 2\cdot 2^{n} \ge 2n \ge n+1$）から直接得られます。

演習 8.2標準

$\log_2(n!) \in \Theta(n\log n)$ を示してください。Stirling の公式は使わないこと。

解答

上からの評価。 $n! = \prod_{i=1}^{n} i \le \prod_{i=1}^{n} n = n^{n}$ なので、両辺の $\log_2$ を取って（$\log_2$ は単調増加）

$$\log_2(n!) \le \log_2(n^{n}) = n\log_2 n .$$

よって $c = 1$, $n_0 = 1$ で $\log_2(n!) \in O(n\log n)$ です。

下からの評価。 $n \ge 2$ とし、積のうち大きいほうの半分だけを残します。$i \ge \lceil n/2\rceil$ を満たす $i$ は少なくとも $n/2$ 個あり、そのそれぞれが $n/2$ 以上なので

$$n! \ge \prod_{i=\lceil n/2\rceil}^{n} i \ge \left(\frac{n}{2}\right)^{n/2} .$$

$\log_2$ を取ると

$$\log_2(n!) \ge \frac{n}{2}\left(\log_2 n - 1\right) .$$

$n \ge 4$ のとき $\log_2 n \ge 2$ なので $\log_2 n - 1 \ge \log_2 n - \frac{1}{2}\log_2 n = \frac{1}{2}\log_2 n$ です。よって

$$\log_2(n!) \ge \frac{n}{4}\log_2 n \qquad (n \ge 4)$$

であり、$c = 1/4$, $n_0 = 4$ で $\log_2(n!) \in \Omega(n\log n)$ です。合わせて $\Theta(n\log n)$ を得ます。

この評価は、比較ソートの最悪比較回数が $\Omega(n\log n)$ であるという下界（定理 6.1［ソートアルゴリズム］）の証明に使われます。

演習 8.3標準

漸化式 $T(1) = 1$, $T(n) = 3\,T(n/4) + n\log_2 n$（$n$ は $4$ のべき乗）を解いてください。定理 6.1 のどの場合に当てはまるか、正則条件が満たされるかを明示すること。

解答

$a = 3$, $b = 4$, $f(n) = n\log_2 n$ です。まず $\log_b a = \log_4 3 = 0.7924\ldots$ を計算します。

どの場合か。 $\varepsilon = 0.2$ と取ると $\log_4 3 + \varepsilon = 0.9924\ldots < 1$ です。$n \ge 2$ のとき $\log_2 n \ge 1$ なので $f(n) = n\log_2 n \ge n \ge n^{0.9925}$ であり、$f(n) = \Omega(n^{\log_4 3 + \varepsilon})$ が成り立ちます。よって場合 3 の第 1 の条件を満たします。

正則条件。 $n = 4^{k}$（$k \ge 1$）に対し

$$a\,f(n/b) = 3\cdot\frac{n}{4}\log_2\frac{n}{4} = \frac{3}{4}\,n\left(\log_2 n - 2\right) \le \frac{3}{4}\,n\log_2 n = \frac{3}{4}\,f(n)$$

です。$c = 3/4 < 1$ と取れるので正則条件は満たされます（$\log_2 n - 2 \le \log_2 n$ は $-2 \le 0$ から従います）。

結論。 定理 6.1 の場合 3 より $T(n) = \Theta(f(n)) = \Theta(n\log n)$ です。再帰の分岐数 $3$ が縮小率 $4$ に負けているため、最上段のコストだけで全体が決まります。

演習 8.4難

$f \notin O(g)$ かつ $g \notin O(f)$ を満たす非負関数の組 $f, g$ を具体的に構成し、証明してください。この例は 命題 3.3 の仮定（極限の存在）が本質的であることを示します。

解答

構成。 $\mathbb{N}$ 上の関数を

$$f(n) = \begin{cases} n^{2} & (n \text{ が偶数}) \\ n & (n \text{ が奇数}) \end{cases} \qquad g(n) = \begin{cases} n & (n \text{ が偶数}) \\ n^{2} & (n \text{ が奇数}) \end{cases}$$

と定めます。どちらも非負です。

$f \notin O(g)$ の証明。 $f \in O(g)$ と仮定します。すると、ある $c > 0$ と $n_0$ があって、$n \ge n_0$ のすべての $n$ で $f(n) \le c\,g(n)$ です。ここで $n$ として $\max(n_0, \lceil c \rceil + 1)$ 以上の偶数を一つ取ります（そのような偶数は存在します）。この $n$ では $f(n) = n^{2}$、$g(n) = n$ なので、不等式は $n^{2} \le c\,n$、すなわち $n \le c$ となります。ところが $n \ge \lceil c\rceil + 1 > c$ なので矛盾です。よって $f \notin O(g)$ です。

$g \notin O(f)$ の証明。 まったく同じ議論を、偶数のかわりに奇数で行います。$g \in O(f)$ と仮定して $c, n_0$ を取り、$\max(n_0, \lceil c\rceil + 1)$ 以上の奇数 $n$ を取ると $g(n) = n^{2}$、$f(n) = n$ なので $n \le c$ となって矛盾します。

極限との関係。 $f(n)/g(n)$ は偶数 $n$ で $n$、奇数 $n$ で $1/n$ なので、$n \to \infty$ で振動し極限を持ちません。命題 3.3 は極限の存在を仮定していたので、この例には適用できません。$O$ 記法による大小関係は全順序ではない、というのがこの演習の教訓です。

参考文献

1. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022 — 第 3 章（漸近記法）、第 4 章（分割統治と漸化式、マスター定理の床関数つきの形）。
2. D. E. Knuth, “Big Omicron and big Omega and big Theta”, ACM SIGACT News 8 (1976), 18–24. DOI: 10.1145/1008328.1008329 — $O$, $\Omega$, $\Theta$ の用法を計算機科学向けに整理した論文。
3. D. E. Knuth, The Art of Computer Programming, Volume 1: Fundamental Algorithms, 3rd ed., Addison-Wesley, 1997 — 1.2.11 節（漸近的表現）。
4. R. L. Graham, D. E. Knuth, O. Patashnik, Concrete Mathematics, 2nd ed., Addison-Wesley, 1994 — 第 9 章（Asymptotics）。漸近展開の技法を詳しく扱っています。
5. J. Kleinberg, É. Tardos, Algorithm Design, Addison-Wesley, 2005 — 第 2 章（アルゴリズム解析の基礎と代表的な計算量クラス）。
6. M. R. Garey, D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, 1979 — 第 1 章。多項式時間と指数時間の差を計算機の高速化と対比する表があります。

Appendix: マスター定理が使えないとき

定理 6.1 は $n$ が $b$ のべき乗である場合に述べました。実際の漸化式は床関数を含み、また分割の形がマスター定理の枠に収まらないこともあります。そのようなときは置換法、すなわち答えを予想して帰納法で検証する方法が使えます。マージソートの正確な漸化式で見ます。

$T(1) = 1$、$n \ge 2$ に対し $T(n) = 2\,T(\lfloor n/2\rfloor) + n$ と定めます（実際のマージソートは $\lfloor n/2 \rfloor$ と $\lceil n/2\rceil$ に分けますが、ここでは技法を見るため簡略化した形を扱います）。

上からの評価。 すべての $n \ge 2$ で $T(n) \le 2n\log_2 n$ が成り立つことを、$n$ についての強い帰納法で示します。

• $n = 2$：$T(2) = 2T(1) + 2 = 4$ であり、$2\cdot 2\log_2 2 = 4$ なので $T(2) \le 4$ が成り立ちます。
• $n = 3$：$T(3) = 2T(1) + 3 = 5$ であり、$2\cdot 3\log_2 3 = 9.50\ldots$ なので成り立ちます。
• $n \ge 4$：このとき $\lfloor n/2\rfloor \ge 2$ かつ $\lfloor n/2 \rfloor < n$ なので帰納法の仮定が使えて、$T(\lfloor n/2\rfloor) \le 2\lfloor n/2\rfloor \log_2 \lfloor n/2\rfloor$ です。$\lfloor n/2\rfloor \le n/2$ と $\log_2$ の単調性から

$$T(n) \le 2\cdot 2\cdot\frac{n}{2}\log_2\frac{n}{2} + n = 2n(\log_2 n - 1) + n = 2n\log_2 n - n \le 2n\log_2 n$$

です。最後の不等号は $n > 0$ から従います。

よって $T(n) = O(n\log n)$ です。$-n$ という余りが残った点が重要で、帰納法が「回った」のはこの余裕があったからです。もし $T(n) \le c\,n\log_2 n$ を $c = 1$ で示そうとすると余りが $0$ 以下にならず、帰納が閉じません。

下からの評価。 まず $T$ が単調非減少であることを示します。$n$ についての強い帰納法で $T(n) \ge T(n-1)$（$n \ge 2$）を示します。$n = 2$ では $T(2) = 4 \ge T(1) = 1$ です。$n \ge 3$ のとき、$\lfloor n/2\rfloor \ge \lfloor (n-1)/2\rfloor \ge 1$ であり、帰納法の仮定（$n$ 未満の引数で $T$ が単調）から $T(\lfloor n/2\rfloor) \ge T(\lfloor (n-1)/2\rfloor)$ です。よって

$$T(n) = 2T(\lfloor n/2\rfloor) + n \ge 2T(\lfloor (n-1)/2\rfloor) + (n-1) = T(n-1)$$

です（$n = 3$ のときは右辺の漸化式が $T(2)$ の定義そのものであり、$n \ge 4$ でも同様です）。

次に $n$ が $2$ のべき乗 $2^{k}$ のときの値を求めます。$T(2^{k}) = 2T(2^{k-1}) + 2^{k}$ と $T(1) = 1$ から、$k$ についての帰納法で $T(2^{k}) = 2^{k}(k+1)$ が示せます。実際 $k = 0$ では $2^{0}(0+1) = 1 = T(1)$ で、$k-1$ で成り立てば

$$T(2^{k}) = 2\cdot 2^{k-1}k + 2^{k} = 2^{k}k + 2^{k} = 2^{k}(k+1)$$

です。そこで一般の $n \ge 1$ に対し $m = 2^{\lfloor \log_2 n\rfloor}$ とおくと $m \le n$ かつ $m > n/2$ なので、単調性から

$$T(n) \ge T(m) = m\left(\lfloor\log_2 n\rfloor + 1\right) > \frac{n}{2}\log_2 n$$

です（$\lfloor \log_2 n\rfloor + 1 > \log_2 n$ を使いました）。よって $T(n) = \Omega(n\log n)$ であり、上の評価と合わせて $T(n) = \Theta(n\log n)$ です。

置換法の要点は、証明したい形をあらかじめ固定してから帰納法に入ることです。$O(n\log n)$ のようにオーダーだけを仮定して帰納すると、定数が毎回大きくなって発散するという誤りに陥ります。$T(n) \le 2n\log_2 n$ のように定数まで込みで書き下し、帰納のステップで同じ定数が保たれることを確認してください。