問題プレビューID: 2e401cb9基本情報技術者試験 午前免除試験 2017年7月23日

問 4
基本情報技術者試験 午前免除試験 2017年7月23日

探索方法とその実行時間のオーダーの適切な組合せはどれか。ここで,探索するデータの数を nn とし,ハッシュ値が衝突する(同じ値になる)確率は無視できるほど小さいものとする。また,実行時間のオーダーが n2n^2 であるとは,nn 個のデータを処理する時間が cn2cn^2(cc は定数)で抑えられることをいう。

選択肢2分探索線形探索ハッシュ探索
アlog⁡2n\log_2 nnn11
イnlog⁡2nn \log_2 nnnlog⁡2n\log_2 n
ウnlog⁡2nn \log_2 nn2n^211
エn2n^211nn
解説

正解は「ア」です。

  • 2 分探索:整列済みのデータを中央で二分しながら探索範囲を半分に絞るため,比較回数は log⁡2n\log_2 n のオーダーになる。
  • 線形探索:先頭から順に目的のデータを探すため,最悪の場合すべてのデータを調べることになり,nn のオーダーになる。
  • ハッシュ探索:ハッシュ関数で格納位置を直接求めてアクセスするため,衝突を無視できるなら 1 回のアクセスで目的のデータに到達でき,11 のオーダーになる。

したがって,組合せが正しいのは「ア」です。

  • イ・ウ・エ: 2 分探索やハッシュ探索のオーダーの見積りが誤っており,適切ではない。

関連問題

本文が同じ・似ている問題を表示しています