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

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

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

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

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

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

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

或者更严格地说，

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

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

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

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

让我们以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次操作添加一个元素(平摊常数时间)。

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()

这就产生了下面的图