我正在尝试和朋友一起做作业，一个问题询问线性探测方法的搜索、添加和删除的平均运行时间。我认为它是 O(n)，因为它必须检查一定数量的节点，直到找到要添加的开放节点。并且在搜索时，它从原始索引开始并向上移动，直到找到所需的数字。但我的朋友说它是 O(1)。哪一个是对的？
问问题
20558 次
1 回答
12
当我们谈论渐近复杂性时，我们通常会考虑非常大的 n。现在对于哈希表中的冲突处理，一些方法是链式哈希和线性探测。在这两种情况下，可能会发生两件事（这将有助于回答您的问题）： 1. 由于哈希表已满，您可能需要调整其大小 2. 可能会发生冲突。
在最坏的情况下，这将取决于您如何实现哈希表，例如在线性探测中您找不到数字，您继续移动并且您正在寻找的数字在最后。这是 O(n) 最坏情况的运行时间。谈到链式散列技术，当发生冲突时，要处理它们说我们已经将键存储在平衡二叉树中，因此最坏情况下的运行时间将是 O(log n)。
现在来到最佳情况运行时间，我认为没有混淆，在任何一种情况下都是 O(1)。
O(n) 会在最坏的情况下发生，而不是在设计良好的哈希表的平均情况下发生。如果在平均情况下开始发生这种情况，哈希表将不会在数据结构中找到位置，因为平均而言，平衡树将始终为您提供 O(log n) 并且在此之上也将保留顺序。
很抱歉这么说，但不幸的是你的朋友是对的。您的情况会在最坏的情况下发生。
还可以在这里查看更多信息，即摊销运行时间：哈希表的时间复杂度
于 2012-04-09T11:34:37.457 回答