技術的なやつ

技術的なやつ

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となる。

*1:O(n^2)とか、Θ(n^2)とか書かれる。読み方は「オーダー」。

*2:sorted dataが前提のため。

*3:情報学に於いてlogの底は2が前提であることが多い。今回もlogの底は2としている。