令和5年度 春期 応用情報技術者試験 午前 問6
テクノロジ／アルゴリズム従業員番号と氏名の対が n 件格納されている表に線形探索法を用いて，与えられた従業員番号から氏名を検索する。この処理における平均比較回数を求める式はどれか。ここで，検索する従業員番号はランダムに出現し，探索は常に表の先頭から行う。また，与えられた従業員番号がこの表に存在しない確率を a とする。
出典：令和5年度 春期 応用情報技術者試験 午前 問6
- ア(n＋1)na／2
- イ(n＋1)(1−a)／2
- ウ(n＋1)(1−a)／2 ＋ n／2
- エ(n＋1)(1−a)／2 ＋ na
正解：エ
解説
従業員番号が表に存在する場合（確率 1−a），先頭から順に比較すると平均比較回数は (1＋2＋…＋n)／n＝(n＋1)／2 回です。存在しない場合（確率 a）は表の全件 n 回比較して初めて存在しないと分かります。よって平均比較回数は (n＋1)(1−a)／2 ＋ na となります。
選択肢ごとの解説
- ア誤り。(n＋1)na／2 は存在する場合の平均回数に na を乗じた形で，期待値の計算として意味をなしません。
- イ誤り。(n＋1)(1−a)／2 は存在する場合の寄与だけを表しており，存在しない場合の n 回×確率 a の項が抜けています。
- ウ誤り。存在しない場合の比較回数は n 回であり，その期待値への寄与は na です。n／2 とするのは，存在しない場合も平均 n／2 回で済むと誤解した場合の式です。
- エ正しい。存在する場合の (n＋1)／2 回×確率 (1−a) と，存在しない場合の n 回×確率 a の和です。