Divide and Conquer
分割統治は問題を独立な部分問題に分割し、再帰的に解いて結果を統合する手法であり、その計算量はマスター定理で解析できることが多い。
目的
マージソートや高速フーリエ変換など、効率的なアルゴリズムを設計するための一般的パラダイムを提供する。
メカニズム
3 ステップ：分割（部分問題へ分割）、統治（部分問題を再帰的に解決）、統合（部分解を併合）。マスター定理により T(n)=aT(n/b)+f(n) の漸近的評価を得る。古典例：マージソート O(n log n)、FFT O(n log n)。
ユースケース
- アルゴリズム設計
- ソートと探索
- 多項式どうしの乗算