动态数组的摊销时间

Question

举一个简单的例子,在动态数组的特定实现中,每次填充时我们将数组的大小加倍.因此,可能需要重新分配阵列,并且在最坏的情况下,插入可能需要O(n).但是,n次插入的序列总是可以在O(n)时间内完成,因为其余的插入是在恒定时间内完成的,因此n次插入可以在O(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

是的，这两个说法说的是同一件事，维基只是解释得更彻底。