アルゴリズムとプログラミング
基本情報技術者試験 科目A免除 修了試験 20160124 実施分 問4
探索方法とその実行時間のオーダの適切な組合せはどれか。ここで，探索するデータの数を 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 |
答えを選ぶ
出典：基本情報技術者試験 科目A免除 修了試験 20160124 実施分 問4（問題文は IPA の公開問題。解説は当サイト作成）
答えと解説を見る
正解：ア
覚える知識
2分探索法の計算量(log2 n)
2分探索の計算量はlog2 n、線形探索はn、ハッシュ探索は(衝突が無視できれば)1のオーダである。
この問題で必要なこと
2分探索はO(log2 n)、線形探索はO(n)、衝突が無視できるハッシュ探索はO(1)。
ひっかけ
2分探索にn log nを当てる、線形探索にn^2を当てるなど、整列や二重ループの計算量との混同。
この知識の出題：本試験系 3 回・免除試験 13 回（公開問題での観測値）