DAA-分割統治

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

に divide and conquer approach、問題を小さな問題に分割し、小さな問題を個別に解決し、最後に小さな問題の解決策を組み合わせて大きな問題の解決策にします。

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

• Divide the problem 同じ問題のより小さなインスタンスであるいくつかのサブ問題に。

• Conquer the sub-problemsそれらを再帰的に解くことによって。それらが十分に小さい場合は、基本ケースとしてサブ問題を解決します。

• Combine the solutions 元の問題の解決策へのサブ問題に。

分割統治法の長所と短所

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

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

分割統治法の適用

以下は、分割統治法を使用して解決されるいくつかの問題です。

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