分割統治法 【divide and conquer algorithm】

概要

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

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

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

様々な問題を解くアルゴリズム（計算手順）に応用される基本的な考え方で、コンピュータでは関数などの再帰呼び出しと組み合わせることで簡素な論理構造や短いプログラムで大きな問題を効率よく解くことができる。値の比較・交換の少ない高速なソート（整列）アルゴリズムとして知られるマージソート（併合ソート）やクイックソートなどの応用例が有名である。