哈希表的复杂度计算错误？

Question

哈希表的复杂度计算错误？

c++hashmaptime-complexityhashtable

3

我正在阅读：https://www.geeksforgeeks.org/given-an-array-a-and-a-number-x-check-for-pair-in-a-with-sum-as-x/。

我认为在方法2（哈希）的时间复杂度计算中存在错误，他们声称它的时间复杂度是O(n)，但我坚持认为它是O(n)摊销。

算法如下：

1. 初始化一个空哈希表s。 2. 对于A[]中的每个元素A[i]执行以下操作： 2.1 如果s[x-A[i]]已经设置，则打印出对(A[i], x-A[i]) 2.2 将A[i]插入哈希表s中。

步骤1需要O(1)时间。步骤2需要O(n)次迭代，对于每一次迭代我们都需要O(1)（2.1和2.2）的摊销时间，因此总的时间复杂度为O(n)摊销。

- Daniel

2

不一定。两者都可以是假的。 - user4581301

1

这个回答是否解决了你的问题？特别是对于O(1)摊销成本的定义，“存在一个常数c，对于每个长度为L的操作序列（也包括以代价高昂的操作结尾的操作），时间不会超过c*L”？当您总计所有的摊销成本时，结果就变成了总成本的真实上限。 - kcsquared

有关算法性能，迭代次数在现代计算机上是一个非常糟糕的度量标准，这个重要的指标是比较次数。 - Lundin

@Lundin 是的，我想要正式的答案。 - Daniel

1

@Daniel：“这是两件不同的事情...只有一个可以是真的。”：O(n)意味着O(n)摊销。如果某个操作X的每个实例最多需要cn步（即O(n)），那么n个操作X的平均值最多需要cn步（因此X是O(n)摊销）。它们是不同的东西，但O(n)操作集是O(n)摊销操作集的子集。 - Eric Postpischil

显示剩余9条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Eric Postpischil · Accepted Answer

当执行O(1)摊销步骤n次时，不能得出总成本仅为O(n)摊销的结论。事实上，一个步骤是O(1)摊销意味着它在n次中的平均成本最多为某个常数c，而其平均成本最多为c的事实意味着这些n步骤的总成本最多为cn，因此n步骤的成本为O(n)，而不仅仅是O(n)摊销。

根据使用总量法的摊销成本定义，一个操作是T(n)/n 摊销的意思是在执行n次操作上有一个上限 T(n)。因此，如果一个操作是O(1)摊销的，意味着有一些c使得平均成本最多为c，我们有 T(n)/n ≤ c，因此 T(n) ≤ cn，执行n次操作的成本最多为cn。因此，n次操作的成本是O(n)，不仅仅是O(n)摊销。

考虑单独操作而非作为一系列n个操作的一部分时，可能会产生某些混淆。如果某个程序执行数十亿次unordered_set插入操作，并且我们随机取样n个操作，则不能保证这n个操作具有O(1)的平摊时间。我们可能没有运气得到许多重建表的插入操作。在这种随机选择中，统计平均时间将是O(1)，但每个样本都可能波动。相比之下，当我们查看插入n个元素到表中的所有插入操作时，它们的时间是相关的；算法的性质保证了表重建仅以一定频率发生，从而保证了n个插入操作中要完成的总工作量为O(n)。