## 定義 分割統治(divide-and-conquer)とは、サイズnの問題を複数の小さな部分問題に分割し、各部分問題を再帰的に解いてから結果を統合するアルゴリズム設計手法である。マージソートが典型例で、リストを前半・後半に分割してそれぞれ再帰的にソートしたのち、2つのソート済みリストをマージして統合する。分割統治アルゴリズムの実行時間解析は**分割統治漸化式(divide-and-conquer recurrence)**という形の式に帰着する。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 21 Recurrences]] §21.2, §21.4) 分割統治漸化式は次の形をとる。 T(n) = Σ_{i=1}^{k} ai T(bi n) + g(n) ここでa1, ..., akは正の定数、b1, ..., bkは0と1の間の定数、g(n)は非負関数である。[[漸化式]]concept文書が扱う線形漸化式(T(n)が固定個数の直前の項の線形結合)とは異なり、T(n)はnから離れた項T(bi n)(nの定数倍だけ小さい項)の関数である点が本質的な違いである。マージソートの比較回数の漸化式Tn = 2Tn/2 + n - 1は、a1 = 2, b1 = 1/2, g(n) = n - 1と置くことでこの形に一致する。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 21 Recurrences]] §21.4) **Akra-Bazziの公式**は、分割統治漸化式のほぼすべてに適用できる漸近解の公式である。Σ ai bi^p = 1を満たす定数pを求めたうえで、 T(n) = Θ(n^p (1 + ∫₁ⁿ g(u)/u^(p+1) du)) として漸近解が得られる。g(n)の導関数|g'(n)|が多項式で抑えられるという穏やかな条件のもとで成り立つ(Akra-Bazziの定理、定理21.4.1)。この公式は境界条件を一切使わない点が特徴で、分割統治漸化式の漸近解は境界条件にほぼ依存しない(境界条件が支配項の係数をちょうどゼロにする例外的な場合を除く)。また、部分問題サイズに床(floor)・天井(ceiling)を適用しても(非整数サイズの補正)、その補正項hi(x)が|hi(x)| = O(x/log²x)という穏やかな条件を満たす限り漸近解は変化しない。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 21 Recurrences]] §21.4.1〜§21.4.3) **マスター定理(Master Theorem)**は、T(n) = aT(n/b) + g(n)という単一項の分割統治漸化式に限定したAkra-Bazziの公式の特殊ケースである。g(n)をn^(log_b a)と比較し、(1) g(n)がn^(log_b a)より真に遅ければT(n) = Θ(n^(log_b a))、(2) g(n) = Θ(n^(log_b a) log^k n)ならT(n) = Θ(n^(log_b a) log^(k+1) n)、(3) g(n)がn^(log_b a)より真に速く、かつag(n/b) ≤ cg(n)(c<1)という正則性条件を満たせばT(n) = Θ(g(n))、という3ケースに場合分けしてΘ解を与える。Akra-Bazziの公式より前から知られていた歴史的経緯から、積分を扱わずに済む簡便な特殊ケースとしてアルゴリズム論の授業で広く使われる。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 21 Recurrences]] §21.4.4) 分割統治漸化式の解の増大率を決める主因は、1回あたりの追加作業g(n)ではなく部分問題のサイズと個数である。部分問題の個数aが2から3へ増えるだけで、Tn = aTn/2 + n - 1の解はΘ(n)(a<2)・Θ(n log n)(a=2)・Θ(n^(log a))(a>2)という質的に異なる3形態に分岐する。この感度は[[漸化式]]concept文書が扱う線形漸化式(特性方程式の根の個数がそのまま指数の底になる)にも共通する現象である。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 21 Recurrences]] §21.5) ## 横断的知見 - Akra-Bazziの公式・マスター定理はいずれも解をΘ記法(big Theta)で表現する。第13章が定義するΘ(f=O(g) かつ g=O(f)、定数因子の範囲で等しいことを表す)の定義がそのまま踏襲されており、第13章末尾の未解決の問い「漸近記法とアルゴリズムの計算量解析との接続」に、分割統治漸化式の解析という具体的な接続先を与える。特に第13章はΘが「n が2倍になったとき実行時間がおおむね何倍になるかというスケーラビリティの情報を保持する」と述べていたが、第21章のマージソート(Θ(n log n))対ハノイの塔(Θ(2^n))の対比は、この係数レベルの精度ではなく増大のクラスそのもの(多項式 対 指数関数)を区別する場面でΘが使われることを示しており、両者は異なる粒度の主張であることが分かる。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 21 Recurrences]] §21.4, §21.5, [[@2015__MIT__Mathematics for Computer Science - Chapter 13 Sums and Asymptotics]] §13.7.3) ## 未解決の問い - Akra-Bazziの定理(定理21.4.1)の証明は「複雑な帰納法による」とだけ述べられ、本章では詳細が割愛されている。証明の骨格(積分と帰納法をどう組み合わせるか)を扱う別ソースがあれば補強したい。 - マスター定理のケース3にある正則性条件(regularity condition、ag(n/b) ≤ cg(n))が具体的にどのような分割統治アルゴリズムで破れるか、本章は例を挙げていない。反例となるアルゴリズムを扱う他ソースがあれば追記したい。 - 分割統治漸化式は本章では実行時間解析(比較回数)の文脈でのみ扱われるが、並列アルゴリズムの計算量解析(スパン・ワークのような別の指標)でも同型の漸化式が現れるはずである。並列アルゴリズムを扱う他ソースがingestされたら、この接続を確認したい。 ## 関連 - source: [[@2015__MIT__Mathematics for Computer Science - Chapter 21 Recurrences]] - 概念: [[漸化式]](分割統治漸化式の線形な姉妹形態、特性方程式による解法) / [[漸近記法]](Akra-Bazziの公式・マスター定理の解を表現するΘ記法の定義元) ## 出典 - Eric Lehman, F. Thomson Leighton, Albert R. Meyer, *Mathematics for Computer Science*, revised 2015-05-18, Chapter 21, §21.2, §21.4〜§21.5.