今回も「明解 Javaによるアルゴリズムとデータ構造」を参照します。 この本に掲載されているサンプルプログラムは著者の後援会のサイトからダウンロードできますが、 文字コードが Shift JIS なため、UTF-8 に変換したものを以下に置いておきます。
多くの要素を持つデータの中から、 条件にあう要素を探し出すことを探索(searching)と言います。
ランダムに並んだデータから、一つずつ取り出して探していくのが線形探索です。 配列を先頭から調べていくのが典型例で、すでに体験済みの手法でしょう。
2分探索は、ソートされたデータから要素を探すアルゴリズムです。
アルゴリズムの良し悪しを測る1つの指標として、計算量があります。 ここでは特に時間計算量を扱います。 時間計算量とは計算にかかる時間を指標としたもので、 時間計算量が小さいほどよいアルゴリズムということになります。
データを処理するアルゴリズムでは、 データ数 n が大きくなったときに、どのように処理の量が増加するかが問題となります。 データ数 n に比例して処理が増える場合、時間計算量は O(n) と表現されます。 これは、n のオーダー(order)で処理が増えるという意味です。 線形探索であれば、データ数に比例して処理が増えるのは自明なので、 線形探索の計算量は O(n) です。
2分探索ではどうでしょうか。 2分探索では、データを 1/2 に分ける処理を繰り返します。 この繰り返しの回数を x としましょう。 データ数を n とするとき、 n が 2倍になったとしても、x は 1 しか増えません。 つまり、x は n に比例するよりもゆっくりと増えます。
| データ数 | 分割回数 |
|---|---|
| 2 | 1 |
| 4 | 2 |
| 8 | 3 |
| 16 | 4 |
| 32 | 5 |
| 64 | 6 |
| n | x |
n = 2x が成り立ちますので、両辺 log をとると log n = x となります。 つまり、2分探索の時間計算量は O(log n) です。
バブルソートの計算量は O(n2) です。
クイックソートの計算量は O(n log n) です。ただし最悪の計算量は O(n2) となります。
マージソートの計算量は、マージが O(n)、マージソート全体で O(n log n) となります。