algorithm - 关于摊销分析

Question

这是关于摊销分析。以下是文章中的文字。

Amortized analyis for problems in which one must perform a series of operations, and our goal is to analyze the time per operation. The motivation for amortized analysis is that looking at the worst case time per operation can be too pessimistic if the only way to produce an expensive is to "set it up" with a a large number of cheap operations before hand.

问题:作者最后的陈述是什么意思，即“如果产生昂贵的唯一方法是在之前用大量便宜的操作”设置它“手”？谁能举例说明这句话的意思？

谢谢!

Answer 1

另一个例子。考虑一个数组，当添加一个超过当前容量的元素时动态增加它的容量。让增加容量为 O(n)，其中 n 是数组的旧大小。现在，添加一个元素的最坏情况复杂度为 O(n)，因为我们可能不得不增加容量。摊销分析背后的想法是，您必须在容量耗尽之前执行 n 个简单的加法，其成本为 O(1)。因此，许多便宜的操作导致一个昂贵的操作。换句话说，昂贵的操作由便宜的操作摊销。