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

第74回 計算量の数学 計算量とは

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

計算量の違いを感じよう

今回から数回に渡って,時間計算量に注目して,アルゴリズムが違うとこれほど計算量が違う,という具体例を示します。コードを動かして,計算量の違いを実行時間の違いとして感じてみてください。

計算量:リニアサーチの場合O (n)

先ずはリニアサーチ※5でやってみましょう。リニアサーチとは,小さい整数値から大きな整数値へ整列済みの配列データ内に,目的の数値が格納されていれば,その値の格納された配列の添え字を返すアルゴリズムです(図74.2⁠⁠。先頭から1つ1つデータをチェックし,一致するまで順次チェックを繰り返します。この様子から,シーケンシャルサーチ※6⁠順次検索)などと呼ばれます。

図74.2 リニアサーチとは

図74.2 リニアサーチとは

リニアサーチでは,先頭に近いデータは早く見つかりますが,末尾に近いデータのときは見つけるのに時間がかかります。最初に「当たりを付ける」ことをしませんので,場合によってはサーチの効率が平均的に悪くなります。

n個のデータの中から目的のデータを見つけるためには,最悪の場合n回の実行を必要としますので,リニアサーチの計算量はO (n)と表します。例えば,for文やwhile文のようなn回のループを実行するプログラムの計算量はO (n)です。

リニアサーチの計算量

O (n)
※5)
linear search
※6)
sequential search

問題 リニアサーチのプログラムを作りましょう。

10万個の要素を持つ整数配列を用意しましょう。配列に格納する値は0から1つずつ増加させましょう。この配列の中から3,27,(10万÷2),(10万×2)の4つの値を1万回検索するために必要な時間を計測するプログラムにしてください。

解説

問題 リニアサーチのプログラムを作りましょう。

それでは,リニアサーチのコード例を示します。是非実行して,お手元の環境での実行時間を計測してみてください。

ソースコード:LinearSearch.java

01:public class LinearSearch {
02:
03:  public static int exec(int[] vals, int target) {
04:    for(int i = 0; i < vals.length; ++i)
05:       if (vals[i] == target) return i;
06:    return -1;
07:  }// end of exec
08:
09:  public static void main(String[] args) {
10:   int len = 100000;
11:   int[] data;
12:   data = new int[len];
13:   for(int i=0; i<len; ++i) data[i]=i;
14:   int result;
15:   int repeat = 10000;
16:   long time;
17:   time = System.currentTimeMillis();
18:   for (int i=0; i<repeat; ++i){
19:     LinearSearch.exec(data,3);
20:     LinearSearch.exec(data,27);
21:     LinearSearch.exec(data,(int)(len/2));
22:     LinearSearch.exec(data,(int)(len*2));
23:   }
24:   time = System.currentTimeMillis() - time;
25:   System.out.println(time + "[msec]passed.");
26:  }// end of main
27:
28:
29:  private static void resultPrint(int result){
30:    if (result != -1) {
31:      System.out.println("[ Found ] index key = " + result);
32:    } else {
33:      System.out.println("[Not Found]");
34:    }
35:  }// end of resultPrint
36:
37:}// end of LinearSearch

以下はその実行結果です。私の環境※6では4.5秒かかりましたよ。

出力画面3

C:\>java LinearSearch

4500[msec]passed.
※6)
CPU:Intel(R) Core(TM)2 Duo CPU U7500 1.06GHz,Memory 2GB,WinXP,java version ⁠1.6.0 12”

今回はここまで

次回は,このリニアサーチを基準に,他のアルゴリズムを使ったサーチがどれだけの計算量で,実際にどれほど高速さを体感出来るのか,やってみましょう。お楽しみに。

今回のまとめ

  • 計算量には時間計算量と領域計算量があることを学びました。
  • リニアサーチの計算量を求め,プログラムを作成・実行しました。

著者プロフィール

平田敦(ひらたあつし)

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