分割統治法 【divide and conquer algorithm】

概要

分割統治法（divide and conquer algorithm）とは、大きな問題を効率的に解く手法の一つで、問題全体を同じ構造の小さな問題に再帰的に分割していき、簡単に解けるサイズにした上で解いていく方式。

対象のデータが多いなど規模の大きな問題を、相似的な構造を持つ小さな部分問題に分割し、部分問題が大きい場合は再帰的に同じ分割手順を繰り返して問題のサイズをどんどん小さくしていく。

それ以上分割できない規模や簡単な手順で解ける規模になったら、これを解いて部分問題の解を求める。求めた多数の部分問題の解を分割と逆方向に順番に併合していき、全体を一つに統合すると最初の大きな問題の解となる。

様々な問題を解くアルゴリズム（計算手順）に応用される基本的な考え方で、コンピュータでは関数などの再帰呼び出しと組み合わせることで簡素な論理構造や短いプログラムで大きな問題を効率よく解くことができる。

値の比較・交換の少ない高速なソート（整列）アルゴリズムとして知られるマージソート（併合ソート）やクイックソートなどの応用例が有名である。

(2019.1.30更新)

他の辞典による解説 （外部サイト）

この記事の著者 ： (株)インセプト IT用語辞典 e-Words 編集部
1997年8月より「IT用語辞典 e-Words」を執筆・編集しています。累計公開記事数は1万ページ以上、累計サイト訪問者数は1億人以上です。学術論文や官公庁の資料などへも多数の記事が引用・参照されています。
ホーム画面への追加方法
1.ブラウザの 共有ボタンのアイコン 共有ボタンをタップ
2.メニューの「ホーム画面に追加」をタップ
閉じる