分割統治法とは？ぶんかつとうちほう
分割統治法とは、大きな問題を、同じ構造を持つより小さな複数の部分問題に分割し、それぞれを再帰的に（同じ手順を自分自身に当てはめて）解いてから結果を統合することで元の問題を解くアルゴリズム設計手法。
最終更新：2026-10-09
この語が出る過去問を解く →具体例
マージソートは、データを半分に分割することを繰り返し（分割）、最終的に1要素まで分割したものを整列しながら併合していく（統治）という分割統治法の典型例。
試験での引っ掛け
動的計画法との違いは部分問題が重複するかどうか。重複しないため結果を記録せずそのまま統合する（マージソート・クイックソートが代表例）。部分問題が重なって同じ計算を繰り返す場合は、一度計算した結果を記録して使い回す（メモ化）動的計画法の出番。
関連用語
出た過去問
出典：平成30年度 秋期 基本情報技術者試験 午前 問6（IPA）解説で登場
クイックソートの処理方法を説明したものはどれか。
正解：適当な基準値を選び，それよりも小さな値のグループと大きな値のグループにデータを分割する。同様にして，グループの中で基準値を選び，それぞれのグループを分割する。この操作を繰り返していく方法である。
要点：クイックソートは基準値で二分し再帰する分割統治法
クイックソートは基準値（ピボット）を選び、それより小さい群と大きい群にデータを分割し、各群に同じ処理を再帰的に適用する分割統治法である。平均計算量はO(n log n)となる。
出典：令和8年度 公開問題 基本情報技術者試験 科目A 問2（IPA）解説で登場
クイックソートの処理方法を説明したものはどれか。
正解：適当な基準値を選び，それよりも小さな値のグループと大きな値のグループにデータを分割する。同様にして，グループの中で基準値を選び，それぞれのグループを分割する。この操作を繰り返していく方法である。
要点：クイックソートは枢軸で分割し再帰的に整列する
クイックソートは、基準値（枢軸）を選んでデータを基準値より小さい グループ と大きいグループに分割し、各グループに対して同じ操作を再帰的（自分自身を呼び出す形で）に繰り返して整列する方法である。分割統治法（問題を小さく分けて解く考え方）に基づくため平均的な計算量（処理にかかる手間の目安）が小さい。挿入・選択・バブルの各整列法とは考え方が異なる。
出典・参考
公式シラバスの1 基礎理論 ＞ 2. アルゴリズム ＞ (3) アルゴリズム設計に掲載されている用語です。
解説は資格暗記が独自に作成しています。過去問の出典は各問題に記載のとおりです。