Design-and-analysis-of-algorithms-divide-conquer

DAA-分割統治

多くのアルゴリズムは、サブ問題を再帰的に処理する特定の問題を解決するために、本質的に再帰的です。

• 分割統治アプローチ*では、問題は小さな問題に分割され、次に小さな問題が個別に解決され、最後に小さな問題の解決策が大きな問題の解決策に結合されます。

一般的に、分割統治アルゴリズムには3つの部分があります-

• *問題を、同じ問題の小さなインスタンスであるいくつかのサブ問題に分割します。
• *サブ問題を再帰的に解決して、サブ問題を克服します。 それらが十分に小さい場合、サブケースを基本ケースとして解決します。
• *サブ問題の解決策*を組み合わせて、元の問題の解決策にします。

分割統治アプローチの長所と短所

サブ問題は独立しているため、分割統治アプローチは並列性をサポートします。 したがって、この手法を使用して設計されたアルゴリズムは、マルチプロセッサシステムまたは異なるマシンで同時に実行できます。

このアプローチでは、ほとんどのアルゴリズムが再帰を使用して設計されているため、メモリ管理が非常に高くなります。 関数の状態を保存する必要がある再帰的な関数スタックが使用されます。

分割統治アプローチの適用

以下に、分割統治アプローチを使用して解決されるいくつかの問題を示します。

• 数列の最大値と最小値を見つける
• Strassenの行列乗算
• ソートをマージ
• 二分検索