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

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

キー $x$ を挿入するときは、ハッシュ値 $h(x)\in \{0,1,\dots ,5\}$ から始めて、セル $h(x),h(x)+1,h(x)+2,\dots$（番号は $6$ を法として考え、セル $5$ の次はセル $0$ とする）の順に調べ、最初に見つかった空のセルにキーを格納する。調べたセルの個数（キーを格納した空のセルも $1$ 個と数える）を、その挿入の探査回数とよぶ。

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

互いに異なる $6$ 個の実数を並べた配列 $A[1],A[2],\dots ,A[6]$ から、最大値と最小値の両方を次のアルゴリズムで求める。

• 最初に $mx=A[1]$、$mn=A[1]$ とする。
• $i=2,3,\dots ,6$ の順に、次の操作を行う。
• まず $A[i]$ と $mx$ を比較する。$A[i]>mx$ であれば $mx=A[i]$ とし、この $i$ についての操作を終える。
• そうでなければ、$A[i]$ と $mn$ を比較し、$A[i]<mn$ であれば $mn=A[i]$ とする。

$6$ 個の数の並び方は $6!$ 通りすべてが等確率 $\frac{1}{6!}$ で起こるとする。このアルゴリズムで行われる要素どうしの比較の回数の期待値を求めよ。

番号 $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$ 個のキーを挿入し終えるまでの探査回数の合計の期待値を求めよ。

バケット数 $5$ のチェイン法ハッシュ表が最初は空である。互いに異なるキーを $1$ 個ずつ順に挿入していき、すでに $1$ 個以上のキーが入っているバケットにキーが挿入された時点（最初の衝突が起きた時点）で挿入をやめる。各キーのハッシュ値は $5$ 個のバケットのそれぞれに確率 $\frac{1}{5}$ で、ほかのキーとは独立に定まるものとする。挿入をやめるまでに挿入したキーの個数を $T$ とする（衝突を起こしたキーも数える）。$T$ の期待値 $E[T]$ を求めよ。

バケット数 $4$ のチェイン法ハッシュ表に、互いに異なる $5$ 個のキーを挿入する。各キーのハッシュ値は $4$ 個のバケットのどれかに等確率 $\frac{1}{4}$ で定まり、キーどうしのハッシュ値は互いに独立であるとする。$5$ 個すべてを挿入し終えたとき、キーを $2$ 個以上含むバケットの個数の期待値を求めよ。