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