恒定摊销时间

摊销时间简单解释：

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

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

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

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

---

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

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

或者更严格地说，

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

---

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

https://i.stack.imgur.com/CPP0P.jpg

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

---

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

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

“动态数组推送操作的动态数组摊销分析考虑一个随着更多元素添加到其中的动态数组，例如 Java 中的 ArrayList。如果我们开始使用大小为 4 的动态数组，则需要将四个元素推入它的恒定时间。但是将第五个元素推入该数组将花费更长的时间，因为该数组必须创建一个当前大小的两倍（8）的新数组，将旧元素复制到新数组中，然后添加新元素。接下来的三个 push 操作同样需要恒定的时间，然后随后的添加将需要另一个缓慢的数组大小加倍。一般来说，如果我们考虑将任意数量的 push n 到大小为 n 的数组中，我们请注意，推送操作需要恒定时间，除了最后一个需要 O(n) 时间来执行大小加倍操作的操作。由于总共有 n 个操作，我们可以取其平均值，并发现将元素推送到动态阵列上y 需要：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 是友好的。

---

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

https://i.stack.imgur.com/0CQd7.png

---

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

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

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

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

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

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

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

或者

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

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

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

---

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

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

这是在 Constant Amortized Time 执行的某项的基本优点。

---

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

---