474

在谈论算法的时间复杂度时，“恒定摊销时间”是什么意思？

4

8 回答 8

860

摊销时间简单解释：

如果您进行操作说一百万次，您并不真正关心该操作的最坏情况或最佳情况 - 您关心的是当您重复操作一百万次时总共花费了多少时间.

因此，操作是否偶尔非常缓慢并不重要，只要“偶尔”足够稀有，可以将缓慢冲淡掉。基本上摊销时间是指“每次操作所花费的平均时间，如果你做了很多操作”。摊销时间不必是恒定的；你可以有线性和对数摊销时间或其他任何东西。

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

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

于 2008-10-30T09:48:34.520 回答
59

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

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

或者更严格地说，

有一个常数 c，因此对于 长度为 L 的每个操作序列（也以代价高昂的操作结束），时间不大于 c*L（感谢Rafał Dowgird）

于 2008-10-14T08:48:11.053 回答
33

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

阴谋

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

于 2017-01-19T10:17:41.617 回答
18

在重复阅读 3 次后，我发现下面的 Wikipedia 解释很有用：

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

“动态阵列

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

考虑一个动态数组，它随着更多元素的添加而增长，例如 Java 中的 ArrayList。如果我们从一个大小为 4 的动态数组开始，将四个元素压入它需要恒定的时间。然而，将第五个元素推入该数组需要更长的时间，因为该数组必须创建一个两倍于当前大小 (8) 的新数组，将旧元素复制到新数组中，然后添加新元素。接下来的三个 push 操作同样需要恒定的时间，然后随后的添加将需要另一个缓慢的数组大小加倍。

一般来说，如果我们考虑将任意数量的推送 n 到大小为 n 的数组，我们注意到推送操作需要恒定时间，除了最后一个需要 O(n) 时间来执行大小加倍操作的操作。由于总共有 n 次操作，我们可以取其平均值，并发现将元素推入动态数组需要：O(n/n)=O(1)，恒定时间。”

我的理解是一个简单的故事：

假设你有很多钱。而且，你想把它们堆放在一个房间里。而且，您的手和腿很长，只要您现在或将来需要。而且，你必须把所有东西都填在一个房间里，所以很容易把它锁起来。

因此，您直接走到房间的尽头/角落并开始堆叠它们。当你堆叠它们时，房间会慢慢地用完空间。但是，当您填充时，很容易将它们堆叠起来。拿到钱，放钱。简单的。它是 O(1)。我们不需要转移任何以前的资金。

一旦房间空间不足。我们需要另一个更大的房间。这里有一个问题，因为我们只能有 1 个房间，所以我们只能有 1 个锁，我们需要把那个房间里所有现有的钱都转移到新的更大的房间里。所以，把所有的钱，从小房间转移到大房间。即，再次将它们全部堆叠。所以，我们确实需要转移所有以前的钱。因此，它是 O(N)。（假设 N 是前一笔钱的总金额）

换句话说，很容易直到 N，只有 1 次操作，但是当我们需要搬到更大的房间时，我们做了 N 次操作。所以，换句话说，如果我们平均下来，它是在开始时插入 1 次，然后在移动到另一个房间时再移动 1 次。总共 2 次操作，一次插入，一次移动。

假设即使在小房间里 N 也像 100 万一样大，那么与 N（100 万）相比的 2 次操作并不是一个真正的可比数字，因此它被认为是常数或 O(1)。

假设当我们在另一个更大的房间里做以上所有事情时，又需要搬家。它仍然是一样的。比如说，N2（比如说，10 亿）是更大房间里新的钱数

所以，我们有 N2（包括以前的 N，因为我们把所有房间都从小房间搬到了大房间）

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

因此，即使对于 N2（10 亿），每个操作也是 2 次。这又没什么了。所以，它是常数，或 O(1)

因此，随着 N 从 N 增加到 N2 或其他，这并不重要。它仍然是恒定的，或者 N 中的每一个都需要 O(1) 次操作。

现在假设，你有 N 为 1，非常小，钱数很少，你有一个很小的房间，只能容纳 1 个钱。

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

当你去更大的房间时，假设它只能再装1个钱，总共2个钱。这意味着，前一个移动的钱和另外 1 个。它又被填满了。

这样，N 增长缓慢，不再是 O(1) 常数，因为我们将所有钱从前一个房间转移，但只能再容纳 1 个钱。

100 次后，新房间可以容纳 100 元以前的钱，还能容纳 1 多钱。这是O(N)，因为O(N+1)就是O(N)，也就是100和101的度数相同，都是百，而不是之前的故事，一到百万，一到十亿.

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

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

第 1 个房间大小 = 适合 1 个钱币
第 2 个房间大小 = 适合 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 是友好的。

于 2016-07-08T07:42:23.433 回答
3

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

这会产生以下情节在此处输入图像描述

于 2021-02-17T06:10:47.513 回答
1

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

现在。我不确定正确的答案。但这与物理学家+银行家方法的主要条件有关：

（摊销运营成本总和）>=（实际运营成本总和）。

我面临的主要困难是，鉴于运营的摊销渐近成本不同于正常渐近成本，我不确定如何评估摊销成本的重要性。

那就是当有人给我一个摊销成本时，我知道它与正常渐近成本不同那我从摊销成本中得出什么结论？

由于我们有一些操作被多收而其他操作被少收的情况，一个假设可能是引用单个操作的摊销成本将毫无意义。

例如：对于斐波那契堆，仅将递减键的摊销成本引用为 O(1) 是没有意义的，因为“早期操作在增加堆潜力方面所做的工作”会降低成本。

或者

我们可以有另一个假设来解释摊销成本的原因如下：

  1. 我知道昂贵的操作将在多个低成本操作之前进行。

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

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

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

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

于 2013-05-10T20:38:35.990 回答
1

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

因此，执行函数的本质Constant Amortized Time是，这个“平均时间”达到了一个上限，随着调用次数的不断增加，这个上限不会被超过。任何特定调用的性能可能会有所不同，但从长远来看，这个平均时间不会越来越大。

这是在Constant Amortized Time.

于 2019-09-04T09:14:49.120 回答
0

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

于 2020-12-26T07:46:54.110 回答