応用情報技術者 2014年春期午前2 問06

問題文

従業員番号と氏名の対が

n

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

選択肢

ア：

\frac{n + 1}{2} + \frac{na}{2}

イ：

\frac{( n + 1 ) ( 1 - a )}{2}

ウ：

\frac{( n + 1 ) ( 1 - a )}{2} + \frac{n}{2}

エ：

\frac{( n + 1 ) ( 1 - a )}{2} + na

（正解）

線形探索法の平均比較回数の計算【午前2 解説】

要点まとめ

結論：平均比較回数は「 $\frac{( n + 1 ) ( 1 - a )}{2} + na$ 」で表され、正解はエです。
根拠：存在する場合は平均で半分の比較、存在しない場合は全件比較が必要で、その確率を加味します。
差がつくポイント：存在しない確率 $a$ を考慮し、存在時と非存在時の比較回数を正しく加算できるかが重要です。

正解の理由

線形探索法では、対象が表に存在する場合、平均比較回数は先頭から順に探索するため、

1

件目から

n

件目までの平均で

\frac{n + 1}{2}

回です。
しかし、問題では対象が存在しない確率

a

も考慮します。存在しない場合は全件比較の

n

回となります。
したがって、平均比較回数は

(1 - a) \times \frac{n + 1}{2} + a \times n

となり、選択肢の中でこれに該当するのはエです。

よくある誤解

存在しない場合の比較回数を半分と誤解し、

na /2

とする選択肢アを選びがちです。
また、存在する場合の平均比較回数を全件比較の

n

と誤認することもあります。

解法ステップ

線形探索で対象が存在する場合の平均比較回数は $\frac{n + 1}{2}$ と理解する。
対象が存在しない場合は全件比較の $n$ 回となることを確認する。
対象が存在する確率は $1 - a$ 、存在しない確率は $a$ であることを把握する。
それぞれのケースの比較回数に確率を掛けて合計する。
式を整理し、選択肢と照合する。

選択肢別の誤答解説

ア: $\frac{n + 1}{2} + \frac{na}{2}$
存在しない場合の比較回数を半分の $\frac{n}{2}$ と誤っている。
イ: $\frac{( n + 1 ) ( 1 - a )}{2}$
存在しない場合の比較回数を無視している。
ウ: $\frac{( n + 1 ) ( 1 - a )}{2} + \frac{n}{2}$
存在しない場合の比較回数を半分の $\frac{n}{2}$ と誤っている。
エ: $\frac{( n + 1 ) ( 1 - a )}{2} + na$
正しく存在する場合としない場合の比較回数を確率で加算している。

補足コラム

線形探索法は単純で実装が容易ですが、平均計算量は

O (n)

と大きいため、大規模データには不向きです。
ハッシュ法や二分探索木などの高速探索法と比較して、探索効率の違いを理解しておくことが重要です。

FAQ

Q: なぜ存在しない場合は全件比較になるのですか？
A: 線形探索は先頭から順に比較するため、対象がなければ最後まで比較を続ける必要があるからです。

Q: 存在する場合の平均比較回数はなぜ

\frac{n + 1}{2}

ですか？
A: 対象がランダムに分布しているため、平均的に半分の位置で見つかると考えられるからです。

関連キーワード: 線形探索、平均比較回数、探索アルゴリズム、確率、アルゴリズム解析

← 前の問題へ次の問題へ →

\ せっかくなら /

応用情報技術者を
クイズ形式で学習しませんか？

クイズ画面へ遷移する→

すぐに利用可能！

応用情報技術者 2014年 春期 午前2 問06

問題文

選択肢