分割統治の漸化式の厳密な解

$T (n) = a T (n /2) + n$ , $T (1) = 1$ のような漸化式を $n = 2^{k}$ とおいて $k$ の漸化式に直し、 $T (2^{k})$ を $k$ の式で求められる

前提

置き換えによる漸化式の解法（数学B 数列）

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

小数の四則計算（算数計算と数のきまり）
分数のたし算・ひき算（算数計算と数のきまり）
分数のかけ算・わり算（算数計算と数のきまり）
小数と分数のまじった計算（算数計算と数のきまり）
逆算（□ を求める）（算数計算と数のきまり）
正負の数の加法・減法（中学数学数と式）
四則の混じった計算の順序（算数計算と数のきまり）
正負の数の乗除・累乗と四則混合（中学数学数と式）
分配法則を使った計算のくふう（算数計算と数のきまり）
文字式の計算（同類項・分配法則）（中学数学数と式）
1 次方程式の解き方（中学数学方程式）
連立方程式の解き方（加減法・代入法）（中学数学方程式）
等差数列・等比数列の一般項（数学B 数列）
$a_{n + 1} = p a_{n} + q$ 型の漸化式（数学B 数列）
等間隔にならんだ数の和（算数計算と数のきまり）
等差・等比数列の和と Σ （数学B 数列）
階差数列と階差型の漸化式（数学B 数列）
（等差）×（等比）の数列の和（数学B 数列）
置き換えによる漸化式の解法（数学B 数列）

説明

アルゴリズムの計算時間を表す $T (n) = a T (n /2) + n$ , $T (1) = 1$ のような分割統治の漸化式を、 $n = 2^{k}$ とおいて普通の数列の漸化式に直し、 $T (2^{k})$ を $k$ の式で正確に求められるようになります。マージソートのように、大きさ $n$ の問題を大きさ $n /2$ の問題 $a$ 個（ $a$ は正の整数）に分けて解き、分割と統合に $n$ に比例する手間がかかる場面で使います。オーダーを見積もるだけでなく、具体的な値まで求められます。

なぜそうしてよいのか

$T (n) = a T (n /2) + n$ は、 $n$ での値を $n /2$ での値から決める式です。 $T (1)$ から出発して $n$ を 2 倍ずつにしていくと、値が決まるのは $n = 1, 2, 4, 8, \dots$ だけです。そこで $n = 2^{k}$ （ $k$ は 0 以上の整数）に限り、 $a_{k} = T (2^{k})$ とおきます。 $n = 2^{k}$ のとき $n /2 = 2^{k - 1}$ なので $T (n /2) = a_{k - 1}$ です。また、式の中の $n$ そのものは $2^{k}$ です。すると漸化式は $a_{k} = a a_{k - 1} + 2^{k}$ （ $k \geq 1$ ）、 $a_{0} = T (1)$ という、添字が 1 ずつ進む普通の数列の漸化式になります。

この形は、前提の技能で扱った $a_{n + 1} = 2 a_{n} + 3^{n}$ 型と同じです。分割統治では $a$ は部分問題の個数なので正の整数であり、特に $a \neq = 0$ です。そこで両辺を $a^{k}$ で割り、 $b_{k} = \frac{a _{k}}{a ^{k}}$ とおくと $b_{k} = b_{k - 1} + (\frac{2}{a})^{k}$ という階差型になります。あとは $b_{k} = b_{0} + j = 1 \sum k (\frac{2}{a})^{j}$ を等比数列の和で計算し、 $a_{k} = a^{k} b_{k}$ に戻せば $T (2^{k})$ が求まります。ただし $a = 2$ のときは公比が 1 なので和は $k$ になり、 $T (1) = 1$ なら $T (2^{k}) = (k + 1) 2^{k}$ です。

手順

$a$ が 0 でない（分割統治では正の整数）ことを確認し、 $a_{k} = T (2^{k})$ （ $k$ は 0 以上の整数）とおく。 $n = 2^{k}$ のとき $n /2 = 2^{k - 1}$ である。
漸化式を $k$ で書き直す: $a_{k} = a a_{k - 1} + 2^{k}$ （ $k \geq 1$ ）。初期値は $a_{0} = T (2^{0}) = T (1)$ 。
$a \neq = 0$ なので両辺を $a^{k}$ で割り、 $b_{k} = \frac{a _{k}}{a ^{k}}$ とおいて階差型 $b_{k} = b_{k - 1} + (\frac{2}{a})^{k}$ に直す（ $b_{0} = a_{0}$ ）。
$b_{k} = b_{0} + j = 1 \sum k (\frac{2}{a})^{j}$ を計算する。 $a \neq = 2$ なら等比数列の和、 $a = 2$ なら和は $k$ 。
$a_{k} = a^{k} b_{k}$ に戻して $T (2^{k})$ を求め、 $k = 0, 1, 2$ で元の漸化式と一致するか確かめる。

