固定摊余时间

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

如果你做了一百万次手术,你不会真正关心手术的最坏情况或最好情况——你关心的是当你重复一百万次手术时,总共花费了多少时间。

因此,只要“偶尔一次”的速度足够低,可以冲淡缓慢的速度,操作是否非常缓慢并不重要。基本上,摊销时间是指“如果你做了许多操作,每个操作所用的平均时间”。摊销时间不必是常数;您可以有线性和对数摊销时间,或者其他任何时间。

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

所以每次放大,所需时间大约是上次放大的两倍。但你也等了两次才做!因此,每次扩大的成本可以在插入物之间“分摊”。这意味着从长远来看,增加 米 数组中的项是 O(m) 因此,摊销时间(即每次插入的时间)为 O(1) .

这意味着,随着时间的推移,最坏的情况将默认为O(1),或常量时间。一个常见的例子是动态数组。如果我们已经为一个新条目分配了内存,那么添加它将是O(1)。如果我们没有分配它,我们将通过分配,比如说,两倍于当前金额来分配。这个特殊的插入将 不 是O(1),但不是别的。

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

或者更严格地说,

有一个常数c,这样 每一个 操作顺序(也是以成本高昂的操作结束的操作) 长度L,时间不大于 C*L(谢谢) Rafał Dowgird )

为了开发一种直观的思考方法,考虑在 dynamic array (例如 std::vector 在C++中。让我们绘制一个图表,显示在数组中插入n个元素所需的操作数(y)的依赖关系:

黑图的垂直部分对应于内存的重新分配,以便展开一个数组。在这里,我们可以看到这个依赖关系可以粗略地表示为一条线。这个直线方程是 Y=C*N + b ( C 是常数, b =0)。所以我们可以说我们需要 C*N 平均向数组中添加n个元素的操作,或 C*1 添加一个元素的操作(摊余固定时间)。

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

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

“动态数组”

动态数组推送操作的摊销分析

考虑一个动态数组,该数组随着添加更多元素而增大。 比如Java中的ARARYLIST。如果我们从一个动态数组开始 对于4号,将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万)相比,这两个操作实际上不是一个可比较的数字,所以它被认为是常数或O(1)。

假设当我们在另一个更大的房间里做以上所有的事情时,又需要搬家。 还是一样的。 比如说,n2(比如说10亿美元)是大房间里新的货币数量

所以,我们有n2(包括之前的n,因为我们都从小房间搬到大房间)

我们仍然只需要两个操作,一个是插入更大的房间,然后另一个移动操作移动到更大的房间。

因此,即使对于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点钱
第三个房间的大小=适合8点钱
第四个房间尺寸=适合16个货币数量
第5间房=32元
第6间房=64元
第7间客房尺寸=适合128美元
第8间房=256元
第9间房=512元
第10间房=1024元
第11间客房尺寸=适合2048美元
…
第16间客房尺寸=适合65536美元
…
第32间客房尺寸=适合4294967296货币数量
…
第64间客房尺寸=适合18446744073709551616货币数量

为什么这样更好?因为与RAM中的内存量相比,它看起来在开始时增长缓慢,在以后增长更快。

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

然而,在最后一个例子中,2的幂,它在RAM的限制中增长。因此,增加2的力量,装甲分析保持不变,对我们今天所拥有的有限RAM是友好的。

上述解释适用于聚合分析,即在多个操作中取“平均值”。 我不知道它们是如何应用于银行家方法或物理学家的摊余分析方法的。

现在。我不太确定正确答案。 但这与两位物理学家+银行家的方法的基本条件有关:

(摊余经营成本之和)>=(实际经营成本之和)。

我面临的主要困难是,鉴于摊余渐进成本不同于正常渐进成本,我不知道如何评估摊余成本的重要性。

也就是说,当有人给我一个摊余成本时,我知道它与正态渐近成本不一样,那么我从摊余成本中得出什么结论呢?

由于我们有一种情况,即某些业务被高估,而其他业务被低估,一种假设可能是,引用单个业务的摊余成本将毫无意义。

例如:对于斐波那契堆,引用只减少键o(1)的摊余成本是毫无意义的,因为成本是通过“早期操作在增加堆潜力方面所做的工作”来降低的。

或

我们可以有另一个假设,即摊余成本的原因如下:

1. 我知道这项昂贵的行动之前会有多个低成本的行动。

2. 为了便于分析,我打算多收一些低成本的操作,这样它们的渐进成本就不会改变。

3. 通过这些增加的低成本操作,我可以证明昂贵的操作具有较小的渐进成本。

4. 因此,我改进/降低了n个操作成本的渐近界。

因此,摊余成本分析+摊余成本界限现在只适用于昂贵的业务。廉价操作的渐进摊余成本与其正常渐进成本相同。