計算量と漸化式オーダー記法・マスター定理・漸化式の解き方

アルゴリズムの計算量は、入力の大きさ $n$ に対する基本操作の回数を関数 $T(n)$ で表し、その増え方を $O$ ・ $\Omega$ ・ $\Theta$ 記法で比べる。分割統治法の計算量は $T(n) = aT(n/b) + f(n)$ の形の漸化式になり、 $f(n)$ と $n^{\log_b a}$ の大小を比べるマスター定理で多くの場合の解が決まる。マスター定理の当てはまらない漸化式は、展開して和を計算する再帰木か、解を予想して帰納法で示す置換法で解く。

アルゴリズムとデータ構造の第1単元（全4単元）。

情報系院試の問題集・ロードマップ

東大情報理工・東京科学大・阪大の大学別に、出題マップと類題を1冊にした教材（各4,980円）。収録内容と見本を商品ページで確認できる。

情報系の教材を見る

計算量とオーダー記法の定義

定義

時間計算量

大きさ $n$ の入力に対してアルゴリズムが行う基本操作（比較、代入、算術演算など）の回数を時間計算量という。大きさ $n$ の入力全体での最大値を最悪時の計算量、入力の分布を決めたときの期待値を平均時の計算量と呼ぶ。使う記憶領域の量を同じように数えたものを領域計算量という。

定義

$O$ ・ $\Omega$ ・ $\Theta$ 記法

$f, g$ を十分大きな $n$ で正の値をとる関数とする。

\begin{aligned} f(n) = O(g(n)) &\iff \exists c > 0,\ \exists n_0,\ \forall n \ge n_0:\ f(n) \le c\, g(n) \\ f(n) = \Omega(g(n)) &\iff \exists c > 0,\ \exists n_0,\ \forall n \ge n_0:\ f(n) \ge c\, g(n) \\ f(n) = \Theta(g(n)) &\iff f(n) = O(g(n)) \text{ かつ } f(n) = \Omega(g(n)) \end{aligned}

$O$ は上界、 $\Omega$ は下界、 $\Theta$ は上下両方からの評価を表す。 $f(n) = o(g(n))$ は「任意の $c > 0$ に対して、十分大きな $n$ で $f(n) < c\,g(n)$ 」を意味する。

定理・法則

極限による判定

条件

$f, g$ は十分大きな $n$ で正。極限 $L = \lim_{n \to \infty} f(n)/g(n)$ が存在する（ $\infty$ を含む）。

主張

$0 < L < \infty$ なら $f(n) = \Theta(g(n))$ 。
$L = 0$ なら $f(n) = o(g(n))$ 、特に $f(n) = O(g(n))$ 。
$L = \infty$ なら $f(n) = \Omega(g(n))$ で、 $f(n) = O(g(n))$ ではない。

要点

極限が存在しない場合はこの判定は使えず、定義に戻る。たとえば $f(n) = n(2 + \sin n)$ と $g(n) = n$ では比が振動するが、 $n \le f(n) \le 3n$ から $f(n) = \Theta(n)$ である。

計算例

定義どおりに $\Theta$ を示す

$f(n) = 3n^2 + 5n$ が $\Theta(n^2)$ であることを、定数 $c, n_0$ を具体的に与えて示せ。

解答

$n \ge 1$ のとき $5n \le 5n^2$ なので $f(n) \le 8n^2$ 。また $f(n) \ge 3n^2$ 。よって $c_1 = 3$ 、 $c_2 = 8$ 、 $n_0 = 1$ として $3n^2 \le f(n) \le 8n^2$ （ $n \ge 1$ ）が成り立ち、 $f(n) = \Theta(n^2)$ 。

検算

極限でも $\lim_{n\to\infty} (3n^2 + 5n)/n^2 = 3$ で、 $0 < 3 < \infty$ から同じ結論になる。

マスター定理と使える条件

定理・法則

マスター定理

条件

$a \ge 1$ 、 $b > 1$ は定数、 $f(n)$ は十分大きな $n$ で正の関数で、 $T(n) = aT(n/b) + f(n)$ （ $n/b$ は $\lfloor n/b \rfloor$ や $\lceil n/b \rceil$ でもよい）。 $\alpha = \log_b a$ とおく。

