什么是常数平摊时间?

当讨论算法的时间复杂度时，“常数平摊时间”是什么意思?

115816 次浏览
小开

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

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

或者更严格地说，

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

小开
最佳答案

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

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

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

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

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

小开
以上解释适用于聚合分析，即对多个操作取“平均值”的思想。 我不确定它们如何适用于班克斯方法或物理学家的平摊分析方法 < p >。我不能肯定正确答案。 但这与物理学家+银行家方法的基本条件有关:

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

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

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

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

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

或

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

  1. 我知道昂贵的操作之前会有多个低成本的操作。

  2. 为了分析起见，我将对一些低成本操作收取过高的费用，这样它们的渐近代价就不会改变。

  3. 通过这些增加的低成本操作，我可以证明昂贵的操作具有更小的渐近代价。

  4. 因此，我改进/减小了n次操作代价的渐近界。

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

小开

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

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

“动态数组

动态数组推操作的平摊分析

考虑一个动态数组，它的大小随着添加元素的增加而增加 比如Java中的数组列表。如果我们从一个动态数组开始 大小为4，将4个元素推入它需要常数时间。 然而，将第五个元素推入该数组将花费更长的时间 数组必须创建一个新数组，其大小是当前数组(8)的两倍， 将旧元素复制到新数组中，然后添加新元素 元素。接下来的三个推操作同样采用常数 时间，然后后续的添加会需要另一个缓慢 数组大小加倍

一般来说，如果我们考虑任意数量的push n到一个数组 大小为n，我们注意到push操作花费常数时间，除了 对于最后一个，它需要O(n)时间来执行大小加倍 操作。因为总共有n个操作，我们可以取平均值 将元素推入动态数组 花费:O(n/n)=O(1)，常数时间。" < / p >

在我看来，这是一个简单的故事:

假设你有很多钱。 你想把它们堆在一个房间里。 而且，你有长长的手和腿，只要你现在或将来需要。 而且，你必须把所有的东西都放在一个房间里，所以很容易锁上 所以，你径直走到房间的尽头/角落，开始堆叠它们。 当你把它们堆起来的时候，慢慢地房间就会没有空间了。 然而，当你填满的时候，很容易把它们堆叠起来。拿到钱，把钱放进去。一件容易的事。这是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。

现在假设，你有N = 1，非常小，钱的数量很少，你有一个非常小的房间，只能装下1笔钱。

只要你把钱放在房间里，房间就被填满了。

当你去更大的房间时，假设它只能装下一笔钱，总共两笔钱。这意味着，前面移动的钱和1。它又被填满了。

这样，N增长缓慢，它不再是常数O(1)，因为我们从前一个房间移动了所有的钱，但只能多装1个钱。

100次后，新房间适合100计数的钱从以前和1更多的钱，它可以容纳。这是O(N)因为O(N+1)等于O(N)也就是说，100度和101度是一样的，都是几百度，而不是之前的，1比百万，1比十亿。

因此，这是为我们的钱(变量)分配空间(或内存/ RAM)的低效方式。

所以，一个好办法是分配更多的空间，用2的幂。

第一个房间的大小=适合1笔钱
第二个房间大小=适合4个数目的钱
第三个房间大小=适合8个数目的钱
第四个房间的大小=适合16个数目的钱
第5个房间大小=适合32个数目的钱
第6个房间大小=适合64个数目的钱
第7个房间大小=适合128个钱
第8个房间大小=适合256个钱
第9个房间大小=适合512计数的钱
第10个房间大小=适合1024个数目的钱
第11个房间大小=适合2048个数目的钱
< br >… 第16个房间大小=适合65,536计数的钱
< br >… 第32个房间大小=适合4,294,967,296计数的钱
< br >… 第64个房间大小=适合18,446,744,073,709,551,616计数的钱

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

这是有帮助的，因为在第一种情况下，虽然它是好的，但每一笔钱要完成的工作总量是固定的(2)，而不是与房间大小(N)相比，我们在初始阶段占用的房间可能太大了(100万)，我们可能无法完全使用，这取决于我们是否可以在第一种情况下节省那么多钱。

然而，在最后一种情况下，2的幂，它在RAM的极限内增长。因此，增加到2的幂，armoized分析都保持不变，而且它对目前有限的RAM很友好。

小开

为了建立一种直观的思考方式，考虑在动态数组中插入元素(例如c++中的std::vector)。让我们画一个图，它显示了在数组中插入N个元素所需的操作数量(Y)的依赖性:

plot

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

小开

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

因此，在Constant Amortized Time执行的函数的本质是这个“平均时间”;当呼叫数继续增加时，达到不会超过的上限。任何特定的调用可能在性能上有所不同，但从长期来看，这个平均时间不会变得越来越大。

这是在Constant Amortized Time执行的东西的基本优点。

小开

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

小开

我创建这个简单的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()

这将产生以下plotenter image description here


提交答案