22.4 分割統治型再帰方程式

前節では任意の線形再帰方程式を解くためのレシピを説明した。しかし、第 22.2 節で考えたマージソートの最大比較回数 \(T(n)\) が満たす再帰方程式は線形でない:

\[ \begin{aligned} T(1) &= 0 \\ T(n) &= 2 T(n/2) + n - 1 \qquad (n \geq 2) \\ \end{aligned} \]

具体的に言えば、\(T(n)\) の値は直前の数項から決まるのではなく、半分だけ戻った \(T(n/2)\) の値に依存している。

マージソートは分割統治 (divide-and-conquer) アルゴリズムの例である: 入力を分割 (divide) し、それぞれの部分を個別に統治 (conquer, 征服) し、その結果を組み合わせて出力を得る。この種のアルゴリズムの解析では、次の形をした分割統治型再帰方程式 (divide-and-conquer recurrence) が頻繁に登場する:

\[ T(n) = \sum_{i=1}^{k} a_{i} T(b_{i}n) + g(n) \]

ここで \(a_{1}\), \(\ldots\), \(a_{k}\) は正の定数、\(b_{1}\), \(\ldots\), \(b_{k}\) は \([0,1)\) に属する定数、そして \(g(n)\) は非負関数を表す。例えば \(k = 1\), \(a_{1} = 2\), \(b_{1} = 1/2\), \(g(n) = n - 1\) と定めるとマージソートの再帰方程式が得られる。

22.4.1 Akra-Bazzi の公式

事実上全ての分割統治型再帰方程式に対する解は Akraアクラ-Bazziバッツィの公式 (Akra-Bazzi formula) と呼ばれる驚くべき結果によって与えられる。非常に単純なことに、一般的な分割統治型再帰方程式

\[ T(n) = \sum_{i=1}^{k} a_{i} T(b_{i}n) + g(n) \]

は次の漸近解 (asymptotic solution, 解が満たすシータ関係) を持つ:

\[ T(n) = \Theta \left( n^{p} \left( 1 + \int_{1}^{n} \frac{g(u)}{u^{p+1}} du \right) \right) \tag{22.2}\]

ここで \(p\) は次の等式を満たす定数である:

\[ \sum_{i=1}^{k} a_{i} b_{i}^{p} = 1 \tag{22.3}\]

ほとんど問題にならない前提条件として、\(g(n)\) が急速に大きくなる、または急速に振動することがあってはいけない。正確には、\(|g^{\prime} (n)|\) が何らかの多項式で抑えられる必要がある。例えば、Akra-Bazzi の公式は \(g(n) = x^{2} \log 2\) なら適用できるのに対して、\(g(n) = 2^{n}\) なら適用できない。

定義代入ではなく Akra-Bazzi の公式を使ってマージソートの再帰方程式をもう一度解いてみよう。まず、次の等式を満たす \(p\) を見つける必要がある:

\[ 2 \cdot \left( \frac{1}{2} \right)^{\! p} = 1 \]

\(p = 1\) とすれば等式は成り立つ。続いて定積分を含む式を計算する:

\[ \begin{aligned} T(n) &= \Theta \left( n \left( 1 + \int_{1}^{n} \frac{u - 1}{u^{2}} du \right) \right) \\[12pt] &= \Theta \left( n \left( 1 + \left[ \log u + \frac{1}{u} \right]_{1}^{n} \right) \right) \\[12pt] &= \Theta \left( n \left( \log n + \frac{1}{n} \right) \right) \\[12pt] &= \Theta (n \log n) \\ \end{aligned} \]

定積分を計算してから式を整理している。最後の式変形で \(1/n\) を無視できるのは、\(\log n\) の項が支配的になるためである。これで再帰方程式の漸近的な挙動が判明した！

次はもっと物騒な見た目の再帰方程式を考えてみよう:

\[ T(n) = 2 T(n/2) + (8/9) T(3n/4) + n^{2} \]

この再帰方程式では \(k = 2\), \(a_{1} = 2\), \(b_{1} = 1/2\), \(a_{2} = 8/9\), \(b_{2} = 3/4\) である。よって \(p\) は次の等式を満たす必要がある:

\[ 2 \cdot (1/2)^{p} + (8/9) (3/4)^{p} = 1 \]

この形の方程式は閉形式の解を持たない場合もあるので、\(p\) を数値的に近似する必要があるかもしれない。ただ、この問題では \(p = 2\) という解がすぐに求まる。ここから次が分かる:

