2 分探索において,データの個数が 4 倍になると,最大探索回数はどうなるか。ここで,データの個数は十分に多いものとする。
1 回増える。
2 回増える。
約 2 倍になる。
約 4 倍になる。
正解は「イ」です。
2 分探索では,探索のたびに対象範囲が半分になるため,最大探索回数はデータの個数 nnn の 2 を底とする対数 log2n\log_2 nlog2n に比例します。データの個数が 4 倍になると,最大探索回数は log2(4n)=log2n+log24=log2n+2\log_2(4n) = \log_2 n + \log_2 4 = \log_2 n + 2log2(4n)=log2n+log24=log2n+2 となり,2 回増えることになります。
本文が同じ・似ている問題を表示しています