バイキングで食事をするとき、若い頃は何も考えずにお皿にどんどん乗せていました。少々無理に盛っても、気合いで食べきっていました。元を取ってやろうとか、元以上に食べてやろうとか、そんな不純な気持ちもありましたし。しかし、このごろ、油ものや炭水化物を控えめにし、更に皿の大きさから自分の食べられる量に見当をつけて取るようになりました。食べ残しをしたくない事もありますが、おなか周りの余剰財産をなんとか増やさないようにしたいのです。その思いはなかなか実らず、だぶついた財産は心肺機能を圧迫し続けています。

さて、見当を付ける、ということは何時でも大切なことです。しかし、プログラミングの初心者のうちは、見当の付けようが分からず、組んで動かしてみて初めてパフォーマンスの悪さに愕然としたりするものです。できるなら、コードを組む前に、少なくとも動かす前にはパフォーマンスの見当を付けたいものです。今回から学習する内容は、そのための強力な武器となります。

計算量とは

計算量[1]とは、あるアルゴリズムを実行するとき、最大でどれだけ大変なことになるかを表す量です。元の英語を直訳すると「計算の複雑さ」となり、この方が意味をよく実感出来ます。

一言でまとめるために「どれだけ大変なことになるか」なんて、ちょっと曖昧な言葉を使いました。具体的には計算量は時間計算量[2]と領域計算量[3]に分けられます。

いくら大型コンピュータを使っているとはいえ、実用的な時間内で実行終了出来なければ意味がありません。何を持って実用的とするかは、実行するプログラムや得られる結果の価値に応じて決まります。あるアルゴリズムAが別のアルゴリズムBより少ない手順で結果を得られるならば「アルゴリズムAの時間計算量がアルゴリズムBの時間計算量より小さい」と言うことが出来ます。

いくら高速に計算が出来るアルゴリズムでも、大量にメモリを消費すると、小さなコンピュータ、例えばパソコンでは実行できません。そのようなアルゴリズムは大型コンピュータで実行すべきです。大量にメモリを消費するアルゴリズムは、領域計算量が大きい、と言うことが出来ます。可能な限り、領域計算量の小さなアルゴリズムを選択するべきです。領域計算量が大きければ、実際のプログラムの実行時間のうちの多くの部分をメモリアクセスの時間で消費してしまうからです。

時間計算量も領域計算量も、実際に取り扱うデータの状態によって大きく変化する事がありますから、アルゴリズムが決まっても計算量はどちらも一意に決まりません。

このため、計算量を表すために、かちっと数式化したものを用いず、おおよそどれくらいの大きさになるかを用います。

この連載中では、計算量といえば時間計算量を指すものとします。領域計算量については取り扱いません。

計算量の記号

おおよそどれくらい、という計算量を表すためにはオーダー表記を用います。

記号O ()をオーダー記号[4]といいます。オーダー表記に単位はありません。例えば時間計算量の単位は秒でもないしクロック数でもありません。「⁠あるアルゴリズムを実行するときの手順の数と繰り返しの数の合計」です。オーダーの違いというと、桁数の違いと直訳してしまいがちですが、実際には10進数や2進数といった基数の違いによって桁数はずいぶん変わりますから、桁数の違いだけでオーダーの違いを限定できません。計算量のオーダーは、1,n,log n,na,･･･といった具合に、式で表現します。たとえば、時間計算量O (1)は、入力の大きさに関わらず一定回数のアルゴリズム実行で終了するもののことです。O (n)は、入力の大きさnに対して、最大でおよそn回のアルゴリズム実行で終了するもののことです。目的が同じならば前者のアルゴリズムの方が優れていると言えます。O (n)のアルゴリズムだけに注目すると、nが大きいときと小さいときの実行時間の差がどれほどになるか見立てることができます。「⁠nが倍の2nになると、実行時間は倍になるだろう」といった具合です。

これがアルゴリズムをオーダー表記することの意味です。

計算量の違いを感じよう

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

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

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

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

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

O (n)

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

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

解説

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

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

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秒かかりましたよ。

C:\>java LinearSearch

4500[msec]passed.

今回はここまで

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