アルゴリズムとプログラミング
平成24年度 秋期 基本情報技術者試験 午前 問3
探索方法とその実行時間のオーダの適切な組合せはどれか。ここで，探索するデータの数を n とし，ハッシュ値が衝突する（同じ値になる）確率は無視できるほど小さいものとする。また，実行時間のオーダが n^2 であるとは，n 個のデータを処理する時間が cn^2（c は定数）で抑えられることをいう。
| 2分探索 | 線形探索 | ハッシュ探索 | |
|---|---|---|---|
| ア | log_2 n | n | 1 |
| イ | n log_2 n | n | log_2 n |
| ウ | n log_2 n | n^2 | 1 |
| エ | n^2 | 1 | n |
- ア [表] 2分探索: log_2 n / 線形探索: n / ハッシュ探索: 1
- イ [表] 2分探索: n log_2 n / 線形探索: n / ハッシュ探索: log_2 n
- ウ [表] 2分探索: n log_2 n / 線形探索: n^2 / ハッシュ探索: 1
- エ [表] 2分探索: n^2 / 線形探索: 1 / ハッシュ探索: n
出典：平成24年度 秋期 基本情報技術者試験 午前 問3
答えと解説を見る
正解：ア
覚える知識
2分探索法の計算量(log2 n)
2分探索の計算量はO(log2 n)、線形探索はO(n)、衝突を無視したハッシュ探索はO(1)である。
この問題で必要なこと
2分探索はlog2 n、線形探索はn、ハッシュ探索は衝突を無視すれば1のオーダである。
ひっかけ
2分探索をn log nと取り違えさせたり、線形探索をn²と取り違えさせたりする。
この知識の出題：本試験系 3 回・免除試験 13 回（公開問題での観測値）