I created this simple python script to demonstrate the amortized complexity of append operation in a python list. We keep adding elements to the list and time every operation. During this process, we notice that some specific append operations take much longer time. These spikes are due to the new memory allocation being performed. The important point to note is that as the number of append operations increases, the spikes become higher but increase in spacing. The increase in spacing is because a larger memory (usually double the previous) is reserved every time the initial memory hits an overflow. Hope this helps, I can improve it further based on suggestions.

import matplotlib.pyplot as plt
import time


a = []
N = 1000000

totalTimeList = [0]*N
timeForThisIterationList = [0]*N
for i in range(1, N):
    startTime = time.time()
    a.append([0]*500) # every iteartion, we append a value(which is a list so that it takes more time)
    timeForThisIterationList[i] = time.time() - startTime
    totalTimeList[i] = totalTimeList[i-1] + timeForThisIterationList[i]
max_1 = max(totalTimeList)
max_2 = max(timeForThisIterationList)

plt.plot(totalTimeList, label='cumulative time')
plt.plot(timeForThisIterationList, label='time taken per append')
plt.legend()
plt.title('List-append time per operation showing amortised linear complexity')
plt.show()

这就产生了下面的图

任何函数的性能都可以通过将“函数调用的总数”除以“所有这些调用所花费的总时间”来求平均。即使函数每次调用的时间越来越长，也可以用这种方法求平均。

因此，在常数平摊时间执行的函数的本质是，这个“平均时间”达到一个上限，随着调用数量的继续增加，这个上限不会被超过。任何特定的调用可能在性能上有所不同，但从长期来看，这个平均时间不会变得越来越大。

这是在常数平摊时间下执行的东西的基本优点。

在重复阅读3次后，我发现维基百科下面的解释很有用:

来源:https://en.wikipedia.org/wiki/Amortized_analysis Dynamic_Array

"Dynamic Array Amortized Analysis of the Push operation for a Dynamic Array Consider a dynamic array that grows in size as more elements are added to it such as an ArrayList in Java. If we started out with a dynamic array of size 4, it would take constant time to push four elements onto it. Yet pushing a fifth element onto that array would take longer as the array would have to create a new array of double the current size (8), copy the old elements onto the new array, and then add the new element. The next three push operations would similarly take constant time, and then the subsequent addition would require another slow doubling of the array size. In general if we consider an arbitrary number of pushes n to an array of size n, we notice that push operations take constant time except for the last one which takes O(n) time to perform the size doubling operation. Since there were n operations total we can take the average of this and find that for pushing elements onto the dynamic array takes: O(n/n)=O(1), constant time."

在我看来，这是一个简单的故事:

假设你有很多钱。 你想把它们堆在一个房间里。 而且，你有长长的手和腿，只要你现在或将来需要。 而且，你必须把所有东西都放在一个房间里，所以很容易锁上。

所以，你径直走到房间的尽头/角落，开始堆叠它们。 当你把它们堆起来的时候，慢慢地房间就会没有空间了。 然而，当你填满的时候，很容易把它们堆叠起来。拿到钱，把钱放进去。一件容易的事。这是O(1)。我们不需要转移以前的钱。

一旦房间没有空间了。 我们需要另一间更大的房间。 这里有一个问题，因为我们只有一个房间所以我们只有一把锁，我们需要把那个房间里所有现有的钱转移到新的更大的房间里。 所以，把所有的钱从小房间搬到大房间。也就是说，把它们全部叠起来。 所以，我们确实需要转移所有以前的钱。 所以是O(N)(假设N为之前货币的货币总数)

换句话说，直到N，只有1个操作，但是当我们需要移动到一个更大的房间时，我们做了N个操作。换句话说，如果我们求平均值，开始时是1个插入，移动到另一个房间时是1个移动。 总共2个操作，一个插入，一个移动。

假设N很大，即使在小房间里也是100万，与N(100万)相比，2个操作并不是一个真正可比较的数字，因此它被认为是常数或O(1)。

假设当我们在另一个更大的房间里做以上所有事情时，又需要搬家。 它还是一样的。 假设N2(10亿)是大房间里的新数目

所以我们有N2(包括之前的N个因为我们都是从小房间移动到大房间)

我们仍然只需要2个操作，一个是插入到更大的房间，然后另一个移动操作移动到更大的房间。

所以，即使对于N2(10亿)，每个都需要2次操作。这又不算什么。所以它是常数，或者O(1)

