1

私は次の質問をします、そしてそれはハッシュを使った解決策を私に叫びます：

問題 ：

数の膨大なリストが与えられた場合、x1........xnここでxi <= T、2つのインデックスが存在するかどうかを知りたいと思います。i,jここで、x_i == x_j。実行時に、また期待値が、問題
のアルゴリズムを見つけます。O(n)O(n)

現時点での私の解決策：ハッシュを使用します。ここでは、を使用したマッピング関数h(x)を使用しchainingます。

Aまず、新しい配列を作成します。これを、各セルがリンクリストであると呼びましょう。これが宛先配列になります。

ここで、ハッシュ関数を使用して、すべてのn数値を実行し、の各要素をx1........xn正しい場所にマップします。これにはO(n)実行時間がかかります。

その後、を実行しA、衝突を探します。に格納されている値にマップされたとlength(A[k]) > 1 を返すセルが見つかった場合、最後に2つの数値（実際に存在する場合）のマップされた値があれば、ここでの合計実行時間は最悪の場合になりますのセル。xixjA[k]O(n)A

4

1 に答える 1

3

同じアプローチは（平均で）約2倍速くなりますが、それでもO(n)平均ですが、定数はより優れています。

すべての要素をハッシュにマップしてからそれを調べる必要はありません-より高速な解決策は次のようになります：

for each element e:
  if e is in the table:
      return e
  else:
    insert e into the table

また、の場合、鳩の巣原理から、最初の要素T < n内に重複が存在する必要があることに注意してください。 また、小さい場合は、サイズTの単純な配列を使用できます。ハッシュは必要ありません。Tの初期化は、初期値としてゼロを含めるために行うことができます。T+1
T(hash(x) = x)O(1)

于 2012-06-20T09:32:38.950 に答える