線形探索の平均計算量
n 個の要素をもつ配列を先頭から順に調べる線形探索の平均計算量(オーダ)はどれか。
解説を見る
線形探索は先頭から順に比較するため、平均でおよそ n/2 回、最悪で n 回の比較が必要。計算量は O(n)。
誤答の解説
BO(log n) は整列済み配列に対する2分探索の計算量。
CO(1) はハッシュ表の平均探索など要素数に依存しない場合。
DO(n^2) は二重ループになる処理の計算量。
ヒント
・先頭から1つずつ、は要素数に比例する。
・先頭から1つずつ、は要素数に比例する。