12.5 まとめ
1. 要点の振り返り
- 分割統治法は一般的なアルゴリズム設計戦略であり、分（分割）と治（統合）の 2 つの段階からなり、通常は再帰に基づいて実装されます。
- それが分割統治法の問題かどうかを判断する基準には、問題を分解できるか、部分問題が独立しているか、部分問題を統合できるかが含まれます。
- マージソートは分割統治法の典型的な応用であり、配列を再帰的に同じ長さの 2 つの部分配列に分割し、要素が 1 つだけになるまで続け、その後で各層を順に統合してソートを完了します。
- 分割統治法を導入すると、多くの場合アルゴリズムの効率を高められます。一方では操作回数が減り、他方では分割後にシステムの並列最適化を行いやすくなります。
- 分割統治法は多くのアルゴリズム問題を解決できるだけでなく、データ構造やアルゴリズム設計にも広く応用されており、至る所でその姿を見ることができます。
- 総当たり探索と比べて、適応的な探索のほうが効率的です。時間計算量が \(O(\log n)\) の探索アルゴリズムは、通常は分割統治法に基づいて実装されます。
- 二分探索は分割統治法のもう 1 つの典型的な応用であり、部分問題の解を統合する手順を含みません。再帰的な分割統治によって二分探索を実現できます。
- 二分木を構築する問題では、木の構築（元の問題）を左部分木と右部分木の構築（部分問題）に分けられます。これは、先行順序走査と中間順序走査のインデックス区間を分割することで実現できます。
- ハノイの塔の問題では、規模 \(n\) の問題を、規模 \(n-1\) の 2 つの部分問題と規模 \(1\) の 1 つの部分問題に分けられます。これら 3 つの部分問題を順に解くと、元の問題も解決されます。