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

标签 c++ hashmap time-complexity hashtable

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

最佳答案

当 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)/nc,因此 T(n) ≤ cn,因此执行 < em>n 操作最多有 cn 成本。因此,n 操作的成本是 O(n),而不仅仅是 O(n) 的摊销。

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

关于c++ - 哈希表的复杂度计算错误?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/69718116/

相关文章:

c++ - 虚拟继承与非默认构造函数

c++ - 尽管链接正确,但未定义的 boost 引用

node.js - 合并两个字典 : perl "hashrefslice" syntax in javascript?

java - HashMap的性能和怪异

java - 如何从 java 中的另一个类调用 hashmap 及其值?

java - 优化 Java 中的递归函数

python - gensim 是如何快速找到最相似的单词的?

C++ 将模板类型名类作为函数参数传递

c++ - 在定义函数时,使用decltype获取函数返回的类型

algorithm - 这个 BFS 算法的时间复杂度是多少?