【線形探索法とは】計算式と例題

線形探索法とは?計算式と例題についてまとめました。

【例題】応用情報技術者試験 平成26年春期 問6

(問題)
従業員番号と氏名の対がn件格納されている表に線形探索法を用いて、与えられた従業員番号から氏名を検索する。
この処理における平均比較回数を求める式はどれか。
ここで検索する従業員番号はランダムに出現し、探索は常に表の先頭から行う。
また与えられた従業員番号がこの表に存在しない確率をaとする。

(解答)
データ数がnの線形リストを先頭から探索する場合、平均探索回数は(n+1)/2回で表されます。
・最小探索回数:1回
・最大探索回数:n回
※データが存在しない場合は、必ずリストの最後まで検索することになるので探索回数は常にn回

データが存在しない確率:a
データが存在する確率:(1-a)

よって、この処理における平均探索回数は、

対象がリストに存在する場合の平均探索回数×対象が存在する確率={(n+1)/2}×(1-a)と、
対象がリストに存在しない場合の探索回数×対象が存在しない確n×aを合算したものとなります。

答えは{(n+1)/2}×(1-a)+(n×a)

【アルゴリズム】整列、併合、探索、再帰、文字列処理、流れ図の理解、アルゴリズム設計
整列、併合、探索、再帰、文字列処理、流れ図の理解、アルゴリズム設計についてまとめました。
【情報処理入門】テクノロジ系、マネジメント系、ストラテジ系、資格試験
情報処理の基礎知識(テクノロジ系、マネジメント系、ストラテジ系)や資格試験についてまとめました。

コメント

タイトルとURLをコピーしました