【アルゴリズム】Javaプログラマのためのアルゴリズムとデータ構造(第2章)

2.1 アルゴリズムの性能の基準

アルゴリズムの性能の基準をどのように定めるか？

• アルゴリズムを実際にコンピュータに実行させて時間を計測するのはどう？

ダメ。問題点が3つある。

1. マシンによって得意・不得意な処理があるので客観的ではない
2. プログラムの実行時間はコードを書く人の腕前によって大きく左右される
3. 高級言語を使う場合はその言語自体や、言語のコンパイラによっても実行時間が変わる

2.2 計算量

アルゴリズムの性能を評価するには計算量を基準にする。

計算量 = 仮想的なコンピュータがあるアルゴリズムを実行した時にどれくらい時間がかかるかを、入力の大きさnの関数として表現したもの

計算量には以下の2種類がある。

1. 時間計算量 = 「アルゴリズムの実行にどれだけ時間がかかるか」
2. 領域計算量 = 「アルゴリズムの実行にどれだけの領域が必要なのか」

プログラムを書く際に最も問題になるのは時間なので、時間計算量を計算量とすることが多い。

通常、計算量を求める際には最悪の入力データを想定する。 これを最大計算量という。

2.2.1 線形探索法による探索の計算量

線形探索法とは、配列の先頭から末尾に向かってスキャンしながら順番にキーと要素の比較を行うもの。

public class LinearSearch {

    /*
     * テーブルのエントリ
     */
    static public class Entry {

        int key; //比較対象となるキー
        Object data; //それ以外の情報

        /**
         * エントリを生成する
         * @param key キー
         * @param data キーkeyに対応するデータ
         */
        private Entry(int key, Object data) {
            this.key = key;
            this.data = data;
        }

        final static int MAX = 100; //データの最大個数
        Entry[] table = new Entry[MAX]; //データを格納する配列
        int n = 0; //tableに登録されているデータの個数

        /*
         * データを登録する
         * @param key キー
         * @param data キーkeyに対応するデータ
         */
        public void add(int key, Object data)
        {
            if(n >= MAX) {
                throw new IllegalStateException("データの個数が多すぎます");
            }
            table[n++] = new Entry(key, data);
        }

        /*
         * キーkeyに対応するデータを探す
         * @param key キー
         * @return キーkeyに対応するデータ。キーが見つからなければnull
         */
        public Object search(int key)
        {
            int i = 0; //(1)
            while (i < n) { //(2)
                if(table[i].key == key) { //(3)
                    return (table[i].data); //(4)
                }
                i++; //(5)
            }
            return null; //(6)
        }
    }
}

計算量の加算 O(f(n)) + O(g(n)) = O(max(f(n), g(n)))

計算量O(f(n))のループをO(g(n))回繰り返すと、 O(f(n))・O(g(n)) = O(f(n)g(n))

ステートメント	実行回数	計算量
(1)	1	O(1)
(2)	n/2	O(n)
(3)	n/2	O(n)
(4)	1	O(1)
(5)	n/2	O(n)
(6)	1	O(1)

searchメソッドの計算量 = O(1) + O(n) + O(1) + O(1) = O(max(1,n,1,1)) = O(n)

定本Javaプログラマのためのアルゴリズムとデータ構造