分割統治はアルゴリズム パターンです。アルゴリズム手法では、設計は、巨大な入力に関する議論を取り上げ、入力を小さな部分に分割し、小さな部分のそれぞれについて問題を決定し、次に区分的な解決策をグローバルな解決策にマージすることです。この問題を解決するメカニズムは、分割統治戦略と呼ばれます。
分割統治アルゴリズムは、次の 3 つのステップによる紛争で構成されます。
| 分ける | 元の問題を一連のサブ問題に分割します。
| 征服する: | すべてのサブ問題を個別に再帰的に解決します。
| 組み合わせる： | 部分問題の解決策を組み合わせて、問題全体の解決策を導き出します。
一般に、次のようにすることができます。 分割統治 3 段階のプロセスでアプローチします。
例: 特定のコンピューター アルゴリズムは、分割統治アプローチに基づいています。
- 最大値と最小値の問題
- 二分探索
- ソート（マージソート、クイックソート）
- ハノイの塔。
分割統治戦略の基本:
分割統治戦略には 2 つの基本があります。
- 関係式
- 停止条件
1. 関係式: それは与えられた技術から生成される公式です。フォーミュラの生成後、D&C 戦略を適用します。つまり、問題を再帰的に分割し、分割された部分問題を解決します。
2. 停止条件: 分割統治戦略を使用して問題を解決する場合、どのくらいの期間分割統治を適用する必要があるかを知る必要があります。したがって、D&C の再帰ステップを停止する必要がある条件は、停止条件と呼ばれます。
分割統治アプローチの応用:
次のアルゴリズムは、分割統治手法の概念に基づいています。
| 二分探索: | 二分探索アルゴリズムは、半区間探索や対数探索とも呼ばれる探索アルゴリズムです。これは、ターゲット値とソートされた配列内に存在する中央の要素を比較することによって機能します。比較を行った後、値が異なる場合は、ターゲットを含めることができない半分が最終的に除外され、残りの半分の検索が続行されます。もう一度真ん中の要素を検討し、目標値と比較します。このプロセスは、目標値が達成されるまで繰り返されます。検索終了後に残りの半分が空であることが判明した場合は、ターゲットが配列内に存在しないと結論付けることができます。
| クイックソート: | これは最も効率的なソート アルゴリズムであり、パーティション交換ソートとも呼ばれます。まず配列からピボット値を選択し、続いて残りの配列要素を 2 つのサブ配列に分割します。パーティションは、各要素をピボット値と比較することによって作成されます。要素がピボットより大きい値を保持しているか小さい値を保持しているかを比較し、配列を再帰的に並べ替えます。
| 並べ替えを結合: | これは、比較を行うことによって配列を並べ替える並べ替えアルゴリズムです。まず配列をサブ配列に分割し、各サブ配列を再帰的に並べ替えます。並べ替えが完了したら、それらをマージして戻します。
| 最も近い点のペア: | 計算幾何学の問題です。このアルゴリズムは、n 個の点が与えられた場合に、点のペア間の距離が最小になるように、距離空間内で最も近い点のペアを見つけることに重点を置いています。
| ストラッセンのアルゴリズム: | これは、Volker Strassen にちなんで名付けられた行列乗算のアルゴリズムです。大規模な行列を処理する場合、従来のアルゴリズムよりもはるかに高速であることが証明されています。
| Cooley-Tukey 高速フーリエ変換 (FFT) アルゴリズム: | 高速フーリエ変換アルゴリズムは、J. W. Cooley と John Turkey にちなんで命名されました。これは分割統治アプローチに従い、O(nlogn) の複雑さを課します。
| 高速乗算のためのカラツバアルゴリズム: | これは、伝統的な時代の最速の乗算アルゴリズムの 1 つで、1960 年末にアナトリー カラツバによって発明され、1962 年に公開されました。この方法では、2 つの n 桁の数値を最大でも 1 桁に減らすことで乗算します。
分割統治の利点
- 分割統治は、数学パズルであるハノイ塔などの最大の問題の 1 つをうまく解決する傾向があります。基本的なアイデアのない複雑な問題を解決するのは困難ですが、分割統治アプローチを利用すると、主要な問題を 2 つに分割して再帰的に解決できるため、労力が軽減されます。このアルゴリズムは他のアルゴリズムよりもはるかに高速です。
- 低速なメイン メモリにアクセスする代わりにキャッシュ メモリ内で単純なサブ問題を解決するため、多くのスペースを占有することなくキャッシュ メモリを効率的に使用します。
- これは、対応するブルート フォース テクニックよりも熟練しています。
- これらのアルゴリズムは並列処理を禁止するため、変更を必要とせず、並列処理を組み込んだシステムで処理されます。
分割統治のデメリット
- そのアルゴリズムのほとんどは再帰を組み込んで設計されているため、高度なメモリ管理が必要になります。
- 明示的なスタックはスペースを過剰に使用する可能性があります。
- CPU 内に存在するスタックよりも厳密に再帰が実行されると、システムがクラッシュする可能性もあります。
