アルゴリズムと計算量の問題

マスター定理は、$T(n)=aT(n/b)+f(n)$（$a\geqq 1$, $b>1$）の形の漸化式について、$f(n)$ と $n^{{\log }_{b}a}$ の増え方を比べて $T(n)$ のオーダーを決める定理である。

手順1：$a$, $b$, $f(n)$ を読み取る。
$a=27$, $b=9$, $f(n)=n\sqrt{n}=n^{3/2}$ である。

手順2：$n^{{\log }_{b}a}$ を計算する。
$27=3^3$, $9=3^2$ なので ${\log }_{9}27=\frac{\log 27}{\log 9}=\frac{3\log 3}{2\log 3}=\frac{3}{2}$。よって $n^{{\log }_{b}a}=n^{3/2}$ である。

手順3：場合を判定する。
$f(n)=n^{3/2}=\Theta (n^{{\log }_{b}a})$ であり、$f(n)$ と $n^{{\log }_{b}a}$ は同じオーダーである。これはマスター定理の第2の場合にあたる。

手順4：結論。
第2の場合では $T(n)=\Theta (n^{{\log }_{b}a}\log n)$ なので $$T(n)=\Theta (n^{3/2}\log n)$$ である。対数の底の違いは定数倍にすぎないので、自然対数で書いてよい。よって $g(n)=n^{3/2}\log n$。

（確認）$n=9^k$ のとき $n^{3/2}=27^k$ なので、漸化式は $T(9^k)=27T(9^{k-1})+27^k$ となる。両辺を $27^k$ で割り $S_k=\frac{T(9^k)}{27^k}$ とおくと $S_k=S_{k-1}+1$, $S_0=T(1)=1$ より $S_k=k+1$。したがって $T(n)=27^k(k+1)=n^{3/2}({\log }_{9}n+1)$ となる。例えば $T(9)=27\cdot 1+27=54=27\cdot 2$ で一致する。${\log }_{9}n=\frac{\log n}{\log 9}$ なので、$T(n)=\Theta (n^{3/2}\log n)$ と確かめられる。

a=27, b=9 なので $n^{{\log }_{9}27}=n^{3/2}$ である（$9^{3/2}=27$）。分割・統合の時間 $f(n)=n\sqrt{n}=n^{3/2}$ はこれと同じオーダーなので、マスター定理の第2の場合にあたる。

直接計算で確かめる。$n=9^k$ とする。$T(n)=27T(n/9)+n^{3/2}$ の両辺を $n^{3/2}$ で割り、$U(k)=T(9^k)/(9^k{)}^{3/2}=T(9^k)/27^k$ とおく。$T(9^k)=27T(9^{k-1})+27^k$ より $U(k)=U(k-1)+1$、$U(0)=1$。したがって $U(k)=k+1$。
よって $T(n)=27^k(k+1)=n^{3/2}({\log }_{9}n+1)$ となる。
${\log }_{9}n=\log n/\log 9$ なので $T(n)=\Theta (n^{3/2}\log n)$。

検算：$k=1$ のとき $T(9)=27\cdot 1+27=54$。公式は $27\cdot 2=54$ で一致する。