我明白为什么在链式哈希表中不成功的搜索平均时间复杂度为 Θ(1+(n/m))，因为在不成功的搜索中检查的元素的预期数量是 (n/m)，总共需要的时间(包括计算 hashFunction(key) 的时间)为 Θ(1+(n/m))。但为什么搜索成功都一样呢？
最佳答案
根据 Cormen 等人的“算法:设计与分析”。在具有单独的链接冲突解决方案的哈希表中成功搜索期间，预期的键比较次数为 1 + α/2 - α/2n [其中 α=n/m]。直观的解释:由于这是一次成功的搜索，我们至少检查一个键(我们搜索它)，以及链中其余键的一半。
时间复杂度:根据 big-theta 符号的定义，Θ(1 + 1 + α/2 - α/2n) = Θ(1 + α)。
关于algorithm - 为什么在链式哈希表中成功搜索的平均时间复杂度为 Θ(1+(n/m))？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/25866380/