主張

ある $\varepsilon > 0$ で $f(n) = O(n^{\alpha - \varepsilon})$ なら $T(n) = \Theta(n^{\alpha})$ 。
$f(n) = \Theta(n^{\alpha})$ なら $T(n) = \Theta(n^{\alpha} \log n)$ 。
ある $\varepsilon > 0$ で $f(n) = \Omega(n^{\alpha + \varepsilon})$ であり、さらにある定数 $c < 1$ と十分大きな $n$ で $a f(n/b) \le c f(n)$ （正則条件）が成り立つなら $T(n) = \Theta(f(n))$ 。

要点

再帰木の深さ $j$ の段の和は $a^j f(n/b^j)$ で、葉は $a^{\log_b n} = n^{\alpha}$ 個ある。場合1は葉の和、場合3は根の項が全体を決め、場合2は $\log_b n$ 段がほぼ同じ大きさになる。 $f(n)$ が $n^{\alpha}$ より大きく（小さく）ても多項式の差 $n^{\varepsilon}$ がなければ、3つのどれにも当てはまらない。

場合2は $f(n) = \Theta(n^{\alpha} \log^k n)$ （ $k \ge 0$ ）に広げられ、そのとき $T(n) = \Theta(n^{\alpha} \log^{k+1} n)$ となる。この拡張版を使う答案では、拡張版であることを書いておく。 $T(n) = T(n-1) + f(n)$ のように引数が定数ずつしか減らない漸化式は、 $b > 1$ の形でないのでマスター定理の対象外である。

よく出る漸化式の解

代表的な漸化式（ $T(1)$ は定数）

二分探索: $T(n) = T(n/2) + \Theta(1) \ \Rightarrow\ T(n) = \Theta(\log n)$
マスター定理の場合2（ $a = 1$ 、 $b = 2$ 、 $\alpha = 0$ ）。
マージソート: $T(n) = 2T(n/2) + \Theta(n) \ \Rightarrow\ T(n) = \Theta(n \log n)$
場合2（ $\alpha = 1$ ）。
木の走査: $T(n) = 2T(n/2) + \Theta(1) \ \Rightarrow\ T(n) = \Theta(n)$
場合1（ $\alpha = 1$ 、 $f(n) = O(n^{1 - \varepsilon})$ ）。
カラツバ法: $T(n) = 3T(n/2) + \Theta(n) \ \Rightarrow\ T(n) = \Theta(n^{\log_2 3})$
$\log_2 3 \approx 1.585$ 。場合1。
挿入ソートの最悪: $T(n) = T(n-1) + \Theta(n) \ \Rightarrow\ T(n) = \Theta(n^2)$
和 $\sum_{k=1}^{n} k = n(n+1)/2$ から。
素朴なフィボナッチ: $T(n) = T(n-1) + T(n-2) + \Theta(1) \ \Rightarrow\ T(n) = \Theta(\varphi^n), \quad \varphi = \frac{1 + \sqrt{5}}{2}$
特性方程式 $x^2 = x + 1$ の大きいほうの解が増え方を決める。

増え方の順序

代表的な関数: $1 \prec \log n \prec \sqrt{n} \prec n \prec n \log n \prec n^2 \prec n^3 \prec 2^n \prec n! \prec n^n$
$f \prec g$ は $f = o(g)$ の意味。任意の $k > 0$ 、 $\varepsilon > 0$ で $\log^k n = o(n^{\varepsilon})$ 、 $n^k = o(2^n)$ 。
スターリングの公式から: $\log_2 n! = n \log_2 n - n \log_2 e + O(\log n) = \Theta(n \log n)$

再帰木と置換法で漸化式を解く

再帰木の方法は次の順で進める。

漸化式を1段ずつ展開し、深さ $j$ の段にある部分問題の数と大きさを書く（例： $a^j$ 個、大きさ $n/b^j$ ）。
段ごとの和 $a^j f(n/b^j)$ を求める。
深さ $\log_b n$ まで足し、葉の分 $\Theta(n^{\log_b a})$ を加える。
得た式を予想として、必要なら帰納法（置換法）で上界・下界を示す。

計算例

$2T(n/2) + n$ の厳密解

