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

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

或者更严格地说，

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

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

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

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

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

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

或者更严格地说，

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

为了开发一种直观的思考方法，可以考虑在动态数组中插入元素(例如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()

这就产生了下面的图

平摊运行时间: 这是指根据每个操作使用的时间或内存来计算算法复杂度。 在大多数情况下，它的运算速度很快，但在某些情况下，算法的运算速度很慢。 因此，研究了操作序列，以了解更多的平摊时间。