分割統治法のソースを表示

{{Otheruses|アルゴリズム|政治、歴史分野での分割統治|分割統治}}
'''分割統治法'''（ぶんかつとうちほう、{{lang-en|divide and conquer algorithm}}、D&C）は、そのままでは解決できない問題を小さな問題に分割することで、最終的に問題を解決しようとする考え方。また、その方法や[[アルゴリズム]]。

[[クイックソート]]や[[マージソート]]に代表されるような[[ソート]]でよく使われている。また、[[構造化プログラミング]]でも、この考え方に基づいている。

==分割統治法のアルゴリズム==
アルゴリズムとしての分割統治法の実装は、[[再帰呼び出し]]を使って実装することができる。以下のような手続きになる。
 function hoge(x)
   if hoge(x)の求値が簡単 then
     return 簡単な方法で解いたhoge(x)の値
   else
     x を y1, y2 といった複数個のパラメータに分割。(小さな副問題に分割)
     hoge(y1), hoge(y2) を再帰呼び出し
     return hoge(y1) と hoge(y2) の値から求めた hoge(x) の値
なおここで小さな副問題に分割するときに副問題を解くアルゴリズムは自由に選択できる。そのため分割統治法を使ったアルゴリズムには、他のアルゴリズムを組み込むことも出来る。

分割統治法は、再帰の際に同じ副問題を複数回解いてしまう場合があり、こうした場合にはこれが原因で計算コストが{{仮リンク|指数関数的成長|label=指数的に発散|en|exponential growth}}してしまう事があるという問題を抱える。この問題は、すでに解いた副問題をメモリ上に記憶する事で解決できる（[[動的計画法]]）。

また上のように再帰呼び出しを使った処理は現在の状態を格納する[[スタック]]を内部的に使用しているので、メモリを消費し、実行速度が遅くなる。しかし、一部の特定のパラメータを格納するスタックや[[キュー]]などを使って再帰呼び出しを使わないで[[ループ_(プログラミング)|ループ]]などで実装することも可能である。

== 関連項目 ==
*[[メモ化]]
*[[分枝限定法]]

{{Computer-stub}}
{{デフォルトソート:ふんかつとうちほう}}
[[Category:アルゴリズム|ふんかつとうちほう]]