アルゴリズムA 第2回


線形探索の計算量は O(n) ですが、二分探索法 (Binary Search) の 計算量は O(log n) です。

二分探索法では、データは大きい順番、または小さい順番に並んでいます。 注目する領域の真中のデータが、探索するデータよりも大きいか、小さいかで 探索領域を次々に半分にしていきます。

二分探索法で10個のデータから、「14」というデータを探索する様子を 下に示します。 表の中では、注目する領域の下が l (low), 上が h (high)、 真中が m (middle) で表されています。

配列番号 a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9]
配列データ 1 3 4 8 13 14 18 20 21 25
初期状態 ↑l ↑m ↑h
2回目 ↑l ↑m ↑h
3回目(発見) ↑l
↑m
↑h

下に示す BinarySearch.java のプログラムにおいて、探索の部分の 計算量を考えてみましょう。

繰り返しの回数は以下のように計算できます。

  データの総数をnとおくと、繰り返しの度に high と low で囲む領域は
  半分になりますから、繰り返し回数を m とすると
    2m = n
  両辺の loge を計算すると
    m loge 2= loge n
    m =  loge n / loge 2
loge 2 は定数なので、繰り返しの回数は log n のオーダーになります。

(1) (2)の計算量 O(1)
(3)〜(9)の計算量 O(log n)
(10)の計算量 O(1)
したがって、二分探索法における探索の計算量は O(log n) となります。

二分探索法による探索の計算量

二分探索法 BinarySearch.java
授業で配布するプリントを参照して下さい。

RunBinarySearch.java
授業で配布するプリントを参照して下さい。

RunBinarySearch.javaの実行例
% javac RunBinarySearch.java
% java RunBinarySearch
10
2 two
4 four
5 five
8 eight
13 thirteen
14 fourteen
18 eighteen
20 twenty
21 twenty-one
26 twenty-six
4
1
Not found
32
Not found
3
Not found
20
value=twenty

RunBinarySearch.javaが扱うデータは次の形式です。

RunBinarySearch.javaへの入力形式

N
K1 D1
K2 D2
...
KN DN
M
Q1
...
QM

最初の行には1個の整数 N が含まれる。 Nはデータの数(ただし1≦N≦100)を表す。

2行目以降はN行に渡ってデータが続く。 各行は1個の整数 Ki 、 データの区切りとしての空白文字1個、 1個の文字列 Di を含む。 Ki はデータのうち「比較の対象となるキー」であり、 Diは「それ以外のデータ」である。

ただしi < j ならば Ki ≦ Kj が 成り立つとする(つまりキーが小さい順にデータが与えられる)。

その次の行は、質問の個数を表す整数 M を含む(1≦M≦10)。 それ以降にM行続き、各行は探索すべきキーとなる整数 Qj (1≦j≦M) を含む。


二分探索法のためのデータ登録の計算量

二分探索法では、データは大きさの順番に並んでいることが必要です。 したがって、データを登録する毎に以下の計算量が必要となります。

(1)データを挿入すべき位置を計算するO(log n)
(2)その位置より後のデータをずらすO(n)
(3)その位置にデータを登録するO(1)

データを1個登録するには、O(n)の計算量が必要です。 すなわち、データをn個登録するには、O(n2) の計算量が必要である、ということになります。

ただし、データを最初にまとめて登録する場合は、もう少し効率のよい 方法が使えます。データを大きさとは関係なく登録しておいて (データ1個を登録する計算量はO(1)、したがってn個の データを登録する計算量はO(n)となります)、 最後に一度だけ整列(sort、最も効率のよいアルゴリズムだと O(n log n)で可能です)を行えばよいのです。


探索アルゴリズムの比較

データがn個の場合の計算量は、アルゴリズムによって以下のように 変化します。

アルゴリズム登録探索
線形探索法O(n)O(n)
二分探索法O(n2) または O(n log n) O(log n)

一般に、データの探索回数の方が登録回数よりも多くなりますので、 そのような場合は線形探索法よりも二分探索法の方が効率がよくなります。 ただし、「探索途中で頻繁にデータの登録がある場合は、二分探索法は向かない」 ことになります。


適切なアルゴリズム

どのようなアルゴリズムが「適切である」かは、 データの大きさやプログラムの利用法によって異なります。 理由を以下に示します。



アルゴリズムA 演習


作成したプログラムが正しく動作することを確認したら、それぞれの 提出先に提出しなさい。 提出した後は、正しく提出されていることを http://nw.tsuda.ac.jp/class/algoA/local/handin/ で必ず確認しておいて下さい。 提出〆切は次回の講義の開始時刻です。

課題2a

提出ファイルBinarySearch.java
コメント欄:指定箇所の通過回数と、各時点における変数low, high, midの値
提出先: 「宿題提出Web:アルゴリズムA:課題2a」 http://nw.tsuda.ac.jp/class/algoA/local/handin/up.php?id=kadai2a

RunBinarySearch.java を動作させて下さい。 Entry.java, EntryTable.java, BinarySearch.java, RunBinarySearch.java が必要となります。

10個の入力データと4個の質問のデータを

10個の入力データ 4個の質問データ
10 ←データの個数
2 two
4 four
5 five
8 eight
13 thirteen
14 fourteen
18 eighteen
20 twenty
21 twenty-one
26 twenty-six
4 ←質問の個数
1
32
3
20
としたとき、それぞれの質問に対して、BinarySearch.javaの searchメソッド中の
	    // [課題]この時点の変数low,high,middleの値を答えること
と書かれた行を何回通過するかを考えなさい。 また、その行を通過する時点で変数low, middle, highがどのように 変わっていくかを考えなさい。

BinarySearch.javaを提出して下さい。 ただし、提出する際のコメント欄には各質問に対する上記の考察の 結果を記述すること。

[解答例]
 質問のキー:6の場合
  4回通過する。
  low=0, high=9, middle=4
  low=0, high=3, middle=1
  low=2, high=3, middle=2
  low=3, high=3, middle=3

課題2b

提出ファイルCubeRoot.java
コメント欄:CubeRoot.javaに2, 8, 100, 1000, 123456789を入力として与えたときのそれぞれの出力
提出先: 「宿題提出Web:アルゴリズムA:課題2b」 http://nw.tsuda.ac.jp/class/algoA/local/handin/up.php?id=kadai2b

与えられた実数 x の立方根(3乗根, )を計算するプログラムを作成しなさい。 与えられる実数 x の値は1より大きいと仮定して構わない。 答に含まれる誤差は1.0×10-5よりも小さいこと。 ただし、Mathクラスのメソッドを使ってはならない。

(ヒント)2分法を使えばよい。 最初は low=1.0, high=x と置いて、lowとhighの真ん中 midの3乗と x を比較する。比較した結果、lowとhighの区間を1/2ずつ狭めていって high-lowが許容誤差よりも小さくなったら終了する。

CubeRoot.java
授業で配布するプリントを参照して下さい。

CubeRoot.javaの実行例
$ javac CubeRoot.java 
$ java CubeRoot 
5 
1.7099723815917969
$ java CubeRoot 
64 
3.9999998211860657