アルゴリズムとプログラミング
平成27年度 春期 基本情報技術者試験 午前 問6
整列された n 個のデータの中から，求める要素を 2 分探索法で探索する。この処理の計算量のオーダを表す式はどれか。
- ア log n
- イ n
- ウ n^2
- エ n log n
出典：平成27年度 春期 基本情報技術者試験 午前 問6
答えと解説を見る
正解：ア
覚える知識
2分探索法の計算量(log2 n)
2分探索の計算量は探索範囲を半減させる回数に等しく、O(log n) である。
この問題で必要なこと
2分探索は探索範囲を毎回半分にするので、計算量のオーダは O(log n) になる。
ひっかけ
線形探索の O(n) や整列の O(n log n)・O(n^2) と混同させる。
この知識の出題：本試験系 3 回・免除試験 13 回（公開問題での観測値）