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

这就产生了下面的图

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

这就产生了下面的图

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

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

或者更严格地说，

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

上述解释适用于聚合分析，即对多个操作取“平均值”的思想。 我不确定它们如何适用于银行家方法或物理学家的平摊分析方法。

现在。我不能肯定正确答案。 但这与物理学家+班克方法的主要条件有关:

(摊销成本之和)>=(实际操作成本之和)。

我面临的主要困难是，鉴于操作的摊销渐近代价不同于正常的渐近代价，我不确定如何评价摊销代价的重要性。

当有人给我一个平摊代价时，我知道它和正态渐近代价不一样，那么我能从平摊代价中得出什么结论呢?

由于我们有一些业务收费过高而其他业务收费过低的情况，一种假设可能是，引用个别业务的摊销成本将是毫无意义的。

例如:对于一个fibonacci堆，仅仅引用reduce - key为O(1)的平摊代价是没有意义的，因为代价是通过“早期操作在增加堆势中所做的功”来减少的。

OR

我们可以用另一个假设来解释摊销代价:

我知道昂贵的操作之前会有多个低成本的操作。 为了分析起见，我将对一些低成本操作收取过高的费用，这样它们的渐近代价就不会改变。 通过这些增加的低成本操作，我可以证明昂贵的操作具有更小的渐近代价。 因此，我改进/减小了n次操作代价的渐近界。

因此，摊销成本分析+摊销成本边界现在只适用于昂贵的操作。廉价操作的渐近平摊代价与正常渐近代价相同。

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

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

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

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