アルゴリズム (全82問中14問目)
No.14
従業員番号と氏名の対がn件格納されている表に線形探索法を用いて，与えられた従業員番号から氏名を検索する。この処理における平均比較回数を求める式はどれか。ここで，検索する従業員番号はランダムに出現し，探索は常に表の先頭から行う。また，与えられた従業員番号がこの表に存在しない確率をaとする。
出典：平成26年春期 問6
- [この問題の出題歴]
- ソフトウェア開発技術者 H20秋期 問12
分類
テクノロジ系 » アルゴリズムとプログラミング » アルゴリズム
正解
エ
解説
データ数がnの線形リストを先頭から探索する場合、最小探索回数は1回，最大探索回数はn回なので、平均探索回数は(n＋1)／2回で表されます。
またデータが存在しない場合は、必ずリストの最後まで検索することになるので探索回数は常にn回となります。
データが存在しない確率がaなので、データが存在する確率は(1−a)です。
この処理における平均探索回数は、
対象がリストに存在する場合の平均探索回数×対象が存在する確率
＝{(n＋1)／2}×(1−a)
と、
対象がリストに存在しない場合の探索回数×対象が存在しない確
n×a
を足し合わせた値になります。
この数式を整えると、
になります。
またデータが存在しない場合は、必ずリストの最後まで検索することになるので探索回数は常にn回となります。
データが存在しない確率がaなので、データが存在する確率は(1−a)です。
この処理における平均探索回数は、
対象がリストに存在する場合の平均探索回数×対象が存在する確率
＝{(n＋1)／2}×(1−a)
と、
対象がリストに存在しない場合の探索回数×対象が存在しない確
n×a
を足し合わせた値になります。
この数式を整えると、
になります。