$n = 2^k$ に対して $T(1) = 0$ 、 $T(n) = 2T(n/2) + n$ を解け。

解答

両辺を $n$ で割って $S(k) = T(2^k)/2^k$ とおくと $S(k) = S(k-1) + 1$ 、 $S(0) = 0$ なので $S(k) = k$ 。よって

T(n) = n \log_2 n

再帰木で見ると、各段の和はどれも $n$ で、段の数は $\log_2 n$ である。

検算

$T(2) = 2$ 、 $T(4) = 2 \cdot 2 + 4 = 8$ 、 $T(8) = 2 \cdot 8 + 8 = 24$ で、 $n \log_2 n$ はそれぞれ $2, 8, 24$ 。マスター定理の場合2の $\Theta(n \log n)$ とも一致する。

計算例

$3T(n/2) + n$ の厳密解

$n = 2^k$ に対して $T(1) = 1$ 、 $T(n) = 3T(n/2) + n$ を解け。

解答

展開すると深さ $j$ の段の和は $3^j \cdot n/2^j = n(3/2)^j$ で、深さ $k$ に $3^k$ 個の葉がある。

T(n) = \sum_{j=0}^{k-1} n\left(\frac{3}{2}\right)^j + 3^k = 2n\left(\left(\frac{3}{2}\right)^k - 1\right) + 3^k = 3 \cdot 3^k - 2n

$3^k = 3^{\log_2 n} = n^{\log_2 3}$ なので $T(n) = 3n^{\log_2 3} - 2n = \Theta(n^{\log_2 3})$ 。

検算

$T(2) = 3 + 2 = 5$ と $3 \cdot 3 - 4 = 5$ 、 $T(4) = 15 + 4 = 19$ と $3 \cdot 9 - 8 = 19$ が一致する。 $f(n) = n = O(n^{\log_2 3 - 0.5})$ なのでマスター定理の場合1とも合う。

計算例

マスター定理の基本形で解けない漸化式

$n = 2^k$ に対して $T(1) = 0$ 、 $T(n) = 2T(n/2) + n\log_2 n$ を解け。

解答

$\alpha = 1$ で、 $f(n)/n^{\alpha} = \log_2 n$ は増えるが、どの $\varepsilon > 0$ でも $n^{\varepsilon}$ より遅い。よって場合3は使えない。再帰木では深さ $j$ の段の和が $2^j \cdot (n/2^j)\log_2(n/2^j) = n(k - j)$ なので

T(n) = \sum_{j=0}^{k-1} n(k-j) = n\,\frac{k(k+1)}{2} = \frac{n \log_2 n\,(\log_2 n + 1)}{2} = \Theta(n \log^2 n)

検算

$T(2) = 2$ 、 $T(4) = 2 \cdot 2 + 4 \cdot 2 = 12$ で、式の値は $2 \cdot 1 \cdot 2/2 = 2$ 、 $4 \cdot 2 \cdot 3/2 = 12$ 。拡張版の場合2（ $k = 1$ ）の $\Theta(n\log^2 n)$ とも一致する。

答案でよくある誤り

1
$O$ を「ちょうどその増え方」の意味で使う。 $n = O(n^2)$ も正しいので、上下両方を言うときは $\Theta$ を使い、下界も示す。
2
$f(n) = n\log n$ 、 $a = b = 2$ にマスター定理の場合3を当てはめる。 $n \log n$ は $n^{1+\varepsilon}$ より遅いので場合3の条件を満たさない。再帰木で解くか、拡張版の場合2を明示して使う。
3
場合3で正則条件 $af(n/b) \le cf(n)$ （ $c < 1$ ）を確かめずに結論する。多項式の $f$ では成り立つが、答案では一行で確認を書く。
4
$T(n) = T(n-1) + n$ にマスター定理を使う。引数が定数ずつ減る漸化式は対象外で、和 $\sum k = \Theta(n^2)$ を直接計算する。
5
対数の底を気にして $O(\log_2 n)$ と $O(\log_{10} n)$ を区別する。底の変換は定数倍なのでオーダーは同じだが、 $2^{\log_2 n} = n$ と $2^{\log_{10} n}$ のように指数に入ると異なる。