問題プレビューID: 40ca918f基本情報技術者試験 午前免除試験 2026年1月25日

問 6
基本情報技術者試験 午前免除試験 2026年1月25日

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

解説

正解は「イ」です。

2 分探索では,探索のたびに対象範囲が半分になるため,最大探索回数はデータの個数 nn の 2 を底とする対数 log⁡2n\log_2 n に比例します。データの個数が 4 倍になると,最大探索回数は log⁡2(4n)=log⁡2n+log⁡24=log⁡2n+2\log_2(4n) = \log_2 n + \log_2 4 = \log_2 n + 2 となり,2 回増えることになります。

  • ア: 2 倍では 1 回しか増えません。
  • ウ・エ: 最大探索回数はデータ数の対数に比例するため,個数そのものに比例して 2 倍や 4 倍にはなりません。

関連問題

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