令和5年度春期 応用情報技術者試験 午前 問6
従業員番号と氏名の対がn件格納されている表に線形探索法を用いて，与えられた従業員番号から氏名を検索する。この処理における平均比較回数を求める式はどれか。ここで，検索する従業員番号はランダムに出現し，探索は常に表の先頭から行う。また，与えられた従業員番号がこの表に存在しない確率をaとする。
※選択肢ア〜エは上の図表内に記載されています。
解答・解説を見る
正解：エ
AI解説
従業員番号が表に存在する場合(確率1-a)の平均比較回数は(n+1)/2、存在しない場合(確率a)は必ず全件のn回を比較するので、全体の平均比較回数はこれらを発生確率で重み付けした(1-a)×(n+1)/2+a×nという式で表される。 ア: 存在確率での重み付けや比較回数の項が正しくない式である。 イ: 同様に、存在する場合・存在しない場合の比較回数の扱いが条件を満たさない式である。 ウ: 同様に、確率aによる重み付けの仕方が正しくない式である。 エ: 正解。(1-a)×(n+1)/2+a×nの形で、存在する場合の平均(n+1)/2と存在しない場合の全件探索nを、それぞれの発生確率(1-a)とaで正しく重み付けした式である。 💡 線形探索の平均比較回数は「見つかる場合は先頭から見つかる位置までの平均=(n+1)/2」「見つからない場合は必ずn回」という2パターンを、それぞれの発生確率で按分するのが定石である。
出典：令和5年度 春期 応用情報技術者試験 午前 問6 ／ 独立行政法人情報処理推進機構（IPA）
※Web掲載用に表記を一部変更しています。図表はIPA公式問題冊子から引用しています。著作権はIPAに帰属します。
※Web掲載用に表記を一部変更しています。図表はIPA公式問題冊子から引用しています。著作権はIPAに帰属します。