従業員番号と氏名の対がｎ件格納されている表に線形探索法を用いて、与えられた従業員番号から氏名を検索する。この処理における平均比較回数を求める式はどれか。ここで、検索する従業員番号はランダムに出現し、探索は常に表の先頭から行う。また、与えられた従業員番号がこの表に存在しない確率をaとする。

【解答】

「与えられた従業員番号がこの表に存在しない確率をａとする」ということは、「与えられた従業員番号がこの表に存在する確率」は１－ａとなる。

また、全体の平均比較回数は

与えられた従業員番号がこの表に存在する確率・平均比較回数

＋

与えられた従業員番号がこの表に存在しない確率・平均比較回数

で表すことが出来る。

ここで、ｎ件のデータを線形探索法で検索する場合、平均比較回数はデータの中に従業員番号が存在する場合と、存在しない場合でそれぞれ異なり、従業員番号が存在する場合の平均比較回数は、

（１＋ｎ）／２　と表すことが出来る。

一方、従業員番号が存在しない場合の平均比較回数は

ｎ　と表すことが出来る。

さらに、従業員番号が存在する場合は１－ａ、従業員番号が存在しない確率はａであるから、

（１－ａ）・（１＋ｎ）／２　＋　ａ・ｎ

となる。