2分探索の計算量
n 個の要素をもつ整列済み配列に対する2分探索の平均計算量(オーダ)はどれか。
解説を見る
2分探索は探索範囲を毎回半分に絞り込むため、比較回数は最大でも log2(n) 程度。したがって計算量は O(log n)。
誤答の解説
AO(1) はハッシュ表の平均探索など、要素数に依存しない場合。
CO(n) は先頭から順に見る線形探索の計算量。
DO(n log n) はマージソートなど効率的な整列アルゴリズムの計算量。
ヒント
・範囲が毎回半分になる回数は何回で1になるか、を考える。