algorithm - 恒定时间和有效恒定时间复杂度之间的差异

Question

我理解“恒定时间复杂度 O(1)”，但是当我遇到有效恒定时间复杂度这个术语时，我感到非常困惑。我从 Scala cook book 中得到了关于 effective constant time 的以下句子。

The operation takes effectively constant time, but this might depend on some assumptions, such as maximum length of a vector, or distribution of hash keys.

但我认为上面的例子不是有效的常数时间，而是摊销常数时间。

能否请您明确区分 constant time 和 effective constant time 。这将非常有帮助。谢谢!!

Answer 1

这与引用所说的几乎完全相同:它不是常数时间，但是，在一些合理的假设下，它只比常数时间差一点点，不足以引起注意。

所以，这不是恒定时间，但它非常接近以至于差异无关紧要，这实际上使其(几乎)成为恒定时间，

例如，将数组数据结构实现为 32 向树在技术上使其复杂度为 O(log n) 而不是 O(1)。但是一个有 40 亿个条目的数组只有 6.4 层深，所以它基本上比传统的可变连续数组慢不到 7 倍。