持续摊还的时间

Question

在讨论算法的时间复杂度时,"恒定摊还时间"是什么意思？

Answer 1

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

如果您做了一百万次操作,那么您并不真正关心该操作的最坏情况或最佳情况 - 您关心的是当您重复操作一百万次时需要花费多少时间.

因此,如果操作偶尔会非常缓慢并不重要,只要"偶尔"很少见,以便缓慢消除.基本上摊还的时间意味着"如果你做很多操作,每次操作需要的平均时间".摊销时间不必保持不变; 你可以有线性和对数的摊销时间或其他任何东西.

让我们来看一个动态数组的示例,您可以重复添加新项目.通常,添加项目需要恒定的时间(即O(1)).但是每次数组都满了,你会分配两倍的空间,将数据复制到新区域,并释放旧空间.假设分配和释放在恒定时间内运行,这个放大过程需要O(n)时间,其中n是数组的当前大小.

所以每次放大时,你花费的时间是最后一次放大的两倍.但是你在做这件事之前也等了两倍!因此,每次放大的成本可以在插入中"展开".这意味着从长远来看,将m个项目添加到数组所花费的总时间是O(m),因此摊销时间(即每次插入的时间)是O(1).

Answer 2

这意味着随着时间的推移,最坏的情况将默认为O(1)或恒定时间.一个常见的例子是动态数组.如果我们已经为新条目分配了内存,则添加它将是O(1).如果我们没有分配它,我们将通过分配当前数量的两倍来实现.这个特定的插入不是 O(1),而是其他东西.

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

或者更严格地说,

有一个常数c,这样对于 长度为L的每个操作序列(也是以昂贵的操作结尾),时间不大于c*L(感谢RafałFowgird)

Answer 3

要开发一种直观的思考方式,请考虑在动态数组中插入元素(例如std::vector在C++中).让我们绘制一个图表,显示在数组中插入N个元素所需的操作数(Y)的依赖关系:

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

Answer 4

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

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

"动态阵列

动态阵列推送操作的摊销分析

考虑一个动态数组,它随着更多元素的添加而增大,例如Java中的ArrayList.如果我们开始使用大小为4的动态数组,则需要花费一些时间将四个元素推到它上面.然而,将第五个元素推送到该数组会花费更长的时间,因为数组必须创建一个当前大小加倍的新数组(8),将旧元素复制到新数组上,然后添加新元素.接下来的三次推送操作同样会花费一些时间,然后随后的添加将需要另一个缓慢加倍的数组大小.

通常,如果我们考虑将任意数量的n推送到大小为n的数组,我们注意到推送操作需要恒定的时间,除了最后一个需要O(n)时间来执行大小倍增操作.由于总共有n个操作,我们可以取平均值,并发现将元素推送到动态数组上需要:O(n/n)= O(1),恒定时间."

以我作为一个简单故事的理解:

假设你有很多钱.而且,你想把它们堆放在一个房间里.并且,你现在或将来需要很长的手和腿.而且,你必须在一个房间里填充所有,所以很容易锁定它.

所以,你走到房间的尽头,然后开始堆叠它们.当你堆叠它们时,房间会慢慢耗尽空间.但是,当你填充它很容易堆叠它们.得到钱,把钱.简单.这是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都需要O(1)运算.

现在假设,你有N为1,非常小,钱数很少,你有一个非常小的房间,只能适合1个钱.

一旦你在房间里装钱,房间就满了.

当你去更大的房间时,假设它只能再装一个钱,总计2个钱.这意味着,之前的移动资金还有1个.它又被填满了.

通过这种方式,N正在缓慢增长,并且它不再是恒定的O(1),因为我们正在从之前的房间移动所有的钱,但是只能再增加1个钱.

经过100次,新房间可以容纳100个以前的钱和1个可以容纳的钱.这是O(N),因为O(N + 1)是O(N),即100或101的程度是相同的,两者都是数百,而不是之前的故事,数百万和数十亿.

所以,这是为我们的钱(变量)分配房间(或内存/ RAM)的低效方式.

所以,一个好方法是分配更多的空间,权力为2.

第一个房间大小=适合1个金额
第二个房间大小=适合4个金额
第3个房间大小=适合8个金额
第4个房间大小=适合16个金额
第5个房间大小=适合32个金额
第6个房间大小=适合64金钱
第7个房间大小=适合128个金额
8个房间大小=适合256个金额
9个房间大小=适合512个金额
10个房间大小=适合1024个金额
11个房间大小=适合2,048个金额
. ..
16号房间大小=适合65,536金额
...
第32个房间大小=适合4,294,967,296金额
...
第64个房间大小=适合18,446,744,073,709,551,616金额

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

这是有帮助的,因为在第一种情况下虽然很好,但每个货币的总工作量是固定的(2)并且不能与房间大小(N)相比,我们在初始阶段所用的房间也可能是我们可能不会完全使用的大(100万),这取决于我们是否可以在第一种情况下获得那么多钱来节省.

但是,在最后一种情况下,2的幂,它在我们的RAM的限制内增长.因此,增加2的幂,Armotized分析保持不变,并且对于我们今天拥有的有限RAM是友好的.

Answer 5

我创建了这个简单的 python 脚本来演示 python 列表中追加操作的摊销复杂性。我们不断向列表中添加元素并为每个操作计时。在此过程中，我们注意到某些特定的追加操作需要更长的时间。这些峰值是由于执行新的内存分配造成的。需要注意的重要一点是，随着追加操作数量的增加，峰值会变得更高，但间距也会增加。间距的增加是因为每次初始内存溢出时都会保留更大的内存（通常是之前的两倍）。希望这会有所帮助，我可以根据建议进一步改进它。

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

这会产生以下情节