マスター定理

$T (n) = a T (n / b) + f (n)$ の形の漸化式について、 $f (n)$ と $n^{l o g_{b} a}$ を比べて場合を判定し、 $T (n) = Θ (\dots)$ の中身の式（例: $n^{l o g_{2} 3}$ , $n lo g n$ ）を答えられる

前提

分割統治の漸化式の厳密な解（大学数学アルゴリズムと計算量）
計算量のオーダーの比較（大学数学アルゴリズムと計算量）

この技能までの道筋（29 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

小数の四則計算（算数計算と数のきまり）
分数のたし算・ひき算（算数計算と数のきまり）
分数のかけ算・わり算（算数計算と数のきまり）
小数と分数のまじった計算（算数計算と数のきまり）
逆算（□ を求める）（算数計算と数のきまり）
正負の数の加法・減法（中学数学数と式）
四則の混じった計算の順序（算数計算と数のきまり）
正負の数の乗除・累乗と四則混合（中学数学数と式）
分配法則を使った計算のくふう（算数計算と数のきまり）
文字式の計算（同類項・分配法則）（中学数学数と式）
1 次方程式の解き方（中学数学方程式）
連立方程式の解き方（加減法・代入法）（中学数学方程式）
等差数列・等比数列の一般項（数学B 数列）
$a_{n + 1} = p a_{n} + q$ 型の漸化式（数学B 数列）
等間隔にならんだ数の和（算数計算と数のきまり）
等差・等比数列の和と Σ （数学B 数列）
階差数列と階差型の漸化式（数学B 数列）
（等差）×（等比）の数列の和（数学B 数列）
置き換えによる漸化式の解法（数学B 数列）
分割統治の漸化式の厳密な解（大学数学アルゴリズムと計算量）
数列の極限（数学III 極限）
関数の極限（数学III 極限）
約数の見つけ方（算数整数の性質）
素因数分解と約数の個数（算数整数の性質）
平方根の意味と根号の簡単化（中学数学数と式）
根号の乗除と加減（中学数学数と式）
指数の拡張と指数関数（数学II 指数関数と対数関数）
対数の定義と性質（数学II 指数関数と対数関数）
計算量のオーダーの比較（大学数学アルゴリズムと計算量）

説明

マスター定理を使うと、問題を $a$ 個の大きさ $n / b$ の部分問題に分け、分割と統合に $f (n)$ の手間がかかる分割統治の漸化式 $T (n) = a T (n / b) + f (n)$ について、増え方 $T (n) = Θ (\dots)$ を解かずに答えられます。やることは、 $f (n)$ と「臨界関数」 $n^{l o g_{b} a}$ を比べ、3 つの場合のどれに当たるかを判定するだけです。マージソート、カラツバ法、ストラッセン法などの計算量を見積もるときに使います。

なぜそうしてよいのか

記号を確認します。正の定数 $c_{1}, c_{2}$ と $n_{0}$ があって、 $n \geq n_{0}$ で $c_{1} g (n) \leq T (n) \leq c_{2} g (n)$ が成り立つとき $T (n) = Θ (g (n))$ と書きます。上からの不等式 $T (n) \leq c_{2} g (n)$ だけが成り立つときは $T (n) = O (g (n))$ 、下からの不等式 $T (n) \geq c_{1} g (n)$ だけが成り立つときは $T (n) = Ω (g (n))$ と書きます。 $Θ$ は定数倍の違いを無視するので、 $lo g_{2} n$ と $lo g n$ は $Θ$ の中では同じです。

$n = b^{k}$ とおき、漸化式をくり返し代入します（前提の技能と同じ置き換えです）。すると $T (n) = j = 0 \sum k - 1 a^{j} f (\frac{n}{b ^{j}}) + a^{k} T (1)$ となります。第 $j$ 段には大きさ $n / b^{j}$ の部分問題が $a^{j}$ 個あり、その段の手間は $a^{j} f (n / b^{j})$ です。最下段の部分問題の個数は $a^{k} = a^{l o g_{b} n} = n^{l o g_{b} a}$ です（ $a^{l o g_{b} n} = b^{l o g_{b} a \cdot l o g_{b} n} = n^{l o g_{b} a}$ だからです）。これが臨界関数 $n^{l o g_{b} a}$ の正体です。

$f (n) = n^{d}$ の場合で確かめます。 $p = lo g_{b} a$ とおくと、第 $j$ 段の手間は $a^{j} (n / b^{j})^{d} = n^{d} r^{j}$ $(r = a / b^{d})$ で、和は公比 $r$ の等比数列になります。 $d > p$ なら $r < 1$ なので、和は $n^{d}$ 以上 $\frac{n ^{d}}{1 - r}$ 以下に収まり、最上段が支配して $Θ (n^{d}) = Θ (f (n))$ です（最下段の $n^{p} T (1)$ は $n^{d}$ より小さいので影響しません）。 $d = p$ なら $r = 1$ なので、どの段も手間が $n^{p}$ で、段数が $lo g_{b} n$ 個あるので $Θ (n^{p} lo g n)$ です。 $d < p$ なら $r > 1$ なので、和は $n^{d} \frac{r ^{k} - 1}{r - 1}$ です。 $r^{k} = a^{k} / b^{d k} = n^{p} / n^{d}$ なので和は $n^{p}$ の定数倍で、最下段が支配して $Θ (n^{p})$ です。一般の $f$ でも同じで、 $f$ と $n^{p}$ のどちらが「多項式の差（ $n^{ε}$ 倍）で」大きいかによって、支配する段が決まります。

