| 基本情報技術者試験 |
2004年度 ＝ 平成16年度・春期 |
午前 |
問11 |
探索方法とその実行時間のオーダの正しい組合せはどれか。ここで、探索するデータ数をn とし、ハッシュ値が衝突する（同じ値になる）確率は無視できるほど小さいものとする。また、実行時間のオーダがn 2であるとは、n 個のデータを処理する時間がcn 2（c は定数）で抑えられることをいう。
|
| ２分探索
| 線形探索
| ハッシュ探索
|
| ア
| log2n
| n
| 1
|
| イ
| n log2n
| n 2
| 1
|
| ウ
| n 2
| 1
| n
|
| エ
| n log2n
| n
| log2n
|
ア
各探索法の実行時間のオーダは、探索に要する平均比較回数から求められます。
■ ２分探索
整列済みの配列の中央に位置する要素と等しいか／大きいか／小さいかの判断を行い、探索すべき範囲を半分ずつに絞り込んでいく探索法であり、探索に要する平均比較回数はlog2nです。したがって、オーダはlog2nです。
■ 線形探索
線形探索法は、配列の先頭から順に比較を行っていく探索法であり、探索に要する平均比較回数はn / 2です。したがって、オーダはnです。
■ ハッシュ探索
キー値に対して何らかの変換関数を適用することによって、そのデータを格納する配列の添字を求める手法です。キー値から直接添字を求められるため、（衝突が発生しない限り）比較の回数はデータ数に依存することなく1回だけとなります。したがって、オーダは1です。
