令和5年度 春期 応用情報技術者試験 午前 問6

線形探索法（リニアサーチ）における平均比較回数を求める問題です。探索対象が表に存在する場合と存在しない場合に分けて期待値を計算します。

1. 探索対象が表に存在する場合 与えられた従業員番号が表に存在する確率は $(1-a)$ です。ランダムに出現するため、1件目で見つかる、2件目で見つかる、...、$n$件目で見つかる確率はそれぞれ等しくなります。この場合の平均比較回数は、$(1 + 2 + \dots + n) \div n = \frac{n+1}{2}$ 回となります。
2. 探索対象が表に存在しない場合 与えられた従業員番号が表に存在しない確率は $a$ です。この場合、表の先頭から末尾まですべてのデータを比較して初めて「存在しない」ことがわかるため、比較回数は必ず $n$ 回となります。 全体の平均比較回数は、それぞれの期待値の和となるため、以下の式で求められます。 $$\frac{n+1}{2} \times (1-a) + n \times a = \frac{(n+1)(1-a)}{2} + na$$

各選択肢の解説

• ア: 誤り。存在する場合の平均比較回数に、さらに $na$ を掛けたような不適切な式です。
• イ: 誤り。探索対象が存在する場合の比較回数の期待値のみを計算しており、存在しない場合の比較回数が考慮されていません。
• ウ: 誤り。存在しない場合の比較回数について、回数や確率の考慮が不正確な式です。
• エ: 正解。存在する場合と存在しない場合それぞれの期待値の和を正しく表しています。