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

Question

我正在阅读: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) 摊销。

Algorithm:

• 1 Initialize an empty hash table s.
• 2 Do following for each element A[i] in A[]
  • 2.1 If s[x – A[i]] is set then print the pair (A[i], x – A[i])
  • 2.2 Insert A[i] into s.

第 1 步在 O(1) 中完成。第 2 步执行 O(n) 次迭代，其中对于每个迭代，我们执行 O(1) 次摊销(2.1 和 2.2)，因此我们总共有 O(n) 次摊销。

Answer 1

当 O(1) 分摊步骤执行 n 次时，不能得出总成本只是 O(n) 分摊的结论。事实上，一个步骤是 O(1) 摊销的，这意味着它的 n 次平均成本至多是某个常数 c，并且它的平均成本至多 c em>c 表示这 n 步的总成本最多为 cn，因此 n 步的成本为 O( n)，而不仅仅是 O(n) 摊销。

通过 the definition of amortized cost with the aggregate method ，一个操作是 T(n)/n 摊销的事实意味着在执行 时有一些上限 T(n) n 操作。所以，如果一个操作是 O(1) 摊销的，这意味着有一些 c 使得平均成本最多为 c，我们有 T(n)/n ≤ c，因此 T(n) ≤ cn，因此执行 < em>n 操作最多有 cn 成本。因此，n 操作的成本是 O(n)，而不仅仅是 O(n) 的摊销。

孤立地考虑操作而不是将其作为 n 操作序列的一部分来考虑可能会造成一些混淆。如果某个程序执行了数十亿次 unordered_set 插入，而我们随机抽取了其中的 n 个样本，则不能保证这些 n 具有 O (1) 摊销时间。我们不太可能获得恰好重建表的许多插入。在这样的随机选择中，统计平均时间为 O(1)，但每个样本都可能波动。相比之下，当我们查看所有插入表中插入 n 个元素时，它们的时间是相关的；该算法的本质是保证表重建只以一定的频率发生，这保证了 n 插入的总工作量是 O(n).