Binary Searchと分割統治によるコード最適化

Binary Searchは強力でソート済みでない配列に対して適用することも可能である。それどころか、対象が離散的な値である必要すら無い。分割統治（Divide-and-conquer）はそれに良く似た手法で、対象を再帰的に半分にしてく手法である。

今回はランダムに数値が並んだ配列の中で、それらの数値の取りうる範囲が指定されており、その範囲の中で一つだけ数値が欠けていて、その欠けている数値を探し出す問題を考える。例えば範囲が1〜10で配列の長さは9であり、配列の中の数値に重複は無い場合である。

直感的に考えると配列をソートして一つずつ順に数値を見ていけば良い。数値が欠けていればインデックスとの対応が合わないはずだ。しかしこれは最速でもO(Nlog(N))かかることになる。もう少し詳しく言えば、ソートしてから一つずつ配列を見ていくので、最悪の場合はO(Nlog(N)+N)になるだろう。

このような問題は分割統治を使ってもっと速くできる。Binary Searchのようにインデックスをlow,highとして扱うような使い方では解けないため、ここは配列のサイズを1/2ずつに分割していく方法を組み合わせる。上記の例で言うと、low=1, high=10, mid=5として初期設定し、midより大きい配列、小さい配列、に分ける。欠けている場合は、配列が期待するサイズよりも小さいはずなので、lowかhighにmidを設定し、そちらの配列を再帰的に検査していく。

ここまで考えることができればO(Nlog(N))よりも速くできることが分かるだろう。しかし、ここに辿り着く前にこれがO(Nlog(N))よりも速くなる、ということに気付くのが難しい。実際には、midを元にサイズNの配列を作成するための走査が必要になるためO(N)になる。Binary Searchを用いていることを実感したいならばもう少し詳しく考えて、N+N/2+N/4+...となるので初項=N、公比=1/2、の等比数列の和を求めると、N*(1-(1/2)^N)/1-(1/2)、となり、Nが十分大きければ(1/2)^N≒0となるためO(N)が導ける。O(Nlog(N))と比較するとすれば、log(N)の部分が定数になる（具体的には2になる）というところがパフォーマンスに影響する。

この問題の解法は、例えば、k個の欠けている数値のうちの一つを探し出す、とか、k個の重複している数値のうちの一つを探し出すなどにも適用できる。コードは以下。配列をスクランブルした後、最後の要素を削除（配列のサイズをマイナス1）することによって、欠けている配列を作り出している。

Find a lost number in O(N) better than O(NlogN) by sort. · GitHub

MBPでの実行結果。

$ for i in `seq 1 5`; do echo $i; ./find_a_lost_number 100000000; done
1
78221769==78221769:OK
func_O_N : 1.27 sec.
78221769==78221769:OK
func_O_NlogN : 20.13 sec.
2
12264665==12264665:OK
func_O_N : 1.21 sec.
12264665==12264665:OK
func_O_NlogN : 20.09 sec.
3
78228998==78228998:OK
func_O_N : 1.23 sec.
78228998==78228998:OK
func_O_NlogN : 20.05 sec.
4
44908476==44908476:OK
func_O_N : 1.32 sec.
44908476==44908476:OK
func_O_NlogN : 20.35 sec.
5
85940350==85940350:OK
func_O_N : 1.24 sec.
85940350==85940350:OK
func_O_NlogN : 20.17 sec.
$

二つ目の問題は、配列の中で合計値が最大となる部分配列を発見する。配列の要素は整数なので、負の値も存在する。

これには、計算量がO(N³), O(N²), O(NlogN), O(N), となる解法が存在するが、分割統治を利用した解法はO(NlogN)となる。1/2に分割しながら中央の値から左と右の部分配列の合計を計算し、最大となる部分配列を見つける。O(N)の解法の基礎となるアイデアは、配列の最初の要素から合計していくが、合計が負の値になったときはその次の要素を部分配列の最初の要素とする。そうやって部分配列を細切れにしながら合計の最大値を更新していくと、O(N)で、つまり一つのループで計算できる。

Find maximum sum of sub array in O(N^3), O(N^2), O(NlogN), O(N). · GitHub

出力としては、部分配列の最初のインデックス-[合計値]-部分配列の最後のインデックスとしている。

$ ./max_sub_array 3000
1653-[62030]-1900
func_O_N3 : 12.63 sec.
1653-[62030]-1900
func_O_N2 : 0.01 sec.
1653-[62030]-1900
func_O_NlogN : 0.00 sec.
1653-[62030]-1900
func_O_N : 0.00 sec.

$ ./max_sub_array 30000
2795-[4884646]-29986
func_O_N2 : 1.34 sec.
2795-[4884646]-29986
func_O_NlogN : 0.00 sec.
2795-[4884646]-29986
func_O_N : 0.00 sec.

$ ./max_sub_array 30000000
25697428-[46557400133]-28003047
func_O_NlogN : 4.39 sec.
25697428-[46557400133]-28003047
func_O_N : 0.20 sec.