不变摊销时间
在谈论algorithm的时间复杂度时，“恒定的摊销时间”是什么意思？
摊销时间用简单的术语解释：
如果你做了一百万次的手术，那么你并不关心手术的最坏情况或最好的情况 – 你关心的是当你重复手术一百万次时总共需要多less时间。
所以，如果手术时间很慢，只要“偶尔一次”足够稀less，慢慢的被稀释就没有关系。 本质上分摊的时间意味着“如果进行多项操作，则每次操作所花费的平均时间”。 摊销时间不一定是恒定的。 你可以有线性和对数摊销时间或其他任何东西。
我们来看一个dynamic数组的例子，你可以反复添加新的项目。 通常添加一个项目需要一定的时间（即O(1) ）。 但是，每次数组满了时，都会分配两倍的空间，将数据复制到新的区域，并释放旧的空间。 假设分配和释放在恒定时间内运行，这个放大过程需要O(n)时间，其中n是数组的当前大小。
所以每次放大的时候，你要花费两倍的时间。 但是在做之前，你还等了两倍！ 每个扩大的成本因此可以在插入中“扩散”。 这意味着从长期来看，将m个项目添加到数组所花费的总时间是O(m) ，所以分摊时间（即每个插入的时间）是O(1) 。
这意味着，随着时间的推移，最糟糕的情况将默认为O（1），或恒定的时间。 一个常见的例子是dynamic数组。 如果我们已经为一个新条目分配了内存，那么添加它就是O（1）。 如果我们没有分配它，我们将通过分配两倍的当前数量来实现。 这个特殊的插入不是 O（1），而是其他的东西。
重要的是，该algorithm保证，在一系列操作之后，昂贵的操作将被分摊，从而呈现整个操作O（1）。
或者更严格地说，
有一个常数c，这样对于长度为L的每一个操作序列（也是一个以高成本操作结尾的序列），时间不大于c * L（感谢RafałDowgird ）
为了开发一种直观的思维方式，考虑在dynamic数组中插入元素（例如C ++中的std::vector ）。 让我们绘制一个图，它显示了在数组中插入N个元素所需的操作数（Y）的依赖关系：
黑图的垂直部分对应于内存的重新分配以扩展数组。 在这里我们可以看到，这个依赖可以粗略地表示为一条线。 这条直线方程是Y=C*N + b （ C是常数，在我们的例子中是b = 0）。 因此，我们可以说我们需要平均花费C*N操作将N个元素添加到数组，或者C*1操作添加一个元素（摊还常量时间）。
我在下面发现维基百科解释有用，重复阅读3次后：
来源： https ： //en.wikipedia.org/wiki/Amortized_analysis#Dynamic_Array
“dynamic数组
dynamic数组推动操作的分期分析
考虑一个随着更多元素添加到其中的dynamic数组，如Java中的ArrayList。 如果我们开始使用大小为4的dynamic数组，则需要花费不变的时间将四个元素推到其上。 然而，将第五个元素推送到该数组将花费更长的时间，因为该数组将不得不创build一个新的当前大小的数组（8）的数组，将旧的元素复制到新的数组，然后添加新的元素。 接下来的三个push操作同样会花费不变的时间，然后后续的添加将需要另一个缓慢加倍的数组大小。
一般情况下，如果我们考虑任意数量的n到大小为n的数组，我们注意到，除了最后一个需要O（n）次执行大小加倍操作的操作之外，推式操作需要一定的时间。 由于总共有n个操作，我们可以取这个平均值，并发现将元素推入dynamic数组需要：O（n / n）= O（1），常数时间。
上面的解释适用于综合分析，即对多个操作采取“平均”的概念。 我不知道他们如何适用于银行家方法或物理学家摊销分析方法。
现在。 我不完全确定正确的答案。 但这与物理学家+银行家的方法的原则条件有关：
（摊余成本之和）> =（实际成本之和）。
我面临的主要困难是，鉴于摊余 – 渐近成本与正常渐近成本不同，我不确定如何评估摊余成本的重要性。
那是什么时候有人给我一个摊销成本，我知道它与正常渐近成本不一样。那么，我从摊销成本中得出什么结论呢？
由于我们有一些业务收费过高而其他业务收费不足，有一个假设可能是引用个别业务的摊销成本是没有意义的。
例如：对于一个斐波那契堆来说，只是将递减关键字的分摊成本引用为O（1）是没有意义的，因为通过“早期操作增加堆的可能性所做的工作”来降低成本。
要么
我们可以有另外一个关于摊销成本的假设：
-
我知道昂贵的操作将在多个低成本操作之前进行。
-
为了分析起见，我打算对一些低成本的业务收费过高，这样他们的渐进成本就不会改变。
-
随着这些增加的低成本作业，我可以certificate昂贵的操作有一个较小的渐近成本。
-
因此，我已经改进/减less了n次操作成本的渐近限制。
因此，摊销成本分析+摊销成本边界现在仅适用于昂贵的操作。 廉价操作具有与其正常渐近成本相同的渐近分摊成本。
