分割統治アルゴリズム 複雑な問題をより小さく管理しやすい部分に分割し、各部分を個別に解決し、その後、解決策を組み合わせて元の問題を解決する問題解決戦略です。これは、コンピューター科学と数学で広く使用されているアルゴリズム手法です。
例： の中に マージソート アルゴリズム、 分割統治 Strategy は要素のリストを並べ替えるために使用されます。下の図は、配列をソートするための分割と結合の状態を示しています。 マージソート 。
目次
分割統治アルゴリズムとは何ですか?
分割統治は、より大きな問題を部分問題に分割し、部分問題を個別に解決し、それらの部分問題の解決策を組み合わせてより大きな問題の解決策を得る問題解決手法です。
分割統治アルゴリズムの段階:
分割統治アルゴリズムは 3 つの段階に分けることができます。 分ける 、 征服する そして マージ 。
1. 分割:
- 元の問題をより小さなサブ問題に分割します。
- 各サブ問題は、問題全体の一部を表す必要があります。
- 目標は、それ以上分割できなくなるまで問題を分割することです。
2. 征服する:
- 小さなサブ問題をそれぞれ個別に解決します。
- 部分問題が十分に小さい場合 (基本ケースと呼ばれることが多い)、それ以上再帰せずに直接解決します。
- 目標は、これらの部分問題の解決策を個別に見つけることです。
3. マージ:
- サブ問題を結合して、問題全体の最終的な解決策を取得します。
- 小さな部分問題が解決されたら、それらの解決策を再帰的に組み合わせて、より大きな問題の解決策を取得します。
- 目標は、部分問題の結果を結合して、元の問題の解決策を定式化することです。
分割統治アルゴリズムの応用:
- 並べ替えを結合: マージ ソートは、分割統治ソート アルゴリズムの典型的な例です。配列を小さなサブ配列に分割し、個別にソートしてから、それらをマージしてソートされた配列を取得します。
- 結果の中央値: 一連の数値の中央値は、分割統治アプローチを使用して見つけることができます。セットをより小さなサブセットに再帰的に分割することにより、中央値を効率的に決定できます。
- 最小値と最大値の検出結果: 分割統治アルゴリズムを使用すると、配列内の最小要素と最大要素の両方を同時に見つけることができます。配列を半分に分割し、それぞれの半分の最小値と最大値のペアを比較することで、全体の最小値と最大値を対数時間計算量で特定できます。
- 行列の乗算: ストラッセンの行列乗算アルゴリズムは、行列をより小さな部分行列に分割し、その積を結合することで、大きな行列に必要な乗算の数を減らす分割統治手法です。
- 最近接ペアの問題: 最近接ペア問題には、多次元空間内の一連の点の中から最も近い 2 つの点を見つけることが含まれます。分割統治アルゴリズム (分割統治最近傍ペア アルゴリズムなど) は、点を再帰的に分割し、部分問題からの解を結合することで、この問題を効率的に解決できます。
分割統治アルゴリズムの基本:
- 分割統治の概要
- 動的プログラミング vs 分割統治
- 減少と征服
- 分割統治の反復のための高度なマスター定理
標準アルゴリズムがオン 分割統治アルゴリズム :
- 二分探索
- マージソート
- クイックソート
- pow(x, n) を計算します。
- 高速乗算のためのカラツバアルゴリズム
- ストラッセンの行列乗算
- 凸包 (単純な分割統治アルゴリズム)
- 凸包用の Quickhull アルゴリズム
二分探索ベースの問題:
- 指定された配列内のピーク要素を検索します
- ソートされた配列内の多数決要素をチェックする
- 2 つのソートされた配列の K 番目の要素
- ゼロの数を調べる
- Rotated Sorted 配列の回転数を見つける
- 単調増加関数が初めて正になる点を見つける
- ソートされた 2 つの配列の中央値
- サイズの異なる 2 つの並べ替えられた配列の中央値
- 二分探索を使用したペインターの分割問題
練習問題 分割統治アルゴリズム :
- 整数の平方根
- 最小比較数を使用した配列の最大値と最小値
- 限られた範囲の配列内の各要素の頻度を O(n) 時間未満で見つけます
- タイリングの問題
- 反転数のカウント
- スカイライン問題
- 行方向および列方向にソートされた 2D 配列での検索
- 最小ページ数を割り当てる
- べき乗剰余演算 (剰余演算におけるべき乗)
クイックリンク ：
- データ構造とアルゴリズムを学ぶ | DSA チュートリアル
- 分割統治に関する「練習問題」
- 分割統治に関する「クイズ」