線形探索の平均比較回数
出典: 令和5年度 春期 応用情報技術者試験 午前 問6 (IPA)
従業員番号と氏名の対が n 件格納されている表に線形探索法を用いて，与えられた従業員番号から氏名を検索する。この処理における平均比較回数を求める式はどれか。ここで，検索する従業員番号はランダムに出現し，探索は常に表の先頭から行う。また，与えられた従業員番号がこの表に存在しない確率を a とする。
- ア (n＋1) na / 2
- イ (n＋1)(1－a) / 2
- ウ (n＋1)(1－a) / 2 ＋ n / 2
- エ (n＋1)(1－a) / 2 ＋ na
正解と解説を見る
正解: エ
- ア: 存在する場合と存在しない場合を分けて考えていない式です。
- イ: 存在しない場合 (確率 a) の n 回の比較が入っていません。
- ウ: 存在しない場合の比較回数 n に確率 a を掛けていません。
- エ: 存在する場合の (n＋1)/2 回に確率 1−a、存在しない場合の n 回に確率 a を掛けて足した式です。正しい答えです。
ポイント
- 存在する場合 (確率 1−a): 平均で (n＋1) / 2 回の比較で見つかります。
- 存在しない場合 (確率 a): 最後まで n 回比較してから「無い」と分かります。
- 平均比較回数 = (n＋1)(1−a) / 2 ＋ na です。