分割統治法とは何ですか？

問題を小さな部分問題に分割し、各部分を解いてから結果を統合するアルゴリズム設計手法。

分割統治法のポイントは？

分割（Divide）→ 解決（Conquer）→ 統合（Combine）の3ステップ。マージソート、クイックソート、二分探索が代表例。再帰的に問題を小さくしていくのが特徴。計算量をO(n²)からO(n log n)に改善できることが多い

【ぶんかつとうちほう】

💡 大きな問題を「分けて解いて合わせる」

📌 このページのポイント

分割統治法のイメージ

ひよこ

具体例で教えて？

ペンギン先生

マージソートが最もわかりやすい例。①配列を半分に分割、②左右それぞれを再帰的にソート、③ソート済みの2つの配列をマージ。8要素の配列なら4+4→2+2+2+2→1+1+...まで分割して、マージしながら戻す。各レベルでn回の比較、レベル数がlog n回だから全体でO(n log n)になるんだよ

ひよこ

動的計画法との違いは？

ペンギン先生

分割統治法は部分問題が独立している場合に使う。動的計画法は部分問題が重複（同じ部分問題を何度も解く）する場合に使う。フィボナッチ数列を分割統治で解くとfib(3)を何度も計算して遅い。動的計画法なら結果をメモ化して再利用する。重複があるかないかが使い分けのポイントだよ

ひよこ

二分探索も分割統治なの？

ペンギン先生

そうだよ。ソート済み配列から値を探す時、①中央の要素と比較、②目標値が小さければ左半分に、大きければ右半分に絞る、③繰り返し。毎回半分に分割するからO(log n)で見つかる。100万件のデータでも最大20回の比較で答えが出る。これも「分割して征服」の典型パターンだよ

ひよこ

おもしろい！実務で意識することは？

ペンギン先生

①並列処理との相性が良い。部分問題が独立しているからマルチスレッドで同時に解ける（Fork/Joinパターン）。②MapReduceは分割統治の大規模分散版。③再帰の深さに注意（スタックオーバーフロー）。④分割のコストと統合のコストのバランスを考える。分割しすぎるとオーバーヘッドが大きくなるよ

まとめ：ざっくりこれだけ覚えればOK！

「分割統治法」って出てきたら「問題を分割して個別に解いてから統合する手法」と思えればだいたいOK！

📖 おまけ：英語の意味

「Divide and Conquer」＝分割して征服せよ

💬 古代ローマの統治戦略と同じ名前。敵を分断して各個撃破する戦略だよ