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

問題文

従業員番号と氏名の対が

n

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

選択肢

ア：

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

イ：

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

ウ：

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

エ：

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

（正解）

従業員番号検索の平均比較回数【午前2 解説】

要点まとめ

結論：平均比較回数は「 $\frac{( n + 1 ) ( 1 - a )}{2} + na$ 」で表される。
根拠：存在する場合は平均 $\frac{n + 1}{2}$ 回、存在しない場合は全件 $n$ 回の比較が必要。
差がつくポイント：存在しない確率 $a$ を考慮し、両ケースの比較回数を加重平均する点が重要。

正解の理由

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

\frac{n + 1}{2}

回です。存在しない場合は全件を比較しても見つからないため、比較回数は

n

回となります。
検索対象が存在する確率は

1 - a

、存在しない確率は

a

なので、平均比較回数は

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

となり、選択肢の中でエが正解です。

よくある誤解

存在しない場合の比較回数を半分程度と誤解しがちですが、線形探索では全件比較が必要です。
また、存在する場合の平均比較回数は単純に

n /2

ではなく、

\frac{n + 1}{2}

である点も注意が必要です。

解法ステップ

線形探索の特徴を理解する（先頭から順に比較）。
対象が存在する場合の平均比較回数を求める（ $\frac{n + 1}{2}$ 回）。
対象が存在しない場合の比較回数は全件比較の $n$ 回。
存在確率 $(1 - a)$ と不存在確率 $a$ を用いて加重平均を計算。
式を整理し、選択肢と照合する。

選択肢別の誤答解説

ア: $\frac{( n + 1 ) na}{2}$
→ 存在しない場合の比較回数を誤って平均的に扱い、存在する場合を無視している。
イ: $\frac{( n + 1 ) ( 1 - a )}{2} + \frac{n}{2}$
→ 存在しない場合の比較回数を $n /2$ と誤認している。
ウ: $\frac{( n + 1 ) ( 1 - a )}{2}$
→ 存在しない場合の比較回数を考慮していない。
エ: $\frac{( n + 1 ) ( 1 - a )}{2} + na$
→ 正しく存在・不存在両方のケースを加重平均している。

補足コラム

線形探索はデータが整列されていない場合に有効ですが、平均比較回数が多いため大規模データには不向きです。
二分探索などの高速探索法は整列済みデータに適用し、比較回数を大幅に減らせます。
また、存在しない場合の比較回数は必ず最大となるため、検索効率の評価に重要な要素です。

FAQ

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

\frac{n + 1}{2}

なのですか？
A: 探索対象が均等に分布しているため、最初から最後までの比較回数の平均が

\frac{1 + 2 + \dots + n}{n} = \frac{n + 1}{2}

となるからです。

Q: 存在しない場合の比較回数はなぜ

n

回ですか？
A: 線形探索は先頭から順に全件を比較し、最後まで見つからなければ不存在と判断するため、全件比較が必要です。

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

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

\ せっかくなら /

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

クイズ画面へ遷移する→

すぐに利用可能！

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

問題文

選択肢