マスター定理

図で納得する

$T(n)$は、大きさ$n$の問題を解く手数（回）である。$n$は、並べ替える数の個数のような問題の大きさで、$a$は分けてできる小さな問題の数、$b$は小さな問題1つが元の何分の1の大きさかを表す。$\Theta (n^d)$は、分けた答えをつなぐ手数が$n$の$d$乗くらいかかることを表す。

$\Theta$（シータ）は、だいたいの増え方を表す記号だ。$T(n)=\Theta (n^2)$は、$n$が大きいとき、$T(n)$が$n^2$の決まった2つの倍数、たとえば1倍と2倍の間に挟まることをいう。つまり、定数倍の違いは気にせず、$n$を10倍にしたら手数が何倍になるかだけを見る。

分割統治の手数は、分け方を木の形に描くとつかめる。いちばん上の段に大きさ$n$の問題を置き、分けた$a$個を1つ下の段に並べる。これを大きさ1になるまで続けると、各段の手数をすべて足したものが$T(n)$になる。

段ごとの手数は、$a$、$b$、$d$の組み合わせによって、下の段ほど減るか、どの段も同じか、下の段ほど増えるかの3通りに分かれる。

大きさ$n=32$の問題を$b=2$で分け、分ける数$a$とつなぐ手数$d$を選ぶと、段0から段5までの手数が棒で並ぶ。マージソート（$a=2$、$d=1$）と二分探索（$a=1$、$d=0$）では、どの段も同じ長さになる。カラツバ法（$a=3$、$d=1$）では下の段ほど長く、$a=2$、$d=2$では下の段ほど短い。

読み出しの${\log }_{2}a$は「2を何乗すると$a$になるか」を表す数で、これを$d$と比べると答えが決まる。

では、段の手数を全部足すと、どれくらいになるのか。段の手数は、1つ下の段へ進むたびに同じ数が掛かる等比数列で、この掛かる数を公比という。等比数列の和は、公比が1より小さければ最初の項で、1より大きければ最後の項でほぼ決まる。

式で確かめる

道すじは3段ある。段ごとの手数を足して等比数列の和にし（手順1〜4）、公比$r$の大きさで3通りに分けて和を見積もり（手順5〜8）、最後に$r$と1の比べ方を、$d$と${\log }_{b}a$の比べ方に直す（手順9〜11）。簡単のため、$n$は$b$の累乗で、大きさ1の問題は1回で解け、つなぐ手数はちょうど$n^d$回とする。

1. 段$k$にある問題の数と、1つの大きさを書く

   $$\text{問題の数 }{a}^k,\text{大きさ }\frac{n}{b^k}$$

2. 段$k$の問題$a^k$個の手数を足す

   $$a^k{\left(\frac{n}{b^k}\right)}^d$$

3. $n^d$を前に出し、残りを$k$乗の形にまとめる

   $$=n^d\frac{a^k}{(b^d{)}^k}=n^d{\left(\frac{a}{b^d}\right)}^k=n^d{r}^k$$

4. 段0から最後の段$L$までを足す

   $$T(n)=n^d\left(1+r+r^2+\cdots +r^L\right)$$

ここで$r=\frac{a}{b^d}$は段から段への公比、$L$は$n$を$b$で何回割ると1になるかを表す数で、$b^L=n$となる。このような$L$を${\log }_{b}n$と書き、「$b$を何乗すると$n$になるか」を表す。$n=8$、$b=2$なら$L=3$で、木は段0から段3までの4段になる。

マージソートの$n=8$（$a=2$、$b=2$、$d=1$）で段1を計算すると、$2^1\times {\left(\frac{8}{2}\right)}^1=8$回で、木の図の段1と合う。公比は$r=\frac{2}{2}=1$なので、どの段も$8\times 1^k=8$回である。手数に定数を掛けても、$\Theta$の答えは変わらない。

5. $r<1$なら、かっこの中は1以上で$\frac{1}{1-r}$より小さい

   $$n^d\le T(n)<\frac{n^d}{1-r}$$

6. $r=1$なら、かっこの中は1が$L+1$個

   $$T(n)=n^d({\log }_{b}n+1)=\Theta (n^d\log n)$$

7. $r>1$なら、かっこの中は最後の項$r^L$以上で、その$\frac{r}{r-1}$倍より小さい

   $$r^L\le 1+r+\cdots +r^L<\frac{r}{r-1}{r}^L$$

8. 最後の段の手数$n^d{r}^L$に$b^L=n$を使う

   $$n^d{r}^L=n^d\frac{a^L}{(b^L{)}^d}=n^d\frac{a^L}{n^d}=a^L$$

手順5の両側はどちらも$n^d$の定数倍なので、$T(n)=\Theta (n^d)$である。手順5と7の倍率$\frac{1}{1-r}$と$\frac{r}{r-1}$は、公比0.5でも公比2でも2になり、等比数列の図の「2倍」はこの数だ。

手順6の${\log }_{b}n$は、$b$（底という）を替えても定数倍しか変わらないので、$\Theta$の中では底を書かない。手順8の$a^L$は最後の段にある問題の数、つまり木の葉の数で、$r>1$では葉の数が手数を決める。

累乗の対数は、指数を前に出した掛け算になる。たとえば${\log }_2{8}^2={\log }_{2}64=6$で、これは$2\times {\log }_{2}8=2\times 3$と等しい。

9. 2つの数の${\log }_b$をとって比べる

   $$\begin{array}{rl}{\log }_b\left(a^{{\log }_{b}n}\right)& ={\log }_{b}n\cdot {\log }_{b}a\\ & ={\log }_b\left(n^{{\log }_{b}a}\right)\end{array}$$

10. 対数が等しいので、元の数も等しい

    $$T(n)=\Theta \left(a^{{\log }_{b}n}\right)=\Theta \left(n^{{\log }_{b}a}\right)$$

11. $r<1$の両辺に$b^d$を掛けてから${\log }_b$をとる

    $$r<1⟺a<b^d⟺{\log }_{b}a<d$$

同じように、$r=1$は$d={\log }_{b}a$に、$r>1$は$d<{\log }_{b}a$にあたる。手順5、6、10の答えが、マスター定理の3つの場合である。

ただ、ここで示したのは、つなぐ手数が$n^d$の形をしているときの簡単な版である。教科書の一般の形では、つなぐ手数を任意の式$f(n)$で書き、$f(n)$が$n^{{\log }_{b}a}$より十分速く増える場合には、$af(n/b)\le cf(n)$（$c<1$）という条件を付け加える。