持续摊还的时间

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＆＃322; Dowgird ）

Answer 3

要想出一种直观的思考方式，请考虑在动态数组中插入元素（例如，C ++中的 std :: vector 。让我们绘制一个图表，显示在数组中插入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万，那么2个操作与N（100万）相比并不是真正可比的数字，所以它被认为是常数或O（1）。

假设我们在另一个更大的房间里做了以上所有事情，并再次需要搬家。 它仍然是一样的。 比方说，N2（比如说10亿）是更大房间的新金额

所以，我们有N2（其中包括之前的N，因为我们将所有从小房间搬到更大的房间）

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

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

因此，当N从N增加到N2或其他时，它并不重要。它仍然是常数，或者每个N都需要O（1）运算。

---

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

只要你在房间里装钱，房间就会被填满。

当你去更大的房间时，假设它只能再装一个钱，总计2个钱。那意味着，

Answer 5

以上解释适用于聚合分析，即采用“平均”分析的概念。多次操作。 我不确定它们如何适用于银行家方法或物理学家摊销分析方法。

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

（摊销 - 运营成本之和）＆gt; =（实际运营成本之和）。

我面临的主要困难是，考虑到操作的摊销 - 渐近成本与正常 - 渐近成本不同，我不确定如何评估摊销成本的重要性。

那时候有人给我的摊销成本，我知道它与正常的渐近成本不一样我从摊余成本中得出什么结论？

由于我们有一些业务被多收，而其他业务收费不足，因此有一种假设可能是引用摊销 - 个别业务的成本将毫无意义。

例如：对于斐波那契堆，引用仅减少关键字为O（1）的摊销成本是没有意义的，因为成本因“早期操作增加堆的潜力所做的工作”而减少。

OR

我们可能有另一个假设，即摊销成本的原因如下：

1. 我知道昂贵的操作将在MULTIPLE LOW-COST操作之前进行。

2. 为了便于分析，我将对一些低成本的操作进行过度收费，例如他们的渐进式成本不会改变。

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

4. 因此，我改善/减少了n次操作成本的ASYMPTOTIC-BOUND。

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