作为一个简单的例子，在动态阵列的具体实施中，我们加倍每填补了时间的阵列的大小。 正因为如此，阵列重新分配可能需要，并且在最坏情况下的插入可能需要为O（n）。 然而，正插入的顺序总是可以在O（n）的时间内完成，因为插入的其余部分在固定时间内完成，因此n的插入可以在O（n）的时间内完成。 因此，每次操作的分期时间为O（n）/ N = O（1）。 --from维基

As a simple example, in a specific implementation of the dynamic array, we double the size of the array each time it fills up. Because of this, array reallocation may be required, and in the worst case an insertion may require O(n). However, a sequence of n insertions can always be done in O(n) time, because the rest of the insertions are done in constant time, so n insertions can be completed in O(n) time. The amortized time per operation is therefore O(n) / n = O(1). --from Wiki

但在另一本书：每增加一倍，需要O（n）的时间，可是偏偏所以很少，它的分期时间仍然是O（1）

But in another book :Each doubling takes O(n) time, but happens so rarely that its amortized time is still O(1).

希望有人能告诉我它在罕见的情况推断百科的解释？谢谢

Hope somebody could tell me does the rare situation infer the Wiki explanation? Thanks

推荐答案

摊销主要是指业务的人均数量。

Amortized basically means average per number of operations.

所以，如果您有n个数组，你需要插入的 N + 1项，直到你需要重新分配。

So, if you have an array of n, you need to insert n+1 items until you'll need the reallocation.

所以，你做的 n次插入这其中的每个人把 O（1），然后插入另一是把 O（N），所以在总你有 N + 1操作，成本您 2N操作

So, you've done n inserts which each one of them took O(1), and another insert that took O(n), so in total you've got n+1 actions that cost you 2n operations .

2n / n+1  ~= 1 

这就是为什么分期时间仍然 O（1）

That's why the Amortized time is still O(1)