所以，当N从N增加到N2，或者其他，这无关紧要。它仍然是常数，或者说每个N。

现在假设，你有N = 1，非常小，钱的数量很少，你有一个非常小的房间，只能装下1笔钱。

只要你把钱放在房间里，房间就被填满了。

当你去更大的房间时，假设它只能装下一笔钱，总共两笔钱。这意味着，前面移动的钱和1。它又被填满了。

这样，N增长缓慢，它不再是常数O(1)，因为我们从前一个房间移动了所有的钱，但只能多装1个钱。

100次后，新房间适合100计数的钱从以前和1更多的钱，它可以容纳。这是O(N)因为O(N+1)等于O(N)也就是说，100度和101度是一样的，都是几百度，而不是之前的，1比百万，1比十亿。

因此，这是为我们的钱(变量)分配空间(或内存/ RAM)的低效方式。

所以，一个好办法是分配更多的空间，用2的幂。

1st room size = fits 1 count of money 2nd room size = fits 4 count of money 3rd room size = fits 8 count of money 4th room size = fits 16 count of money 5th room size = fits 32 count of money 6th room size = fits 64 count of money 7th room size = fits 128 count of money 8th room size = fits 256 count of money 9th room size = fits 512 count of money 10th room size= fits 1024 count of money 11th room size= fits 2,048 count of money ... 16th room size= fits 65,536 count of money ... 32th room size= fits 4,294,967,296 count of money ... 64th room size= fits 18,446,744,073,709,551,616 count of money

为什么这样更好呢?因为它看起来在开始时增长缓慢，之后增长更快，也就是说，与RAM中的内存数量相比。

这是有帮助的，因为在第一种情况下，虽然它是好的，但每一笔钱要完成的工作总量是固定的(2)，而不是与房间大小(N)相比，我们在初始阶段占用的房间可能太大了(100万)，我们可能无法完全使用，这取决于我们是否可以在第一种情况下节省那么多钱。

然而，在最后一种情况下，2的幂，它在RAM的极限内增长。因此，增加到2的幂，armoized分析都保持不变，而且它对目前有限的RAM很友好。

用简单的术语解释摊销时间:

如果你做一个操作一百万次，你不会真正关心这个操作的最差情况或最好情况你关心的是当你重复这个操作一百万次时总共花费了多少时间。

因此，如果操作偶尔非常缓慢，这并不重要，只要“偶尔”足够罕见，可以稀释掉这种缓慢。本质上，摊销时间指的是“如果你做了很多操作，每次操作所花费的平均时间”。摊销时间不一定是常数;你可以有线性和对数平摊时间或者其他的。

让我们以mats的动态数组为例，您可以反复向其中添加新项。通常，添加一项需要常数时间(即O(1))。但是每当数组满时，分配两倍的空间，将数据复制到新区域，并释放旧空间。假设分配和释放操作在常数时间内运行，这个扩大过程需要O(n)时间，其中n是数组的当前大小。

所以每次放大的时间是上次放大的两倍。但你也等了两倍的时间才这么做!因此，每次扩大的成本可以在插入之间“分摊”。这意味着从长远来看，向数组中添加m个元素所花费的总时间是O(m)，因此摊销时间(即每次插入的时间)是O(1)。

为了开发一种直观的思考方法，可以考虑在动态数组中插入元素(例如c++中的std::vector)。让我们画一个图，它显示了在数组中插入N个元素所需的操作数量(Y)的依赖性:

黑色图的垂直部分对应于为了扩展数组而重新分配内存。在这里，我们可以看到这种依赖关系可以粗略地表示为一条线。直线方程是Y=C*N + b (C是常数，这里b = 0)因此，我们可以说，我们平均需要花费C*N次操作向数组添加N个元素，或者C*1次操作添加一个元素(平摊常数时间)。

这意味着随着时间的推移，最坏的情况将默认为O(1)，即常数时间。一个常见的例子是动态数组。如果我们已经为一个新条目分配了内存，添加它将是O(1)。如果我们没有分配它，我们会分配，比如说，当前数量的两倍。这个特殊的插入不是O(1)，而是其他的东西。

重要的是，该算法保证在一系列操作之后，昂贵的操作将被摊销，从而将整个操作呈现为O(1)。

或者更严格地说，

有一个常数c，使得 的每一个操作序列(也是一个以代价高昂的操作结束的序列) 长度L，时间不大于 c*L(感谢拉法沃格德)