応用情報技術者試験令和5年春午前問6 解説付き過去問

問題

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

(n＋1)na2

(n＋1)(1－a)2

(n＋1)(1－a)2＋n2

(n＋1)(1－a)2＋na

この問題は、線形探索法（リニアサーチ）において、検索対象が存在する場合と存在しない場合の両方を考慮して、平均比較回数を求めるものです。以下の手順で解説します。

線形探索法の特徴
線形探索法は、データの先頭から順番に1件ずつ比較を行っていき、目的のデータが見つかるか、最後まで見つからなければ探索を終了する方式です。
このアルゴリズムでは、データが見つかる位置によって必要な比較回数が変動します。
データが見つかる場合の平均比較回数
目的のデータが n 件の中に存在する場合、先頭から末尾まで一様な確率で出現すると仮定すると、平均的には n＋12 回の比較で見つかります。
データが見つからない場合の比較回数
目的のデータがリスト内に存在しない場合は、最後のデータまで全て比較して確認する必要があるため、n 回の比較が常に必要となります。
全体の平均比較回数の求め方
検索対象が存在しない確率を a とすると、存在する確率は (1－a) になります。
したがって、平均比較回数は以下の2つの項の合計で表されます。

これらを加えることで、平均比較回数は次の式になります。

(n＋1)(1－a)2 ＋ na

したがって、この探索処理における平均比較回数は、(n＋1)(1－a)2 ＋ na です。