3秒でわかる
大きな問題を同じ形の小さな問題へ割り、解いてから統合する設計手法。マージソートや二分探索など、速い定番アルゴリズムの骨格です。
もう少し詳しく
どういうものか
分割統治法は、問題をそれ自身と同じ形の小さな問題へ分け、十分小さくなったところで直接解き、部分の答えを合わせて全体の答えにする手法です。分ける、解く、統合するの3段階からなり、解く部分は再帰で自分自身を呼びます。マージソート、クイックソート、二分探索、高速フーリエ変換がこの型で書かれています。
なぜ必要か
素直に全部を一度に扱うと計算量が n の2乗になる問題でも、半分ずつに割れば n log n まで落ちることがあります。半分にする操作は log n 回しか行えないので、各段の作業が n で済むなら全体が n log n になるという理屈です。1万件の並べ替えで比べると、2乗の手法が1億回に対して n log n は約13万回で、3桁の差が出ます。もうひとつの利点は分割した部分が互いに独立している点で、そのまま別のCPUコアや別のマシンへ配れます。
具体例
def merge_sort(xs):
if len(xs) <= 1: # これ以上割らない大きさ
return xs
mid = len(xs) // 2
left = merge_sort(xs[:mid]) # 分けて
right = merge_sort(xs[mid:]) # それぞれ解いて
return merge(left, right) # 統合する
def merge(a, b):
out, i, j = [], 0, 0
while i < len(a) and j < len(b):
if a[i] <= b[j]:
out.append(a[i]); i += 1
else:
out.append(b[j]); j += 1
return out + a[i:] + b[j:]分割の様子を図にすると次の形になります。
[5 2 8 1]
/ \
[5 2] [8 1]
/ \ / \
[5][2] [8][1] ここまで分ける
\ / \ /
[2 5] [1 8] 統合しながら整列
\ /
[1 2 5 8]つまずきやすいところ
再帰の停止条件を書き忘れると、割り続けてスタックが尽きます。要素が1個以下なら返す、という土台を先に書いてから分割を足すと安全です。もうひとつは統合の重さです。分けるところまでは速くても、合わせる処理が2乗なら全体は速くなりません。クイックソートが最悪 n の2乗になるのも、分割が偏って半分にならない場合があるためです。
似た用語との違い
| 手法 | 部分問題の関係 |
|---|---|
| 分割統治法 | 部分問題は重ならない |
| 動的計画法 | 部分問題が重なるので答えを覚えて再利用する |
| 貪欲法 | 分けずに毎回その場で最善を選ぶ |
