分割統治法

本物のページはこちら→divide-and-conquer

Included page "divide-and-conquer" does not exist (create it now)

divide and conquer略してD&C
分割統治法は多くのアルゴリズムの基本となっている考え方。
大きな問題が与えられたらそれを小さい問題に再帰的に分割して解き、それらの解を集めて最終的な解を得るというもの。
再帰を使うことによってプログラムが簡単になる他、
分割をバランスよく行うことで計算量を削減することができる。
クイックソートマージソートなどがその典型例。
分割統治法で問題を解くときには、なるべく少ない数の、なるべく小さい問題に分割することが重要。

List of pages tagged with divide-and-conquer:

関連する有名なアルゴリズム

参考にした本

サポートサイト Wikidot.com