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