\[ \begin{aligned} T(n) &= \Theta \left( n^{2} \left( 1 + \int_{1}^{n} \frac{u^{2}}{u^{3}} du \right) \right) \\[10pt] &= \Theta (n^{2} (1 + \log n)) \\ &= \Theta (n^{2} \log n) \end{aligned} \]

見た目に反して解答は簡単に求まった！

22.4.2 二つの問題

ここまで言及してこなかった分割統治型再帰方程式に関する問題がいくつかある。ここで説明しよう。

まず、Akra-Bazzi の公式は境界条件を全く利用しない。その理由を理解するために、第 22.2.2 項でマージソートの再帰方程式を定義代入で解いたときのことを思い出してほしい。最終的に次の関係が導かれていた:

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

この式は第 \(n\) 番目の項を初項の関数として表しており、\(T_{1}\) の値は境界条件から定まる。しかし \(T_{1}\) がどんな値だったとしても \(T_{n} = \Theta(n \log n)\) は必ず成り立つ点に注目してほしい。境界条件は漸近関係の正しさに影響しない！

これは典型的な状況である: 基本的に分割統治型再帰方程式の漸近解は境界条件に依存しない。直感的な説明は次の通りである: 再帰アルゴリズムの最も下のレベルで実行される基本操作にかかる時間が \(2\) 倍になれば、全体の実行時間も最大で \(2\) 倍になる。これは現実の問題を解く上では重要な違いを生むものの、漸近関係を考えるとき定数 \(2\) による乗算は無視できる。よって漸近解は変化しない。ただし例外もある。例えば \(T(n) = 2 T(n/2)\) は \(T(1) \neq 0\) なら漸近解 \(\Theta(n)\) を持ち、\(T(1) = 0\) なら解 \(0\) を持つ。しかし、こういったケースは実用的な意味に乏しいので、以降では考えない。

続いて、線形再帰方程式では考える必要のなかった分割統治型再帰方程式に特有の問題が一つある: \(n\) を整数で割るので、一部の場合で \(n\) が非整数になる。例えば、マージソートの再帰方程式には \(T(n/2)\) という項が含まれる。\(n\) が \(15\) のときはどうすればいいのだろうか？ \(7.5\) 個の要素をソートするのにかかる時間を求めるのだろうか？以前にマージソートの再帰方程式を解いたときは入力のサイズが \(2\) の冪と仮定し、この問題を回避していた。しかし、そうするとサイズが例えば \(100\) のとき起こることについては何も言えない。厳密な議論をするには、再帰方程式を次のように改変する必要がある:

\[ \begin{aligned} T(1) &= 0 \\ T(n) &= T(\left\lceil n/2 \right\rceil) + T(\left\lfloor n/2 \right\rfloor) + n - 1 \qquad (n \geq 2) \end{aligned} \]

こうすれば厳密になるものの、天井関数と床関数によって正確な解の計算は難しくなる。

しかし幸いにも、基本的に分割統治型再帰方程式の漸近解は天井関数と床関数の影響を受けない。さらに正確に言えば、\(T(b_{i} n)\) を \(T (\left\lceil b_{i} n \right\rceil)\) または \(T (\left\lfloor b_{i} n \right\rfloor)\) に置き換えたとしても漸近解は変化しない。よって漸近解を考えるときは分割統治型再帰方程式から天井関数と床関数を自由に除去して構わない。

22.4.3 Akra-Bazzi の定理

等式 \(\text{(22.2)}\) が示す Akra-Bazzi の公式、そして上述の境界条件や整数性に関する事実は全て次の Akra-Bazzi の定理から従う:

定理 22.4.1[Akraアクラ-Bazziバッツィの定理 (Akra-Bazzi theorem)]

\(T \colon \mathbb{R} \to \mathbb{R}\) が非負関数かつ \(0 \leq x \leq x_{0}\) で有界であり、\(T\) が次の再帰方程式を満たすと仮定する:

\[ T(x) = \sum_{i=1}^{k} a_{i} T(b_{i}x + h_{i}(x)) + g(x) \qquad (x > x_{0}) \tag{22.4}\]

さらに、次の条件が成り立つとする:

\(x_{0}\) は十分に大きく、\(T\) は well-defined である。
\(a_{1}\), \(\ldots\), \(a_{k}\) は正の定数である。
\(b_{1}\), \(\ldots\), \(b_{k}\) は \([0,1)\) に属する定数である。
\(g(x)\) は非負関数であり、\(|g^{\prime}(x)|\) は多項式で抑えられる。
\(|h_{i}(x)| = O(x / \log^{2} x)\)

