ikemonn's blog

技術ネタをちょこちょこと

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

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

二分探索法とは、あらかじめキーが昇順に整列されている配列の中から特定のキーを持つデータを探しだすアルゴリズム

public class BinarySearch {
    /*
     * テーブルのエントリ
     */
    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に登録されているデータの個数


    /*
     * キーkeyに対応するデータを探す
     * @param key キー
     * @return キーkeyに対応するデータ。キーが見つからなければnull
     */
    public Object search(int key)
    {
        int low = 0; //(1)
        int high = n - 1; //(2)

        while (low <= high) { //(3)
            int middle = (low + high) / 2; //(4)
            if(key == table[middle].key) //(5)
                return table[middle].data; //(6)
            else if (key < table[middle].key) //(7)
                high = middle - 1; //(8)
            else //key > table[middle].keyである
                low = middle + 1; //(9)
        }
        return null; //(10)
    }
}

計算量

(1)(2)の計算量O(1) (3)〜(9)の計算量O(log n) (10)の計算量 O(1)

二分探索法の計算量 = O(1) + (1)(2)の計算量O(1) + O(1) = O(max(1, log n, 1)) = log n

データの登録に必要な計算量

線形探索法の場合

データの登録は配列の末尾に要素を追加するだけなので、計算量はO(1)

public void add(int key, Object data)
{
    if(n >= MAX) {
        throw new IllegalStateException("データの個数が多すぎます");
    }
    table[n++] = new Entry(key, data);
}

二分探索法の場合

キーの昇順にデータがソートされている状況を保たねばならない。

public void add(int key, Object data)
{
    int pos;
    pos = データを挿入すべき場所;  //(1)
    配列中のposより後ろの要素を1つずつ後ろにずらす; //(2)
    table[pos] = new Entry(key,data); //(3)
}

(1)で挿入する位置を探すには二分探索法を使えばよいので、計算量はO(log n) (2)では平均してn/2個のデータを移動する必要があるので計算量はO(n) (3)の計算量はO(1)

これらを合計すると

O(log n) + O(n) + O(1) = O(max(log n , n, 1)) = O(n)

2.2.4線形探索法と二分探索法の比較

登録(n要素あたり) 探索(1回あたり)
線形探索法 O(n) O(n)
二分探索法 O(nの2乗) O(log n)

上の表から二分探索法は探索は速いものの登録に時間がかかることが分かる。 そのためプログラムの初期化の段階で全データをテーブルに登録しておき、メイン処理では探索のみを行うようにすると計算量を減らせる。 そのためには、まず線形探索法と同じようにデータを登録順に配列の末尾に追加する。この処理はO(n)でできる。 次に、この配列をキーの昇順になるように整列する。この処理はO(n log n)のものがある。

合計の計算量は、

O(n) + O(n log n) = O(max(n ,n log n)) = O(n log n)

結論として二分探索法は「プログラムの実行中に頻繁にデータ登録を行いながら同時に探索も行う」という使い方には向かない

2.2.5ハッシュ法

ハッシュ法とは、キーの値を配列の添字へと変換する関数を利用することにより高速に探索を行うアルゴリズム。

例) 大きさ100の配列を使って整数のキーを持つデータを扱うには、ハッシュ関数h(key)を以下のように定める。

h(key) = key % 100

ハッシュ関数が返す値をハッシュ値といい、keyを与えられた時にh(key)を計算するとデータの格納場所が分かる。 例) key = 2034の場合

h(2034) % 100 = 34

なのでこのデータは配列の添字34に格納されている。

ハッシュ法の計算量について考える。ハッシュ関数は基本操作のみで実現できるのでハッシュの衝突を考えなければO(1)となる。 衝突した場合は面倒だが、登録されているデータに比べて、ハッシュ配列の大きさが十分大きければ衝突が発生する可能性が低くなる。

2.2.6 アルゴリズムを選択する基準

計算量で比較すると

ハッシュ法 > 二分探索法 > 線形探索法

となる。 しかし、計算量以外の得失として以下のものがある。

  1. 線形探索法ではデータを登録した順序が保存されているが、他2つでは失われる
  2. ハッシュ法では、登録するデータの個数より大きい配列を用意する必要がある。また、ハッシュ関数の選択しだいではハッシュ値が頻繁に衝突して性能が大幅に低下するおそれがある。

このように実際のプログラムで使用するにあたって、選択基準は様々である。 以下に、アルゴリズムを選択するにあたって計算量以外に考慮すべきファクターをあげる。

  1. nが小さい時はオーダーよりも定数の大小の影響が大きい
  2. 実装の手間を
  3. 時間と空間のトレードオフ

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

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