分割統治法
問題を解くアプローチで、対象の問題をより小さな問題に分割して解き、その解を組み合わせることで元の問題を解くアプローチです。このアプローチの特徴から再帰との相性が良いです。
ソート問題に対する分割統治法の代表例のマージソートを擬似コードで説明する。
サイズが小さい問題に分割するのでいずれ解けるベースケースにたどり着く。
探索が関わる問題ではなんども同じ部分問題を解くことになり計算量が指数関数的になったりする。
そのような場合にはメモ化再帰を使うことで改善できる。
code:mergesort.py
import itertools
def merge_sort(l: ListInt) -> ListInt: if len(l) <= 1:
return l
array = []
while len(left) != 0 and len(right) != 0:
array.append(left.pop(0))
else:
array.append(right.pop(0))
return list(itertools.chain.from_iterable(array, left, right)