出典：公益社団法人 日本技術士会「技術士第一次試験 過去問題」
データの個数が8倍に増加した場合の、二分探索の最大探索回数の変化として最も適切なものを選ぶ問題。二分探索の計算量はO(log n)で、8倍(2^3倍)になると、最大探索回数は3回増える。
二分探索の計算量がデータ数の対数に比例することを、具体的な倍率で確認する問題。
① 二分探索の最大回数 ≒ log₂n。データが2倍になるごとに1回増える
② 8倍 = 2³ → 3回増える(倍になるのではなく足し算で増える)。⑤の約8倍は線形探索の場合
③ ②
二分探索は、探索範囲を1回ごとに半分にしていくので、最大探索回数は、およそlog2(n)(切上げ)回である。データの個数が8倍になると、log2(8n)=log2(n)+log2(8)=log2(n)+3となり、最大探索回数は3回増加する。したがって②が最も適切である。
二分探索=O(log n)。データ数がk倍になると、最大探索回数は、log2(k)回だけ増える。線形探索=O(n)で、k倍になる。
キーワード: 二分探索、探索回数、計算量、O(log n)、アルゴリズム、対数、情報工学部門