【線形探索法とは】計算式と例題

線形探索法とは?計算式と例題についてまとめました。

【例題】応用情報技術者試験平成26年春期　問6

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

(解答)
データ数がnの線形リストを先頭から探索する場合、平均探索回数は(n＋1)／2回で表されます。
・最小探索回数:1回
・最大探索回数:n回
※データが存在しない場合は、必ずリストの最後まで検索することになるので探索回数は常にn回

データが存在しない確率:a
データが存在する確率:(1－a)

よって、この処理における平均探索回数は、

対象がリストに存在する場合の平均探索回数×対象が存在する確率＝{(n＋1)／2}×(1－a)と、
対象がリストに存在しない場合の探索回数×対象が存在しない確n×aを合算したものとなります。

答えは{(n＋1)／2}×(1－a)+(n×a)