分割統治法 とは？

マージソートを考えよう。[4, 1, 3, 2]を[4, 1]と[3, 2]に分け、さらに1要素ずつにする。1要素はそのままで並んでいるので、まず[1, 4]と[2, 3]を作り、次に小さい値から合わせて[1, 2, 3, 4]にするんだ。

それ以上分けなくても直接答えが出る条件を決めるよ。マージソートなら0個や1個の要素は、すでに並んでいる。こうした終了条件が再帰の土台。分割しても問題が小さくならない作りでは、いつまでも処理が終わらないことがあるんだ。

必ずではないよ。分割や統合にも仕事があり、部分問題の数や大きさも重要。マージソートは、各段階で全体の要素数に比例する仕事をし、半分ずつ分ける段階が対数的に増えるので、一般的な実装の時間計算量はO(n log n)になる。すべての分割統治法がこの計算量になるわけではないよ。

分割統治の例だけれど、分け方が違うよ。基準の値を使って要素を左右に分け、それぞれを並べ替える。平均ではO(n log n)の時間で処理できる一方、分割が偏ると最悪でO(n²)になる。分け方が性能に影響する例として覚えるとよいね。

部分問題が互いの処理に依存せず、実行環境も対応していれば、並列に解く設計ができるよ。ただし実行を分ける費用や結果を合わせる費用もある。小さすぎる問題まで分ければ速くなるとは限らない。分割・解決・統合の仕事を全体で見ることが大切なんだ。