基本情報技術者 予想問題｜A 第16問

解説

線形探索は配列の先頭から順に1つずつ目的の値と比較する探索法である。目的の要素が先頭にあれば1回、末尾にあればn回の比較が必要で、位置が一様に分布すると仮定すると平均は (1+2+…+n)÷n = (n+1)/2、概算でn/2回となる。よって「n/2」が正解である。1回は最良の場合に過ぎず、平均を表さない。log n（正確には log2 n）は整列済みデータに対する二分探索の比較回数である。n^2は単純な整列アルゴリズムの計算量であり、探索の比較回数ではない。「線形探索は平均n/2回・最悪n回、二分探索は約log2 n回」という対比は頻出であり、整列済みかどうかという適用条件の違いも併せて押さえておきたい。