algorithm - 动态数组的摊销时间

Question

举个简单的例子，在动态数组的具体实现中，每次数组填满时，我们将数组的大小加倍。因此，可能需要重新分配数组，在最坏的情况下，插入可能需要 O(n)。但是，一个序列的 n 次插入总是可以在 O(n) 时间内完成，因为其余的插入是在恒定时间内完成的，因此可以在 O(n) 时间内完成 n 次插入。因此，每次操作的摊销时间为 O(n) / n = O(1)。——来自维基

但是在另一本书中：每次加倍需要 O(n) 时间，但发生如此之少以至于它的摊销时间仍然是 O(1)。

希望有人能告诉我这种罕见的情况是否可以推断出 Wiki 的解释？谢谢

Answer 1

摊销基本上是指每操作次数的平均值。

因此，如果您有一个 n 数组，则需要插入n+1 个项目，直到需要重新分配。

因此，您已经完成了n 个插入，其中每个插入都使用了O(1)，另一个插入使用了O(n)，因此总共有n+1 个操作花费了2n 个操作。

2n / n+1  ~= 1 

这就是为什么摊销时间仍然是O(1)

Answer 2

是的，这两个陈述说的是同一件事，Wiki 只是更彻底地解释了它。