こんにちは私はCLRSのユニバーサルハッシュに関する章を読んでいます。
234ページ
系11.4
ユニバーサルハッシュとmスロットのテーブルをチェーンすることによる衝突解決を使用すると、O（m）INSERT操作を含むn個のINSERT、SEARCH、およびDELETE操作のシーケンスを処理するのにTheta（n）に予想時間がかかります。
ちょっとわかりましたが、この英語の文章を理解するのに苦労しています。「O（m）INSERT操作を含む」という終わりはどういう意味ですか？
n = O（m）の挿入がすでに実行されているという意味ですか。じゃあ……わかりません。この文を解析できません。1番目のINSERTと2番目のINSERTの違いは何ですか？
ご意見をお聞かせください。
ありがとう！
n個の挿入、検索、削除操作のシーケンスは1つだけだと思いますが、パラメーターmは、これらのn個の操作内に入れることができる挿入操作の数を制限するために使用されます。サイズ10、つまりm = 10のテーブルがあり、最初の500000回の操作でn=1 000 000を設定し、次の500000がテーブルにないアイテムを検索するとします。その場合、テーブルには約100 000アイテムのチェーンが含まれるため、パフォーマンスは非常に低くなります。
したがって、m個のスロットを持つテーブルがある場合、定理では約m個の挿入操作しか許可されないため、テーブルに約m個を超えるアイテムが保持されることはなく、チェーンが長くなりすぎず、すべての操作がほぼOになります。 （1）-上記の例では、挿入操作は約10回しかないため、他の999990操作は検索または削除のいずれかである必要があります。
"O(m)" という INSERTC*m+B操作は、シーケンスに INSERT 操作があることを意味します。ここで、m はスロットの数です。
m 個のスロットを持つテーブルに対して一連の n 個の操作があります。INSERT 操作の数は、(シーケンスの長さに関係なく) スロットの数に比例し、操作の数には比例しません。
つまり、予想される時間は、挿入数が n の関数 (たとえば、シーケンス内の操作の半分が挿入) ではなく、スロット数の線形関数である場合にのみ、theta(n) になります。シーケンスの長さとともに成長しません。