探索方法とその実行時間のオーダの正しい組合せはどれか。ここで，探索するデータの数をn とし，ハッシュ値が衝突する（同じ値になる）確率は無視できるほど小さいものとする。また，実行時間のオーダが
であるとは，n 個のデータを処理する時間がc（ c は定数）で抑えられることをいう。
用語を抑えておけば簡単に解ける問題。
まずオーダというのは「だいたいの桁数」くらいの意味で覚えておけばいい。
3500とか7500は千の位だから「千のオーダ」、153万とか693万7千とかは百万の位だから「百万のオーダ」とざっくりいったりする。物理学者が好んで使う言葉だ。
2分探索はバイナリサーチとも呼ばれ、その名の通りデータを2分しながら探す探索法だ。
データが昇順に並んでいる必要がある。
分割する方法はデータの中央値を求め、それと探索するデータを比較。大小関係を求めて探す範囲を狭めていく。
話を単純にして考えよう。
以下のように並んでいる中から、8を探したいとする。
1 2 3 4 5 7 8
このとき中央値は4だから、それと大小を比較して7の方が大きいため5以降を探せばいいことになる。
同様に、5 7 8の並びから中央値の7と8を比較。
8の方が大きいから、8の並びに求めるデータがあることがわかる。
8の並びは8ひとつだけだから、ここでデータを見つけることができて探索終了。
8個のデータの中から、3回で見つけることができた。
オーダとしてはlog2nである。
次は線形探索。
これはデータを順番に上から探していく。
順番に探していくので、最悪の場合はそのデータ量と同じだけの探索が必要になる。
2分探索と同じように、単純化して考えよう。
以下の中から8を探すと
1 2 3 4 5 7 8
上から順番に探していくので、データの比較回数は8回になる。
つまり、オーダとしてはnだ。
続いてハッシュ探索。
衝突が無視できるほど少ないなら常にデータのアドレスは一回で探せる。
「Aというデータは5番」
「Bというデータは7番」
「Cというデータは9番」
…のように「(3+2n)%500」のように順番に格納されているとして、3+2n番が500を超えると余りが重複しだすため、別のアドレスにデータ格納しなければならない。それを衝突(コリジョン)というが、500以下ならば一回で探索が終了する。
「ハッシュのオーダは1」と覚えよう。
以上から、正解はアである。
探索アルゴリズムは午後の試験でも必要になってくるので、あやふやにはしないこと。
実際にプログラムを組めば理解が進むが、まずは単純化してでもイメージは掴んで欲しい。