我明白为什么在链式哈希表中不成功的搜索平均具有 Θ(1+(n/m)) 的时间复杂度，因为在不成功的搜索中检查的元素的预期数量是 (n/m)，并且总所需时间（包括计算 hashFunction(key) 的时间）为 Θ(1+(n/m))。但是为什么成功的搜索是一样的呢？
问问题
6264 次
4 回答
7
根据 Cormen 等人的“算法：设计与分析”。在具有单独链接冲突解决方案的哈希表中成功搜索期间的预期键比较数为 1 + α/2 - α/2n [其中 α=n/m]。直观的解释：由于这是一次成功的搜索，我们检查至少一个键（我们搜索它），以及链中其余键的一半。
时间复杂度：Θ(1 + 1 + α/2 - α/2n) = Θ(1 + α)，根据大θ符号的定义。
于 2014-09-17T02:52:39.540 回答
2
绝对条件下成功和不成功搜索的总时间是不相等的。只有当我们谈论渐近符号时它们才相等。
成功搜索的总时间将等于 1 + 所需键之前链表中的元素数。然后这个问题归结为找到在链表中添加特定键后将添加的元素的平均数量。
假设要搜索密钥 k1。最初在准备表格时，在 T[h(k1)] 的开头添加了 k1。设键为 k1 的元素相加后的元素个数为 x。因此，我们仍然有 (nx ) 元素要添加到表中。
由于这个 x 值可能是 1 到 n（因为键 k1 将始终在表中），所以我们将 (nx) 从 1 加到 n 并乘以进入添加键 k1 的同一索引的概率。P(h(任意键) = 1/m
因此平均值为：1 + {(1/n) (Summation (1/m)(nx))}
x 的下限和上限分别为 1 和 n。结果是 Theta(1 + n/m)。
于 2018-10-20T01:58:11.137 回答
2
成功搜索
注释： α= n/m = 负载系数
A) 数学证明
1）假设在链表末尾插入了一个新元素
2)插入第i个元素后，列表的预期长度为(i-1)/m
3）在成功搜索的情况下，预期检查的元素数量比插入寻找的元素时检查的元素数量多1！
因此，所检查的预期元素数量为
现在添加“1”来表示计算哈希函数的时间
我们得到，
B）直觉 对于成功的搜索，您将计算散列函数 O(1) 并平均遍历链中一半的键
于 2015-10-23T15:34:18.797 回答
0
在链式中成功搜索的时间复杂度为 O(1 + n/m) 而不是 Θ(1+(n/m)，因为如果你找到了你的元素，你就可以停下来。无需查看其余元素。
于 2014-09-16T11:09:48.093 回答