为什么在链式哈希表中成功搜索的时间复杂度平均为 ?(1+​​(n/m))？

Question

我明白为什么在链式哈希表中搜索不成功的时间复杂度平均为 ?(1+​​(n/m))，因为在不成功搜索中检查的元素的预期数量是 (n/m)，并且总数所需时间（包括计算hashFunction(key)的时间）为?(1+(n/m))。但是为什么搜索成功的结果是一样的呢？

Answer 1

根据 Cormen 等人的“算法：设计和分析”。在具有单独链接冲突解决方案的哈希表中成功搜索期间的预期键比较次数为 1 + ?/2 - ?/2n [其中 ?=n/m]。直观的解释：由于这是一次成功的搜索，我们至少检查一个键（我们搜索它），以及链中其余键的一半。

时间复杂度：?(1 + 1 + ?/2 - ?/2n) = ?(1 + ?)，根据 big-theta 符号的定义。