このとき、次の関係が成り立つ:

\[ T(x) = \Theta \left( x^{p} \left( 1 + \int_{1}^{x} \frac{g(u)}{u^{p+1}} du \right) \right) \]

ただし \(p\) は次の制約を満たす:

\[ \sum_{i=1}^{k} a_{i} b_{i}^{p} = 1 \]

Akra-Bazzi の定理は数学的帰納法を使った複雑な議論で証明されるが、本書では証明を省略する。ただ、せめて定理が主張することの確認はしておこう。

これまでに考えてきた再帰方程式の解はどれも整数を取る関数だった。これはよくあるケースであるものの、Akra-Bazzi の定理はさらに一般的であり、実数を取る関数にも適用できる。

Akra-Bazzi の公式と Akra-Bazzi の定理を比べると、後者にだけ関数 \(h_{i}\) が存在することが分かる。この \(h_{i}\) を利用すると、天井関数や床関数といった小問題のサイズに対する小さな補正がある再帰方程式にも定理を適用できる。例えば、次のように定数を設定したとする:

\[ \begin{aligned} a_{1} &= 1 &\qquad b_{1} &= 1/2 &\quad h_{1}(x) &= \left\lfloor x/2 \right\rfloor - x/2 \\[10pt] a_{2} &= 1 &\qquad b_{2} &= 1/2 &\quad h_{2}(x) &= \left\lceil x/2 \right\rceil - x/2 \\[10pt] & & g(x) &= x - 1 & & \end{aligned} \]

これは次の再帰的方程式に対応する:

\[ \begin{aligned} T(x) &= 1 \cdot T \left( x/2 + \left( \left\lfloor x/2 \right\rfloor - x/2 \right) \right) + 1 \cdot T \left( x/2 + \left( \left\lceil x/2 \right\rceil - x/2 \right) \right) + x - 1 \\[10pt] &= T \left( \left\lfloor x/2 \right\rfloor \right) + T \left( \left\lceil x/2 \right\rceil \right) + x - 1 \end{aligned} \]

これは全ての入力サイズに対して成り立つ厳密に正確なマージソートの再帰方程式である。\(h_{1}(x)\) と \(h_{2}(x)\) はいずれも \(1\) 以下なので、Akra-Bazzi の定理が課す \(O(x/\log^{2} x)\) という条件は容易に満たされる。これらの関数 \(h_{1}\), \(h_{2}\) は再帰方程式の漸近解に影響しない (そもそも式に含まれない) ので、以前に述べた「分割統治型再帰方程式では、小問題のサイズに天井関数や床関数を適用しても漸近解が変化しない」という主張がこれで正当化される。

22.4.4 Master 定理

Akra-Bazzi の公式には Masterマスター定理 (Master theorem) と呼ばれる有名な特殊ケースが存在し、この定理だけでも情報科学でよく登場する様々な再帰方程式を解くことができる。「Master」定理という大仰な名前で呼ばれるのには理由がある: Akra と Bazzi が現れるよりずっと前に証明されたこの結果は、分割統治型再帰方程式の求解問題に対する最後の一撃だと長く考えられていた。ここで Master 定理を紹介するのは、アルゴリズムの講義で言及されることがあり、積分を計算しなくても使用できるからである。

定理 22.4.2[Masterマスター定理 (Master theorem)]

関数 \(T\) が次の形をした再帰方程式を満たすとする:

\[ T(n) = a\,T (n/b) + g(n) \]

ある定数 \(\varepsilon > 0\) で \(g(n) = O(n^{\log_{b}a - \varepsilon})\) なら、次の関係が成り立つ:

\[ T(n) = \Theta \hspace{-2pt} \left( n^{\log_{b}a} \right) \]
ある定数 \(k \geq 0\) で \(g(n) = \Theta (n^{\log_{b}a} \log^{k} n)\) なら、次の関係が成り立つ:

\[ T(n) = \Theta \hspace{-2pt} \left( n^{\log_{b}a} \log^{k+1} n \right) \]
ある定数 \(\varepsilon > 0\) で \(g(n) = \Omega(n^{\log_{b}a + \varepsilon})\) で、ある定数 \(c < 1\) と十分大きな \(n\) で \(ag(n/b) < c g(n)\) なら、次の関係が成り立つ:

\[ T(n) = \Theta(g(n)) \]

Master 定理は \(n\) に関する数学的帰納法で証明できる。また、定理 22.4.1 の系として簡単に示すこともできる。証明の詳細は省略する。