データ構造とアルゴリズム
異なる100個の値が入った配列から、先頭から順に1つずつ比べる線形探索で目的の値を探す。目的の値は必ず配列の中にあり、どの位置にある確率も等しいとき、比較の回数の平均はいくらか。
- A約7回
- B50.5回
- C100回
答えと解説を見る
正解：B. 50.5回
目的の値が k 番目にあれば比較は k 回なので、平均は (1 + 2 + … + 100) / 100 = 50.5回、一般には (n + 1)/2 回です。最良の場合(先頭にある)は1回、最悪の場合(末尾にある)は100回で、平均も最悪も n に比例するので計算量は O(n) です。約7回は log₂ 100 ≈ 6.6 に当たる二分探索の回数で、データが整列されていなければ使えません。
- A. 二分探索の最大の回数に近い値で、線形探索の平均ではありません。
- B. 正しい。(1 + 2 + … + 100)/100 = 50.5回で、一般には (n + 1)/2 回です。
- C. 最悪の場合(目的の値が末尾にある場合)の回数です。