問題
整列された n 個のデータの中から、求める要素を 2 分探索法で探索する。この処理の計算量のオーダを表すものはどれか。
選択肢
- 1log n
- 2n
- 3n²
- 4n log n
正解
1. log n
詳しい解説を見る解説を閉じる
解説
2 分探索法は探索範囲を毎回半分に絞り込むため、最悪でも log₂ n 回程度の比較で目的の要素にたどり着く。よって計算量のオーダは O(log n) であり「ア」が正しい。線形探索の O(n) と比較して、データ数が増えても探索回数の増加が緩やかなのが特徴である。(出典: 平成27年度 春期 基本情報技術者試験 午前 問6)
一問一答
科目A 180問+科目B 60問