手順

形を確認し、 $a, b, f$ を読み取る： $a \geq 1$ と $b > 1$ は定数で、 $f (n)$ は十分大きい $n$ で正であること。
臨界指数 $p = lo g_{b} a$ を計算し、臨界関数 $n^{p}$ を求める。
$f (n)$ が $n^{p}$ より多項式的に小さい（ある $ε > 0$ で $f (n) = O (n^{p - ε})$ ）なら、場合 1 として $T (n) = Θ (n^{p})$ と答える。
$f (n) = Θ (n^{p})$ なら、場合 2 として $T (n) = Θ (n^{p} lo g n)$ と答える。
$f (n)$ が多項式的に大きい（ある $ε > 0$ で $f (n) = Ω (n^{p + ε})$ ）なら、正則条件を確かめる。正則条件とは、ある定数 $c < 1$ について十分大きい $n$ で $a f (n / b) \leq c f (n)$ が成り立つことである。成り立てば、場合 3 として $T (n) = Θ (f (n))$ と答える。
3 つのどれにも当てはまらない場合（例： $f (n) = n^{p} lo g n$ ）は、基本形のマスター定理は使えない。 $n = b^{k}$ とおいて直接計算する。

例題

$n$ は 2 の累乗とし、 $T (1) = 1$ 、 $T (n) = 7 T (n /2) + n^{2}$ （ $n \geq 2$ ）とする。 $T (n) = Θ (g (n))$ となる $g (n)$ を、 $Θ$ の中身の最も簡単な形の式で求めよ。

例題の解答

手順 1： $a = 7 \geq 1$ 、 $b = 2 > 1$ 、 $f (n) = n^{2} > 0$ なので、マスター定理の形をしている。
手順 2： $p = lo g_{2} 7$ である。 $2^{2} = 4 < 7 < 8 = 2^{3}$ より $2 < p < 3$ （ $p \approx 2.807$ ）。臨界関数は $n^{l o g_{2} 7}$ である。
手順 3： $ε = lo g_{2} 7 - 2 > 0$ とおくと $f (n) = n^{2} = n^{p - ε}$ なので、 $f (n) = O (n^{p - ε})$ が成り立つ。よって $f$ は臨界関数より多項式的に小さく、場合 1 に当たる。
結論： $T (n) = Θ (n^{l o g_{2} 7})$ 。
（確認：第 $j$ 段の手間は $n^{2} (7/4)^{j}$ で、公比 $7/4 > 1$ の等比数列になる。したがって最下段の $n^{l o g_{2} 7}$ が支配する。）

答え: $n^{l o g_{2} 7}$

よくある誤り

臨界指数を $lo g_{a} b$ や $a / b$ にしてしまう誤り。 $T (n) = 4 T (n /2) + n$ の臨界関数を $n^{l o g_{4} 2} = n^{1/2}$ としてはいけない。正しくは $p = lo g_{2} 4 = 2$ なので、場合 1 となり $Θ (n^{2})$ である。
場合 2 で $lo g n$ を付け忘れる誤り。 $T (n) = 2 T (n /2) + n$ では $f (n) = n = Θ (n^{l o g_{2} 2})$ なので、答えは $n$ ではない。正しくは $Θ (n lo g n)$ である。
場合 3 なのに臨界関数を答えてしまう誤り。 $T (n) = 2 T (n /2) + n^{2}$ では $n^{2} = Ω (n^{1 + 1})$ である。正則条件も $2 (n /2)^{2} = \frac{1}{2} n^{2}$ で $c = \frac{1}{2} < 1$ として成り立つ。よって答えは $n$ ではなく、正しくは $Θ (n^{2})$ である。
「大きい」だけで場合 3 を当てはめてしまう誤り。 $T (n) = 2 T (n /2) + n lo g n$ では、 $n lo g n$ は $n$ より大きいが、どんな $ε > 0$ に対しても $n lo g n = o (n^{1 + ε})$ なので、多項式的には大きくない。したがって $Θ (n lo g n)$ とは言えない。正しくは $n = 2^{k}$ とおいて $T (2^{k}) / 2^{k}$ の階差型の漸化式を解き、 $Θ (n (lo g n)^{2})$ を得る。

この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。

マスター定理

前提

説明

なぜそうしてよいのか

手順

例題

よくある誤り

入口の問題

この技能を使う問題