はじめMath! Javaでコンピュータ数学

第75回 計算量の数学 計算量と実際のコード その1

この記事を読むのに必要な時間:およそ 1 分

仕事をやり遂げるために必要な時間を見立てることが出来たら,次はその時間をいかに短縮するかを考えます。同じ仕事が短時間で出来るなら,それにこしたことはありません。余った時間で間違いがないかどうかの確認や,より品質を高めることが出来ます。

前回は,計算量O (n )のアルゴリズムの例としてリニアサーチを取り上げました。要素の数nの大きさに比例して,最悪検索時間が長くなります。今回は,リニアサーチよりも高速なバイナリサーチの計算量を求め,実際にコードを動かして速さの違いを実感しましょう。本当に同じ仕事を,より短い時間で実行できるのでしょうか。

図75.1 同じ品質ならより速く

図75.1 同じ品質ならより速く

計算量:バイナリサーチの場合O (log2(n))

バイナリサーチ※1とは,データの真ん中の値,すなわち中央値※2「とりあえず」チェックする方法です。データは整列済みで,小さい値から大きい値の順に並んでいます。目的の値が中央値だろう,と当たりを付けるのです。もちろん,一発で目的の値になることは少ないでしょう。でも,この「当たりを付ける」ということがとても有効なんです。図75.2を用いて解説します。

[Step 1]

図75.2の①のように,5個の整数を格納した配列valsから値「5」を格納した位置(添え字の値)を検索する場合target=5を紹介します。

図75.2 バイナリサーチとは

図75.2 バイナリサーチとは

図75.2 バイナリサーチとは

図75.2 バイナリサーチとは

先ず検索範囲を設定します。最初ですから左端は配列の先頭要素ですので,変数left=0右端は配列の末尾要素ですから変数right=vals.length-1=4となります。中央値の位置は(left+right)/2=2です。

もし,中央値が目的の値ならば,めでたく検索は終了です。しかし,違っていれば,中央値と目的の値の大小を比較します。もし,中央値よりも目的の値が小さければ,中央値以降のデータは捨ててしまいます。今回は,中央値より目的の値が大きいので,中央値より前のデータを捨てます。

[Step 2]

図の②のように,Step1の操作によって,注目する配列の範囲はn/2 になりました。話を簡単にするために,nの偶奇は考えません。実際にコードを組む際には,n/2 を整数変数の除算として取り扱えば,小数部分が発生せず,都合良く範囲が決まります。

新しい配列の中央の値と目的の値を比較します。等しければ検索は終了。

等しくなければ大小を比較します。中央値よりも目的の値が大きいので,現在注目しているデータ以前を捨ててしまいます。

[Step 3]

図の③のように,Step2の操作によって,残った配列のサイズは(n/2)/2になりました。今回の場合では残りのデータは1つだけになりました。ここで探す値target=5と配列の値vals[4]=5が等しいので,めでたく検索は成功し終了です。もし,vals[4]の値が5でなければ,探す値は配列内に存在しなかった,ということで,検索は失敗し終了します。検索に失敗した場合には,-1などの,配列の添え字としてあり得ない値を返して,検索に失敗したことを表明しましょう。

[Step a,最悪の場合]

最悪の場合,配列のサイズが1になるまでこのアルゴリズムが実行されます。繰り返しの回数aは次のような式で表されます。

バイナリサーチの計算量

O (log2(n))

y=log2(x) のグラフとy=x のグラフを並べて描くと,x が大きくなるほどバイナリサーチが有効なことがよく分かります。

図75.3 y=xy=log2xのグラフ

図75.3 <span styl

※1)
binary search
※2)
median

著者プロフィール

平田敦(ひらたあつし)

地方都市の公立工業高等学校教諭。趣味はプログラミングと日本の端っこ踏破旅行。2010年のLotYはRuby。結城浩氏のような仕事をしたいと妄想する30代後半♂。

コメント

コメントの記入