基本情報技術者試験 2007年度 = 平成19年度・秋期 午前 問11

 探索方法とその実行時間のオーダの正しい組合せはどれか。ここで、探索するデータ数をn とし、ハッシュ値が衝突する(同じ値になる)確率は無視できるほど小さいものとする。また、実行時間のオーダがn2であるとは、n 個のデータを処理する時間がcn 2c は定数)で抑えられることをいう。

2分探索 線形探索 ハッシュ探索
log2n n 1
n log2n n log2n
n log2n n 2 1
n 2 1 n

解答



解説

 各探索法の実行時間のオーダは、探索に要する平均比較回数から求められます。

2分探索
 整列済みの配列の中央に位置する要素と等しいか/大きいか/小さいかの判断を行い、探索すべき範囲を半分ずつに絞り込んでいく探索法であり、探索に要する平均比較回数はlog2n です。したがって、オーダはlog2nです。

線形探索
 線形探索法は、配列の先頭から順に比較を行っていく探索法であり、探索に要する平均比較回数はn / 2です。したがって、オーダはnです。

ハッシュ探索
 キー値に対して何らかの変換関数を適用することによって、そのデータを格納する配列の添字を求める手法です。キー値から直接添字を求められるため、(衝突が発生しない限り)比較の回数はデータ数に依存することなく1回だけとなります。したがって、オーダは1です。


BohYoh.comトップページへ