テクノロジ
分割統治法とは
読み方：ぶんかつとうちほう
ひとことで言うと：問題を小さな部分問題へ分け、それぞれを解いて結果を統合する設計手法。
意味をわかりやすく解説
分割統治法は、大きな問題を互いに扱いやすい小さな部分問題へ分割し、それぞれを解いた後で結果を統合して元の問題を解く設計手法です。
再帰処理と相性がよく、マージソート、クイックソート、二分探索などで使われます。部分問題が十分小さくなったときの終了条件も必要です。
具体例
マージソートでは配列を半分ずつ分け、それぞれを整列し、最後に二つの整列済み列を併合します。
似た用語との違い
動的計画法
分割統治は独立した部分問題へ分けることが中心です。動的計画法は重複する部分問題の結果を保存して再利用します。
再帰
分割統治法は再帰で実装されることが多いですが、再帰は呼出し方法、分割統治は問題設計の考え方です。
覚え方
Divide→Conquer→Combine。分ける、解く、合わせる。
基本情報技術者試験の試験ポイント
どのアルゴリズムが分割統治法か、再帰終了条件と統合処理を問う問題に備えます。
CHECK QUESTION
マージソートが分割統治法の例といえるのはなぜですか。
答えを見る
配列を小さな部分へ分割し、各部分を整列してから結果を併合して全体を解くからです。
この説明は分かりやすかったですか？
基本情報技術者試験を勉強中ですか？
この用語を含む重要用語を、単語帳や4択テストで学習できます。