分割統治法

出典: フリー百科事典『ウィキペディア（Wikipedia）』

分割統治法（ぶんかつとうちほう、D&C、Divide and conquer algorithm）は、そのままでは解決できない問題を小さな問題に分割することで、最終的に問題を解決しようとする考え方。また、その方法やアルゴリズム。

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

[編集] 分割統治法のアルゴリズム

アルゴリズムとしての分割統治法の実装は、再帰呼び出しを使って実装することができる。以下のような手続きになる。

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) の値

なおここで小さな副問題に分割するときに副問題を解くアルゴリズムは自由に選択できる。そのため分割統治法を使ったアルゴリズムには、他のアルゴリズムを組み込むことも出来る。

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