performance - 有人可以澄清摊销常数时间(加倍数组向量)吗？

Question

我想我理解了这个概念。让我根据它在 doubling array vectors 中的应用来解释我是如何理解它的。

The rate of copying items to an array remains constant. While the growth of the array is exponential, the rate at which the array needs to double in size is logarithmic. Because of this, the decreased occurrence of doubling the array size 'sort of' cancels out the resources required to double the array and copy it's elements, as this only happens O(n Log N) times throughout the life of the array. Thus, the O(n^2) for the rate of growth combined with O(n Log N) for the frequency at which the array grows resolves to somewhere around O(n).

这是正确的吗？如果不是，那是哪些部分出错了？我无法解决这个问题。我很确定我给出的 Big Oh 符号不正确。

谢谢

Answer 1

假设当数组达到 2 个元素时，您将数组加倍，4、8、16、32, ..., 2^k.

这意味着对大小为 n 的数组进行 O(log n) 加倍操作。很容易说这使得事情成为 O(n log n)，但事实并非如此。

为所有这些加倍操作执行的操作数受以下限制:

1 + 2 + 4 + ... + 2^k = (2^k - 1) (sum of geometric series)

但是请注意，k = 倍增操作数 = O(log n)，因此我们将倍增所需的操作数限制为 2^(log n) = n

因此，整个事情仍然是 O(n):当您在将数组加倍时执行大量操作时，请考虑与整个数组大小相关的“大量操作”以及如何执行了很多次后，它们不再是“很多”，只是 O(n)。

摊销基本上意味着您要牢记大局:当然，我今天可能需要工作很多，但这意味着我可以在本周剩下的时间里呆在家里。这是否意味着我这周会工作很多？不，我实际上工作得很少。

我认为您的解释并不完全准确且过于复杂。没有任何类型，也没有 O(n^2) 增长率。如您所见，数学加起来就是 O(n)。

总的来说，我的建议是忽略摊销这个词，只做数学运算。我已经看到它无缘无故地引起了很多困惑。当然，这可能是此类分析中涉及的正式内容，但大多数时候它只会引发对所发生情况的困惑。只要问问自己:“好吧，这个算法会执行多少操作？”。通常情况下，您不需要任何花哨的东西来回答这个问题。