14

練習のためだけに（宿題としてではなく）、私はこの問題を解決しようとしてきました（CLRS、第3版、演習11.2-6）：

サイズmのハッシュテーブルにn個のキーを格納し、チェーンによって衝突を解決し、最長のチェーンの長さLを含む各チェーンの長さを知っているとします。ハッシュテーブル内のキーの中からランダムに均一にキーを選択し、予想時間O（L *（1 + m / n））で返す手順を説明します。

これまで私が思っていたのは、各キーが返される確率は1/nだということです。1からnまでのランダムな値xを取得しようとし、最初にバケットでソートされ、次にバケット内のチェーンに沿ってx番目のキーを順番に見つけようとすると、O（m）が正しいバケットを見つけるのにかかります。バケットを1つずつ通過し、O（L）時間で、チェーン内の適切なキーを取得します。

4

1 に答える 1

23

要素が返されるまで、次の手順を繰り返します。

  • バケットをランダムに選択します。バケットk内の要素の数とします。
  • pからランダムに均一に選択し1 ... Lます。その後、バケット内のth要素を返しp <= kます。p

プロシージャが要素をランダムに均一に返すことは明らかです。2D配列に配置された要素に棄却サンプリングを適用しているようなものです。

バケットあたりの予想される要素数はですn / m。サンプリングの試行が成功する確率はです(n / m) / L。したがって、バケットを見つけるために必要な予想試行回数はですL * m / n。O(L)バケットから要素を取得するコストと合わせて、予想される実行時間はO(L * (1 + m / n))です。

于 2011-12-25T17:29:44.953 に答える