平成26年度 春期 応用情報技術者試験 午前 問6
テクノロジ／アルゴリズム従業員番号と氏名の対がn件格納されている表に線形探索法を用いて，与えられた従業員番号から氏名を検索する。この処理における平均比較回数を求める式はどれか。ここで，検索する従業員番号はランダムに出現し，探索は常に表の先頭から行う。また，与えられた従業員番号がこの表に存在しない確率をaとする。
出典：平成26年度 春期 応用情報技術者試験 午前 問6
- ア(n+1)/2 ＋ na/2
- イ(n+1)(1−a)/2
- ウ(n+1)(1−a)/2 ＋ n/2
- エ(n+1)(1−a)/2 ＋ na
正解：エ
解説
目的の従業員番号が表に存在する確率は(1－a)であり，その場合の平均比較回数は先頭から末尾まで一様に分布するため(n＋1)/2回である。存在しない確率はaで，その場合は必ず表の全n件を比較してから「該当なし」と判定するのでn回になる。したがって全体の平均比較回数は(1－a)×(n＋1)/2＋a×n＝(n＋1)(1－a)/2＋naとなる。
選択肢ごとの解説
- ア誤り。存在しない場合の比較回数をna/2としているが，線形探索では存在しないと判定するまでに表の全n件を比較する必要があるため誤りである。
- イ誤り。存在する確率(1－a)を考慮した項はあるが，存在しない確率aの場合の比較回数（n回）を加算していないため不完全な式である。
- ウ誤り。存在しない場合の比較回数をn/2としているが，正しくはn回であるため誤りである。
- エ正しい。存在する場合（確率1－a）の平均(n＋1)/2と，存在しない場合（確率a）のn回を合算した(n＋1)(1－a)/2＋naが平均比較回数として正しい。