従業員番号と氏名の対がn件格納されている表に線形探索法を用いて，与えられた従業員番号から氏名を検索する。
この処理における平均比較回数を求める式はどれか。
ここで，検索する従業員番号はランダムに出現し，探索は常に表の先頭から行う。
また，与えられた従業員番号がこの表に存在しない確率をaとする。
正答4
解説
正解は4です。
線形探索で、探す番号が表にある場合とない場合に分けて比較回数の期待値を求めます。
【計算】
表に存在する確率は1-aです。
存在する場合、目的の番号は1番目からn番目まで等しい確率で現れます。
このときの平均比較回数は(1+2+…+n)/n=(n+1)/2回です。
存在しない確率はaで、このときは表の全件と比較するのでn回です。
平均比較回数＝(1-a)×(n+1)/2＋a×n＝(n+1)(1-a)/2＋naです。
【選択肢別解説】
1：× (n+1)na/2は、存在する場合の(n+1)/2と、存在しない場合のnaを掛け合わせた形です。
期待値は場合ごとの「確率×比較回数」を足して求めるので、掛け合わせるのは誤りです。
存在する確率1－aも使われていません。
2：× (n+1)(1-a)/2は存在する場合の項だけで、存在しない場合に必要なn回の比較が抜けています。
3：× 存在しない場合の項がn/2になっています。
見つからないときは途中で止まらず全n件を比較するので、正しくはnaです。
4：○ 存在する場合の(n+1)(1-a)/2と、存在しない場合のnaを足した式であり、計算結果と一致します。
【ポイント】
期待値は「確率×その場合の値」を場合ごとに足して求めます。
線形探索の平均比較回数は、見つかる場合(n+1)/2回、見つからない場合n回と覚えましょう。