分割統治パラダイムとは何ですか?

Question

分割統治パラダイムとは何ですか?

Accepted Answer

**分割統治**は、問題を(1)**分割**して小さなサブプロブレムにし、(2)各サブプロブレムを**解決**し、(3)結果を**統合**することで問題を解きます。多くの効率的なアルゴリズムはこのテンプレートに従っています。

## 考え方

サブプロブレムが独立していて、素早く縮小する場合、総処理量は**マスター定理**で分析できる漸化式に従います。

## 例: 分割統治による最大要素

```python
def max_dc(arr, lo, hi):
    if lo == hi:                       # base case: one element
        return arr[lo]
    mid = (lo + hi) // 2
    left = max_dc(arr, lo, mid)        # conquer left
    right = max_dc(arr, mid + 1, hi)   # conquer right
    return max(left, right)            # combine

max_dc([3, 9, 2, 7], 0, 3)            # -> 9
```

## 古典的な例

- **マージソート / クイックソート** — O(n log n) ソート。
- **二分探索** — O(log n)。
- **高速累乗、Karatsuba乗算、最近傍点対。**

## 計算量

しばしば T(n) = a·T(n/b) + f(n) です。マージソートの場合、T(n) = 2T(n/2) + O(n) = **O(n log n)**。

## 使用時と落とし穴

問題が**独立したサブプロブレムに明確に分割**できるときに使用します。サブプロブレムが**重複**する場合は、(再計算を避けるため)動的計画法を優先します。再帰のオーバーヘッドと統合ステップは小さな入力では支配的になる可能性があります。

## なぜ重要なのか

分割統治は、効率的なアルゴリズムの大部分の背後にある再利用可能なテンプレートです。

このパターンを認識することで、漸化式を使って素早く新しいアルゴリズムを導出・分析できます。

また、独立したサブプロブレムは並行実行できるため、自然と並列化にマップされます。