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/
我认为计算 Method2(散列)的时间复杂度是错误的,他们声称它是 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 的事实意味着这 n 步的总成本至多是 cn,所以n 步的成本是 O(n),而不仅仅是 O(n) 摊销。
来自 the definition of amortized cost with the aggregate method ,一个操作是 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)。

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

相关文章:

algorithm - 给出了三种算法的时间复杂度。对于较大的N值,哪一个执行最慢?

c++ - 使用 Google 测试框架(不是 Windows)进行内存泄漏检测的标准做法是什么

c++ - 如何评估 'if (A && B)' 语句?

java - 这个 HashMap 怎么了,我不断得到不兼容的类型

java - 抓取键为特定值的对象

python - HashMap 在 Python 字典中传递引用

c++ - 如何在配置文件中隐藏数据库密码

c++ - 使用派生类创建基类对象

big-o - alpha(n) 的大 O 时间复杂度

algorithm - 以下表达式的时间复杂度是多少?