不变摊销时间
谈论算法的时间复杂度时，“恒定摊销时间”是什么意思？
摊销时间用简单的术语解释：
如果你做了一百万次手术，你并不关心这种手术的最坏情况或最佳情况 - 你关心的是当你重复手术一百万次时总共需要多少时间。
所以，如果手术一度很缓慢，只要“偶尔一次”足够稀释缓慢就可以了。 本质上分摊的时间意味着“如果您进行了许多操作，则每次操作的平均时间”。 摊销时间不一定是恒定的; 你可以有线性和对数分期时间或其他任何东西。
我们来看一个动态数组的示例，您可以重复添加新项目。 通常添加一个项目需要一定的时间（即O(1) ）。 但是每次数组满了时，都会分配两倍的空间，将数据复制到新的区域，并释放旧的空间。 假设分配和释放在恒定时间内运行，这个放大过程需要O(n)时间，其中n是数组的当前大小。
所以每次放大时，您的时间大约是最后一次放大的两倍。 但是在做之前你还等了两次！ 因此每个扩大的成本可以在插入中“分散”。 这意味着从长期来看，将m项添加到数组所花费的总时间为O(m) ，所以摊余时间（即每次插入的时间）为O(1) 。
这意味着，随着时间的推移，最糟糕的情况将默认为O（1）或恒定时间。 一个常见的例子是动态数组。 如果我们已经为一个新条目分配了内存，那么将它添加为O（1）。 如果我们没有分配它，我们将通过分配两倍的当前数量来实现。 这个特殊的插入不会是O（1），而是其他的东西。
重要的是，该算法保证了在一系列操作之后，昂贵的操作将被摊销并且由此呈现整个操作O（1）。
或者更严格地说，
有一个常数c，对于长度为L的每一个操作序列（也有一个以高成本操作结束），时间不大于c * L（感谢RafałDowgird）
为了开发一种直观的思维方式，考虑在动态数组中插入元素（例如C ++中的std::vector ）。 让我们绘制一个图，它显示了在数组中插入N个元素所需的操作数（Y）的依赖关系：
黑图的垂直部分对应于内存的重新分配以扩展数组。 在这里我们可以看到这个依赖关系可以粗略地表示为一条线。 这条直线方程是Y=C*N + b （ C是常数，在我们的例子中是b = 0）。 因此我们可以说，我们需要平均花费C*N操作向数组添加N个元素，或者添加一个元素（摊余常量时间）来添加C*1操作。