我正在和朋友一起做作业，其中一个问题要求计算线性探测法的搜索、添加和删除的平均运行时间。我认为它是O(n)，因为它必须在一定数量的节点上检查，直到找到一个可添加的空节点。而在搜索时，它从原始索引开始向上移动，直到找到所需的数字为止。但我的朋友说它是O(1)。哪一个是正确的呢？
哈希碰撞线性探测运行时间
12
- Richard
1
2我想补充一下Yavar的答案：请记住，O（1）不是一个操作。它可能是一个大常数，但如果它不是从像n这样的变量派生出来的话，那就没关系了。即使你需要遍历20个节点才能放置哈希，它仍然是O（1）。当然，这仅适用于哈希表，前提是某些条件为真，但对于设计良好的哈希表，在平均情况下是O（1）。 - Archeg
1个回答
15
当我们谈论渐进复杂度时，通常考虑的是非常大的n。现在对于哈希表中的冲突处理，一些方法是链式哈希和线性探测。在这两种情况下，可能会发生以下两件事（这将有助于回答您的问题）：1.由于哈希表变满，您可能需要调整哈希表的大小。2.可能发生冲突。
在最坏的情况下，这将取决于您如何实现哈希表，在线性探测中如果你找不到数字，你会继续移动，而你正在寻找的数字在最后面。这就是O(n)最坏情况运行时间。至于链式哈希技术，在发生冲突时，为了处理它们，假设我们将键存储在平衡二叉树中，那么最坏情况的运行时间将是O(log n)。
现在来看最好情况的运行时间，我认为没有混淆，在任一情况下都是O(1)。
O(n)只会发生在最坏情况下，而不是好设计的哈希表的平均情况下。如果这在平均情况下开始发生，哈希表将无法在数据结构中找到位置，因为平衡树在平均情况下总是给出O(log n)，并且还将保留顺序。
很抱歉说这句话，但不幸的是，您的朋友是正确的。您的情况将发生在最坏情况下。
此外，请查看这里以获取更多信息，即摊销运行时间：哈希表的时间复杂度。
在最坏的情况下，这将取决于您如何实现哈希表，在线性探测中如果你找不到数字，你会继续移动，而你正在寻找的数字在最后面。这就是O(n)最坏情况运行时间。至于链式哈希技术，在发生冲突时，为了处理它们，假设我们将键存储在平衡二叉树中，那么最坏情况的运行时间将是O(log n)。
现在来看最好情况的运行时间，我认为没有混淆，在任一情况下都是O(1)。
O(n)只会发生在最坏情况下，而不是好设计的哈希表的平均情况下。如果这在平均情况下开始发生，哈希表将无法在数据结构中找到位置，因为平衡树在平均情况下总是给出O(log n)，并且还将保留顺序。
很抱歉说这句话，但不幸的是，您的朋友是正确的。您的情况将发生在最坏情况下。
此外，请查看这里以获取更多信息，即摊销运行时间：哈希表的时间复杂度。
- Yavar
1
1谢谢@DanAllen，你上面的评论真的很鼓舞人心 :) - Yavar
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接