例題

関数 $T$ が $T (1) = 1$ 、 $T (n) = 3 T (n /2) + n$ （ $n$ は 2 以上の 2 のべき乗）を満たすとき、 $T (2^{k})$ （ $k$ は 0 以上の整数）を $k$ の式で求めよ。

例題の解答

手順1: $a = 3 \neq = 0$ 。 $a_{k} = T (2^{k})$ とおく。 $n = 2^{k}$ のとき $n /2 = 2^{k - 1}$ なので $T (n /2) = a_{k - 1}$ 。
手順2: 漸化式は $a_{k} = 3 a_{k - 1} + 2^{k}$ （ $k \geq 1$ ）、初期値は $a_{0} = T (1) = 1$ 。
手順3: 両辺を $3^{k}$ で割ると $\frac{a _{k}}{3 ^{k}} = \frac{a _{k - 1}}{3 ^{k - 1}} + (\frac{2}{3})^{k}$ 。 $b_{k} = \frac{a _{k}}{3 ^{k}}$ とおくと $b_{k} = b_{k - 1} + (\frac{2}{3})^{k}$ 、 $b_{0} = 1$ 。
手順4: $k \geq 1$ のとき $b_{k} = 1 + j = 1 \sum k (\frac{2}{3})^{j} = 1 + \frac{\frac{2}{3} ( 1 - ( \frac{2}{3} ) ^{k} )}{1 - \frac{2}{3}} = 1 + 2 (1 - (\frac{2}{3})^{k}) = 3 - 2 (\frac{2}{3})^{k}$ 。これは $k = 0$ のときも $3 - 2 = 1 = b_{0}$ で成り立つ。
手順5: $a_{k} = 3^{k} b_{k} = 3^{k + 1} - 2 \cdot 2^{k} = 3^{k + 1} - 2^{k + 1}$ 。確認: $k = 0$ で $3 - 2 = 1$ 、 $k = 1$ で $T (2) = 3 \cdot 1 + 2 = 5 = 9 - 4$ 、 $k = 2$ で $T (4) = 3 \cdot 5 + 4 = 19 = 27 - 8$ と一致する。
よって $T (2^{k}) = 3^{k + 1} - 2^{k + 1}$ 。

答え: $3^{k + 1} - 2^{k + 1}$

よくある誤り

式の中の $n$ を $k$ に書き換えて $a_{k} = 3 a_{k - 1} + k$ としてしまう誤り。正しくは $n = 2^{k}$ なので $a_{k} = 3 a_{k - 1} + 2^{k}$ 。
初期値を $a_{1} = T (1) = 1$ としてしまう誤り。 $1 = 2^{0}$ なので正しくは $a_{0} = T (1) = 1$ 。 $a_{1} = 1$ から始めると $a_{2} = 3 \cdot 1 + 2^{2} = 7$ となるが、本当の $a_{2} = T (4) = 19$ とは合わず、誤った値になる（一般には $a_{k} = 5 \cdot 3^{k - 1} - 2^{k + 1}$ という誤った式が出る）。
$a = 2$ （例: $T (n) = 2 T (n /2) + n$ ）のときも等比数列の和の公式 $\frac{r ( 1 - r ^{k} )}{1 - r}$ に $r = \frac{2}{2} = 1$ を入れてしまう誤り。分母が 0 になるので使えない。正しくは $b_{k} = b_{k - 1} + 1$ より $b_{k} = b_{0} + k$ 、 $T (1) = 1$ なら $T (2^{k}) = (k + 1) 2^{k}$ 。
求めた式が 2 のべき乗でない $n$ にも成り立つとしてしまう誤り。この漸化式で値が決まるのは $n = 2^{k}$ のときだけで、 $n$ の式にするなら $k = lo g_{2} n$ として $T (n) = 3 n^{l o g_{2} 3} - 2 n$ （ $3^{l o g_{2} n} = n^{l o g_{2} 3}$ を用いた）と、 $n$ が 2 のべき乗の場合に限って書く。

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

入口の問題

この技能を使う問題

この技能の次に学べること

マスター定理（大学数学アルゴリズムと計算量）