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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

OR

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

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

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

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

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

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

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(感谢拉法沃格德)