0.1 二分探索(binary search)
ムラサちゃんとskypeで雑談してたら、こんな問題が飛んできた。
n個の整数の集合Sとある整数xが与えられたとき、Sの中の2個の要素でそれらの和がちょうどxになるものの組を見つける、実行時間Θ(nlog2(n))のプログラムを作れ。
整数は面倒なので、10億程度までの自然数で考える。0は含めても含めなくても良い。
普通に考えると、以下のような探索が思いつく。
for(int i=0; i<n-1; ++i){ for(int j=i+1; j<n; ++j){ if(s[i] + s[j] == x){ ... } } }
これの(時間)計算量はO(n^2)*1である。計算量のお話はまた今度する。
まぁ、これでも十分なんだけど、nが1,000になると計算量が1,000,000となり、実行時間的には少し怪しげになる。
そこで、O(nlogn)のアルゴリズムを考えてみる。これだと、nが1,000になっても計算量は32,000程度である。すごい。
O(logn)を見ると真っ先に思い浮かぶのが、二分探索(binary search)であった。ので、二重めのループで二分探索を用いたコードを書いた。
二分探索は、あらかじめソートされたデータ群を前提とする探索方法である。
たとえば、以下のようなデータ群から''13''をサーチしたいとする。
{1,2,4,6,7,9,10,13,15,16}
このデータ群の真ん中に位置するデータをチェックする。「真ん中」は真ん中付近であれば大雑把で良い。今回は、データ群の個数kが偶数のときは、左から(k/2)+1番目を見ることにしよう。
上の例で、真ん中のデータは''9''である。サーチデータ''13''ではなかった。ここで、サーチデータ''13''は、少なくとも''9''より右側に存在することが分かる*2。
よって、今度は以下のデータ群で再び同様のチェックを行う。
{10,13,15,16}
真ん中のデータは''15''である。サーチデータ''13''は、少なくとも''15''より左側に存在することが分かる。
今度は、以下のデータ群で見てみる。
{10,13}
真ん中のデータは''13''である。サーチデータ''13''と一致し、めでたく探索が終了する。
この探索の凄い所は、1回の探索で探索せねばならないデータ数が半分に減ることである。よって、n個のデータ群の探索で最悪O(logn)の計算量である*3。
二重めのループで二分探索を用いることで、探索アルゴリズムの計算量はO(nlogn)となる。
#include <iostream> using namespace std; const int max_n = 10000; int s[max_n]; //集合S int culc_num; //計算回数(比較回数) //二分探索 //見つかった:0 見つからなかった:-1 int binary_search(int *data, int data_num, int target){ int m = data_num / 2; ++culc_num; /* if(m >= 0){ cout << "\t("; for(int i=0; i<data_num; i++){ cout << data[i]; if(i < data_num-1) cout << ","; else cout << ")" << endl; } cout << "\tcheck:" << data[m] << endl; } */ if(data_num < 1) return -1; else if(data[m] == target) return 0; else{ if(data_num == 1) return -1; else if(data[m] < target) return binary_search(&data[m+1], data_num-m-1, target); else return binary_search(&data[0], m, target); } } int main(){ //見つけたい解を入力 int x; cin >> x; //データ数の入力 int n; cin >> n; //n個のデータを入力。昇順入力じゃないとぉこだょ for(int i=0; i<n; ++i) cin >> s[i]; //s[i] + s[j] = xなる解を探索 int ans_num = 0; //解の個数 for(int i=0; i<n-1; ++i){ int target = x - s[i]; //どの数値を見つければ良いか // cout << "search:" << target << endl; if(binary_search(&s[i+1], n-i-1, target) == 0){ cout << "(" << s[i] << "," << target << ")" << endl; ++ans_num; } } //解の出力 if(ans_num == 0) cout << "NA" << endl; cout << "ans_num:" << ans_num << endl; cout << "culc_num:" << culc_num << endl; return 0; }
コメント化している命令を解除すれば、どのような動きで探索が為されているか見れる。
たとえば、x=13,n=10,S={1,3,4,4,5,6,7,8,9,10}なる入力を与えると、その結果は以下のようになる。
入力:
13
10
1
3
4
4
5
6
7
8
9
10出力:
(3,10)
(4,9)
(4,9)
(5,8)
(6,7)
ans_num:5
culc_num:20
同じことを、最初のO(n^2)アルゴリズムで行うと、culc_numは45となる。