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