この問題は、利用者からの報告を受けて確認中です。答えや解説に誤りがあるかもしれません。

アルゴリズムと計算量の問題

難易度 3期末試験の応用レベル大学数学アルゴリズムと計算量

番号 $0, 1, 2, 3, 4$ の $5$ 個のスロットからなるハッシュ表が最初は空である。この表に、互いに異なる $3$ 個のキーを $1$ 個ずつ順に、次の線形探査法（オープンアドレス法）で挿入する。

キーのハッシュ値を $h$ とし、スロット $h, h + 1, h + 2, \dots$ の順に（番号は $5$ を法として考え、スロット $4$ の次はスロット $0$ とする）調べ、最初に見つかった空のスロットにそのキーを入れる。
$1$ 個のスロットを調べることを探査 $1$ 回と数える。キーを入れた空のスロットを調べることも $1$ 回に数える（たとえば、スロット $h$ が空ならば探査は $1$ 回）。

各キーのハッシュ値は $0, 1, 2, 3, 4$ のどれかに等確率 $\frac{1}{5}$ で定まり、キーどうしのハッシュ値は互いに独立であるとする。 $3$ 個のキーを挿入し終えるまでの探査回数の合計の期待値を求めよ。

この問題で使うもの

ハッシュの衝突の期待値（説明と入口の問題）
指示変数と期待値の線形性（説明と入口の問題）

この問題を解けるようになるまで（71 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの問題で使う技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

ヒント

行き詰まったら、上から順に 1 つずつ開いてください。

ヒント 1

期待値の線形性を使い、 $1$ 個目・ $2$ 個目・ $3$ 個目のキーの挿入でかかる探査回数の期待値を別々に求めて足そう。

ヒント 2

$3$ 個目のキーの探査回数は、それまでに埋まった $2$ 個のスロットが「隣り合って塊になっているか」「離れているか」で変わる。それぞれの状態になる確率と、その状態での条件付き期待値を求めよう。

ヒント 3

$1$ 個目の期待値は $1$ 、 $2$ 個目は $\frac{6}{5}$ である。 $2$ 個のキーを入れた後、埋まったスロットが隣り合う確率は $\frac{3}{5}$ 、離れる確率は $\frac{2}{5}$ になる。

答えと解説

答えを見る

\frac{93}{25}

結果を記録する（このブラウザにだけ保存されます）:

解説を読む

期待値の線形性により、 $k$ 番目のキーの挿入にかかる探査回数を $X_{k}$ とすると、求める期待値は $E [X_{1}] + E [X_{2}] + E [X_{3}]$ である。

1 個目のキー: 表は空なので必ず $X_{1} = 1$ 。 $E [X_{1}] = 1$ 。

2 個目のキー: 1 個目のキーがスロット $a$ に入っているとする。2 個目のハッシュ値が $a$ のとき（確率 $\frac{1}{5}$ ）はスロット $a$ , $a + 1$ を調べて $X_{2} = 2$ 、それ以外（確率 $\frac{4}{5}$ ）は $X_{2} = 1$ 。
$E [X_{2}] = 2 \cdot \frac{1}{5} + 1 \cdot \frac{4}{5} = \frac{6}{5}$

2 個のキーを入れた後の表の状態: 2 個目のキーが入るスロットは
- ハッシュ値が $a$ のとき $a + 1$ 、ハッシュ値が $a + 1$ のとき $a + 1$ 、ハッシュ値が $a - 1$ のとき $a - 1$
- ハッシュ値が $a + 2$ のとき $a + 2$ 、ハッシュ値が $a - 2$ のとき $a - 2$

である。前の 3 通り（確率 $\frac{3}{5}$ ）では、埋まったスロットが隣り合う $2$ 個の連続した塊になる（状態 P）。後の 2 通り（確率 $\frac{2}{5}$ ）では、埋まったスロットが隣り合わない $2$ 個に分かれる（状態 Q。 $5$ 個のスロットが環状なので、どちら側にも空きスロットが挟まる）。

