パターン
マージソートとクイックソートで見てきた三段階のパターンは分割統治 (devide-and-conquer)と呼ばれます:
- 与えられた問題のインスタンスを同じ問題の独立したより小さいインスタンスに分割する (devide)。
- 小さいインスタンスを再帰の妖精に任せる (delegate)。
- 小さいインスタンスの答えを元のインスタンスの答えになるよう組み合わせる (combine)。
インスタンスのサイズがある定数よりも小さくなったら、再帰的な処理をやめ、問題を直接解きます。問題を直接解くのは総当たりで、定数時間で行われます。
分割統治法のアルゴリズムが正しいことを示すときにはほとんど常に帰納法が使われます。また実行時間の解析には再帰方程式を解く必要がありますが、再帰木を使えば通常は解くことができます (残念ながらいつも解けるとは限りませんが！)。