Data-structures-algorithms-divide-and-conquer

データ構造-分割と征服

分割統治アプローチでは、手元の問題は小さな副問題に分割され、各問題は個別に解決されます。 サブ問題をさらに小さなサブ問題に分割し続けると、最終的には、それ以上分割できない段階に達する可能性があります。 それらの「アトミックな」最小のサブ問題（分数）は解決されます。 元の問題の解決策を得るために、すべての副問題の解決策が最終的にマージされます。

分割統治

概して、3段階のプロセスで「分割統治」アプローチを理解できます。

分割/分割

このステップでは、問題をより小さなサブ問題に分割します。 サブ問題は、元の問題の一部を表す必要があります。 このステップでは、一般に再帰的なアプローチを使用して、問題をさらに分割できるサブ問題がなくなるまで問題を分割します。 この段階では、サブ問題は本質的にアトミックになりますが、実際の問題の一部を表します。

征服/解決

このステップには、解決すべき小さな副次的な問題がたくさんあります。 一般に、このレベルでは、問題はそれ自体で「解決」されたと見なされます。

結合/結合

小さなサブ問題が解決されると、この段階では元の問題の解決策が定式化されるまで再帰的に結合されます。 このアルゴリズムのアプローチは再帰的に機能し、征服とマージのステップは非常に近いため、1つのように見えます。

例

次のコンピューターアルゴリズムは、*分割統治*プログラミングアプローチに基づいています-

• ソートのマージ
• クイックソート
• バイナリ検索
• Strassenの行列乗算
• 最も近いペア（ポイント）

コンピューターの問題を解決する方法はさまざまありますが、言及されているのは、分割統治アプローチの良い例です。