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

問 6
基本情報技術者試験 午前免除試験 2023年12月10日

2 分探索において,データの個数が 4 倍になると,最大探索回数はどうなるか。ここで,データの個数は十分に多いものとする。

解説

正解は「イ」です。

2 分探索では,比較のたびに探索範囲が約半分になるので,データの個数を nn とすると最大探索回数はおよそ log⁡2n\log_2 n 回です。データの個数が 4 倍になると,最大探索回数は

log⁡24n−log⁡2n=log⁡24=2\log_2 4n - \log_2 n = \log_2 4 = 2

となり,2 回増えることになります。

  • ア: データが 2 倍のときに 1 回増えます。
  • ウ・エ: 探索回数はデータ個数に比例して増えるのではなく,対数的にしか増えません。

関連問題

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