12.5 まとめ
- 分割統治は一般的なアルゴリズム設計戦略で、分割（分割）と統治（マージ）の2つの段階から構成され、一般的に再帰を使用して実装されます。
- 問題が分割統治アプローチに適しているかどうかを判断するために、問題が分解可能かどうか、部分問題が独立しているかどうか、部分問題をマージできるかどうかを確認します。
- マージソートは分割統治戦略の典型的な例です。配列を再帰的に2つの等しい長さの副配列に分割し、1つの要素のみが残るまで続け、次にこれらの副配列を層ごとにマージしてソートを完了します。
- 分割統治戦略の導入は、しばしばアルゴリズムの効率を向上させます。一方では操作数を減らし、他方では分割後のシステムの並列最適化を促進します。
- 分割統治は多数のアルゴリズム問題に適用でき、データ構造とアルゴリズム設計で広く使用され、多くのシナリオに現れます。
- 総当たり検索と比較して、適応検索はより効率的です。時間計算量が \(O(\log n)\) の検索アルゴリズムは、通常分割統治戦略に基づいています。
- 二分探索は分割統治戦略のもう一つの古典的な応用です。部分問題の解のマージを含まず、再帰的な分割統治アプローチで実装できます。
- 二分木構築問題では、木の構築（元の問題）を左の部分木と右の部分木の構築（部分問題）に分割できます。これは前順走査と中順走査のインデックス範囲を分割することで実現できます。
- ハノイの塔問題では、サイズ \(n\) の問題をサイズ \(n-1\) の2つの部分問題とサイズ \(1\) の1つの部分問題に分解できます。これら3つの部分問題を順次解決することで、元の問題が解決されます。