3 個目のキー:

状態 P で、埋まったスロットを $b, b + 1$ とする（ $b + 2$ は空）。ハッシュ値が $b$ なら $b, b + 1, b + 2$ を調べて $3$ 回、 $b + 1$ なら $2$ 回、残りの $3$ 個の空きスロットならどれも $1$ 回。
$E [X_{3} ∣ P] = \frac{3 + 2 + 1 \cdot 3}{5} = \frac{8}{5}$

状態 Q で、埋まったスロットを $c, d$ とする。どちらの次のスロットも空なので、ハッシュ値が $c$ または $d$ なら $2$ 回、残りの $3$ 個の空きスロットなら $1$ 回。
$E [X_{3} ∣ Q] = \frac{2 + 2 + 1 \cdot 3}{5} = \frac{7}{5}$

よって
$E [X_{3}] = \frac{3}{5} \cdot \frac{8}{5} + \frac{2}{5} \cdot \frac{7}{5} = \frac{24}{25} + \frac{14}{25} = \frac{38}{25}$

合計:
$E [X_{1}] + E [X_{2}] + E [X_{3}] = 1 + \frac{6}{5} + \frac{38}{25} = \frac{25 + 30 + 38}{25} = \frac{93}{25}$

別解

1 個目: 表は空なので探査は必ず 1 回。期待値 $1$ 。

2 個目: 1 個目が入ったスロットを $s$ とする。ハッシュ値 $h \neq = s$ （確率 $\frac{4}{5}$ ）なら探査 1 回、 $h = s$ （確率 $\frac{1}{5}$ ）なら $s$ が埋まっていて次の $s + 1$ が空なので探査 2 回。期待値 $\frac{4}{5} \cdot 1 + \frac{1}{5} \cdot 2 = \frac{6}{5}$ 。

このとき 2 個目の入るスロットは、 $h \neq = s$ なら $h$ 、 $h = s$ なら $s + 1$ 。 $s$ を基準に 2 個のキーが占めるスロットは、 $h = s$ （ $s + 1$ ）、 $h = s + 1$ 、 $h = s - 1$ の各確率 $\frac{1}{5}$ で隣り合い（合計 $\frac{3}{5}$ ）、 $h = s + 2, s + 3$ のとき（合計 $\frac{2}{5}$ ）は隣り合わない（環状に距離 2）。

3 個目:
- 隣り合う場合、占有を ${a, a + 1}$ とする。 $h = a$ なら探査 3 回、 $h = a + 1$ なら 2 回、残り 3 通りは 1 回。合計 $3 + 2 + 3 = 8$ 、期待値 $\frac{8}{5}$ 。
- 隣り合わない場合、占有を ${a, a + 2}$ とする。 $h = a$ なら $a$ が埋まり $a + 1$ が空なので 2 回、 $h = a + 2$ なら $a + 3$ が空なので 2 回、残り 3 通りは 1 回。合計 $2 + 2 + 3 = 7$ 、期待値 $\frac{7}{5}$ 。

3 個目の期待値は $\frac{3}{5} \cdot \frac{8}{5} + \frac{2}{5} \cdot \frac{7}{5} = \frac{24 + 14}{25} = \frac{38}{25}$ 。

期待値の線形性より合計は $1 + \frac{6}{5} + \frac{38}{25} = \frac{25 + 30 + 38}{25} = \frac{93}{25}$ 。

検算: 3 個のハッシュ値の組は全部で $5^{3} = 125$ 通り。2 個目までの場合分けの確率 $\frac{3}{5}, \frac{2}{5}$ は合計 1 で、各場合の 3 個目の探査回数の平均が $\frac{8}{5}, \frac{7}{5}$ であることを上のように確かめたので、全体の期待値は $3.72 = \frac{93}{25}$ 。

アルゴリズムと計算量の問題

この問題で使うもの

ヒント

答えと解説

次のおすすめ

この問題の確認

間違いを報告する

関連する問題