分割統治法 | 応用情報技術者試験
分割統治法とは
分割統治法とは、そのままでは解決するのが難しい大きな問題を、いくつかの「扱いやすい小さな問題」に細かく分割し、それぞれの小さな問題を個別に解決(統治)してから、最後にその結果を組み合わせて元の大きな問題の答えを導き出す手法です。
このアプローチはアルゴリズム設計の基本であり、特にデータを並び替える「ソート」や、データを検索する処理でよく使われます。問題を細かく分割するプロセスは、これ以上分割できない最小単位になるまで再帰的(繰り返し)に続けられ、小さな問題を一瞬で解いてから、ドミノ倒しのように組み上げていきます。
具体例
バラバラに置かれた8枚のカードを数字の小さい順に並べ替える(ソートする)場面を考えます。分割統治法(マージソート)では、まず8枚を4枚ずつの2グループに分け、さらに2枚ずつ、最終的に1枚ずつの8グループに分解します。1枚ずつのグループはすでに整列しているとみなせるため、隣り合うグループ同士を「小さい順になるように合流(マージ)」させながら、2枚、4枚、8枚と組み立て直すことで効率よく並べ替えを完了します。
もう少し詳しく