分割統治法

gpt-5.icon

分割統治法（Divide and Conquer）は、大きな問題を小さな部分問題に分割し、それぞれを解いてから結果を統合することで全体の解を得るアルゴリズム設計手法です。計算機科学において非常に重要で、多くの効率的なアルゴリズムがこの考え方で構築されています。

基本ステップ

分割統治法は通常、次の3ステップに従います：

1. Divide（分割）

問題をいくつかの小さな部分問題に分割します。

多くの場合、元の問題と「同じ型」の部分問題に分けられます。

2. Conquer（征服 / 解決）

部分問題を再帰的に解きます。

部分問題が十分に小さい場合は、直接解を求めます（ベースケース）。

3. Combine（統合）

部分問題の解を統合して、元の問題の解を構築します。

典型例

Divide: 配列を半分に分割。

Conquer: 各部分配列を再帰的にソート。

Combine: 2つのソート済み配列をマージ。

Divide: ピボットを選び、小さいものと大きいものに分割。

Conquer: 部分配列を再帰的にソート。

Combine: 何もせず、既に並んでいる。

二分探索 (Binary Search)

Divide: 探索区間を半分に分ける。

Conquer: 該当する半分を再帰的に探索。

Combine: 必要なし。

メリット

複雑な問題をシンプルに分けて考えられる。

再帰的に考えることで数学的に分析しやすい。

並列計算に向いている（部分問題が独立していることが多い）。

デメリット

再帰呼び出しが多い場合、オーバーヘッドが発生する。

部分問題の統合（Combine）が重いと効率が悪化する。

問題によっては分割統治が適さないケースもある。