問題プレビューID: f0eb947f基本情報技術者試験 午前免除試験 2021年12月12日

問 5
基本情報技術者試験 午前免除試験 2021年12月12日

探索方法とその実行時間のオーダーの適切な組合せはどれか。ここで,探索するデータの数を 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 分探索:整列済みのデータの中央の値と比較して探索範囲を半分に絞る操作を繰り返すため,比較回数はデータ数 nn の対数に比例し,オーダーは log⁡2n\log_2 n です。
  • 線形探索:先頭から順に 1 件ずつ比較するため,最悪の場合すべてのデータを調べることになり,オーダーは nn です。
  • ハッシュ探索:キー値から格納位置を直接計算してアクセスするため,衝突が無視できるならば 1 回で目的のデータに到達でき,オーダーは 11 です。

したがって,2 分探索 log⁡2n\log_2 n,線形探索 nn,ハッシュ探索 11 の組合せである「ア」が正解です。

  • イ・ウ: 2 分探索のオーダーは nlog⁡2nn\log_2 n ではありません。
  • エ: 線形探索とハッシュ探索のオーダーが逆になっています。

関連問題

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