応用情報技術者 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

（正解）

🔒 解説は解答すると表示されます

与えられた従業員番号が表に存在する確率を

1 - a

、存在しない確率を

a

とすると、探索開始は常に先頭から行うため、成功時の比較回数の期待値は位置の期待値に等しく

\frac{n + 1}{2}

になります。失敗時は表の全

n

件と一致しないことを確かめるために

n

回のキー比較が必要です。よって平均比較回数は

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

となり、選択肢エがこれに対応するため正解です。

（注）ここでの「比較回数」は「与えられた従業員番号と表中の各エントリのキーを照合する回数」を指します。

成功時の扱い
- 「表に存在する」場合、目標は位置 1 から n のどこかに一様に現れると仮定する。位置 k にあるとき比較回数は k。
- 位置 k の平均は $\frac{1 + 2 + \dots + n}{n} = \frac{n + 1}{2}$ 。
- 成功確率は $1 - a$ なので成功時の期待値の寄与は $(1 - a) \frac{n + 1}{2}$ 。
失敗時の扱い
- 「表に存在しない」場合は表の先頭から最後まで各キーを比較して全部不一致を確かめる必要がある。比較回数は $n$ 。失敗確率は $a$ なので寄与は $an$ 。
全体の期待値
- 上の2つを足し合わせて $E = (1 - a) \frac{n + 1}{2} + an .$
これが選択肢のエに一致するため正解とする。

ア: $\frac{n + 1}{2} + \frac{na}{2}$
成功時の期待値を $(n + 1) /2$ とした上で、失敗時の寄与を $\frac{na}{2}$ としているが、失敗時の比較回数は $n$ （全件比較）であり $\frac{n}{2}$ ではないため誤りです。代数的に比べるとアは真値より $a /2$ 多く見積もられます。
イ: $\frac{( n + 1 ) ( 1 - a )}{2}$
これは成功時の寄与のみを取り、失敗時（確率 $a$ ）のコストを無視しています。失敗時の比較回数 $n$ を加える必要があります。
ウ: $\frac{( n + 1 ) ( 1 - a )}{2} + \frac{n}{2}$
失敗時コストを平均 $n /2$ と誤っている形です。失敗時は最後まで確認するため比較回数は $n$ であり、ここでも過小評価になっています。
エ: $\frac{( n + 1 ) ( 1 - a )}{2} + na$
成功時・失敗時それぞれ正しい期待値を用いており、正解です。

失敗時の平均比較回数を「表の中央まで調べる平均 $n /2$ 」と誤る。先頭から最後まで順に調べる場合、失敗時は必ず全 $n$ 件と比較するので比較回数は $n$ です。
センチネル（番兵）を使うと比較回数が変わらないと単純に言い切る誤り。センチネルは境界チェック（配列終端判定）を省く実装上の最適化ですが、比較の定義次第では不成功時のキー一致比較回数が $n$ から $n + 1$ になるなど変化する場合があります。ここでは「キーと各エントリを一致判定する比較回数」を比較回数として扱っているので、標準実装では失敗時は $n$ 回です。
探索対象が均一分布でない（位置に偏りがある）場合に上式が成り立たない点を見落とす。位置分布の仮定は期待値計算の前提です。

特殊ケースの確認
- $a = 0$ （必ず表にある）なら $E = \frac{n + 1}{2}$ （成功のみ）。
- $a = 1$ （必ず表にない）なら $E = n$ （失敗のみ）。
計算上の複雑度は期待比較回数のオーダで表すと平均 $O (n)$ （定数係数は上の式で与えられる）。最悪ケース（失敗または最後にある）は $n$ 比較で $O (n)$ 。

Q: センチネルを入れると平均比較回数はどうなる？
A: 実装によって違います。境界チェックが減りループが単純になるため実行時間は改善することが多いですが、「キーとテーブル内エントリの一致を調べる回数」という定義の比較回数は、成功時は同じ $\frac{n + 1}{2}$ 、失敗時は実装次第で $n$ または $n + 1$ など変わることがあります。問題文での比較回数定義を確認してください。
Q: 位置分布が一様でない場合は？
A: 成功時の期待比較回数は位置確率分布の重み付き平均になります。一般には $(1 - a) \sum_{k = 1}^{n} p_{k} k + a \cdot n$ （ $p_{k}$ は位置 k の出現確率）。