22.5 再帰方程式の勘どころ

これまでに私たちは再帰方程式の解を推測・検証し、定義を代入し、特性方程式の根を見つけ、定積分を計算し、指数方程式と線形再帰方程式系を解いてきた。最後に一歩下がって、何か一般的な経験則が得られないか考えてみよう。再帰方程式を見るだけで解に関して何か分かることはないだろうか？

本章で解いた再帰方程式とその解を次にまとめる:

\[ \def\arraystretch{1.35}\begin{array}{l|ll} & \hspace{20pt} \text{再帰方程式} & \hspace{40pt}\text{解} \\ \hline \text{Hanoi の塔} & T_{n} = 2 T_{n-1} + 1 & T_{n} \sim 2^{n} \\ \text{マージソート} & T_{n} = 2 T_{n/2} + n - 1 & T_{n} \sim n \log n \\ \text{Hanoi の塔 (改変)} & T_{n} = 2 T_{n-1} + n & T_{n} \sim 2 \cdot 2^{n} \\ \text{Fibonacci 数} & T_{n} = T_{n-1} + T_{n-2} & T_{n} \sim (1.618\ldots)^{n+1} / \sqrt{5} \\ \end{array} \]

Hanoi の塔とマージソートの再帰方程式はよく似ているにもかかわらず、その解は大きく異なる点に注目してほしい。\(n = 64\) 要素のリストをマージソートするとき実行される比較は数百回に過ぎないのに対して、\(n = 64\) 枚の円盤の移動には \(10^{19}\) 以上のステップが必要になる！

この二つの再帰方程式を比較すると、いずれも解が相手より大きくなる要素と小さくなる要素を一つずつ持っている。Hanoi の塔の再帰方程式では再帰的に呼び出される小問題のサイズが \(n-1\) と大きいのに対して、それ以外に足される値が \(1\) と小さい。マージソートの再帰方程式では再帰的に呼び出される小問題のサイズが \(n/2\) と小さいのに対して、それ以外に足される値が \(n - 1\) と大きい。この事実があるにもかかわらず、マージソートの方が圧倒的に速く実行できる！

この観察から、再帰的アルゴリズムを高速化するには、再帰呼び出し以外の処理を少なくするよりも、再帰的に呼び出される小問題を小さくする方がずっと重要であることが示唆される。例えば、改変された Hanoi の塔の再帰方程式では再帰的呼び出し以外の処理に対応する項が \(+1\) から \(+n\) に変更されるものの、解は \(2\) 倍にしかならない。あるいは、Fibonacci 数の再帰方程式では一つの小問題のサイズがほんの少し (\(n-1\) から \(n-2\) に) 小さくなっただけであるにもかかわらず、解は指数的に小さくなる！一般に、典型的な線形再帰方程式は小問題のサイズが大きいために解が指数的になり、典型的な分割統治型再帰方程式は小問題のサイズが小さいために解が多項式で抑えられることが多い。

上記の再帰方程式は全てサイズ \(n\) の問題を二つの小問題に分割する。小問題の個数が増えると解はどのように変化するだろうか？例えば、Hanoi の塔の再帰方程式における小問題の個数を \(2\) から \(3\) に変えたとする:

\[ T_{n} = 3 T_{n-1} + 1 \]

このとき特性方程式の解は \(2\) から \(3\) になり、漸近解は \(\Theta(2^{n})\) から \(\Theta(3^{n})\) へ指数的に増加する。

分割統治型再帰方程式の解も小問題の個数によって大きく変化する。例えば、マージソートの再帰方程式を一般化した次の再帰方程式を考える:

\[ \begin{aligned} T_{1} &= 0 \\ T_{n} &= a T_{n/2} + n - 1 \end{aligned} \]

Akra-Bazzi の公式からは次の関係が分かる:

\[ T_{n} = \begin{cases} \Theta(n) & (a < 2) \\ \Theta(n \log n) & (a = 2) \\ \Theta(n^{\log a}) & (a > 2) \\ \end{cases} \]

\(a\) の値を \(1.99\) から \(2.01\) に変化させると、解は三つの全く異なる関数に変化する！

境界条件は再帰方程式の解にどのような影響を及ぼすだろうか？先述したように、分割統治型再帰方程式では境界条件が漸近解に影響することはまずない。線形再帰方程式では、最も大きな項は指数関数であり、その底は小問題の個数とサイズから決定される場合が多い。そのため、この指数関数の項の係数が \(0\) になるような境界条件があるときに限って漸近解は変化する。

これで経験則が手に入った！再帰的アルゴリズムの性能は再帰的に呼び出される小問題のサイズと個数によって決定され、再帰呼び出し以外の処理やベースケースの処理にかかる時間にはあまり影響を受けない。また、小問題のサイズと元の問題のサイズの差が定数なら、解は指数的になる可能性が高い。これに対して、小問題のサイズが元の問題のサイズに比例するなら、解は多項式で抑えられる場合が多い。