問題プレビューID: 8c521455基本情報技術者試験 午前免除試験 2016年1月24日

問 4
基本情報技術者試験 午前免除試験 2016年1月24日

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

Label

2分探索

線形探索

ハッシュ探索

ア

log⁡2n\log_2 n

nn

11

イ

nlog⁡2nn \log_2 n

nn

log⁡2n\log_2 n

ウ

nlog⁡2nn \log_2 n

n2n^2

11

エ

n2n^2

11

nn

解説

正解は「ア」です。

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

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

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

関連問題

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