1
arr2がサブセットであるかどうかを確認する。 入力：arr1[] = {11, 1, 13, 21, 3, 7}, arr2[] = {11, 3, 7, 1} 出力：我々は、プロービングリニアを使用している場合arr2[]はarr1[]ハッシュを使用する配列サブセット
のサブセットです。 ハッシュテーブルは次のようになります。 {0=7, 1=1, 2=13, 3=21, 4=3, 5=11}最初の項目はインデックス（ハッシュコード）の2番目の値は です。要素7が表示されている場合は、ハッシュコードは7%6=1です。 1から、すべてのバケットをチェックすることで完全なハッシュテーブルをトラバースする必要があります。ここでは、時間の複雑さはO（n）
です。その後、arr2のすべての要素をハッシュテーブルで検索します。
したがって、全体的な時間の複雑さはLen（arr2）* O（n）になります。
ハッシングの利点は何ですか？
どのように全体の複雑さをO（1）と言うことができますか。 Len（arr2）はNになります。完全な配列をたどる必要があります。 –
私はあなたが言及したものを知っています。しかし、この場合は乾いた状態にしてください。 完全ハッシュテーブルをトラバースして0に戻らなければなりません。したがって、O（n）は複雑さです。 したがって、全体の複雑さはO（M * N） –
です.On、Len（1）をm、Len（2）をmとして表現することができます。 O（mn）になりますが、償却後の複雑さはO（mn）より小さくなります。その場合、ハッシュテーブルを使用しない場合は、O（mn） –