什么是算法的摊销分析？
与渐进分析有何不同？您何时使用它，为什么？
我读过一些写得不错的文章，例如：
http://www.ugrad.cs.ubc.ca/~cs320/2010W2/handouts/aa-nutshell.pdf
http://www.cs.princeton.edu/~fiebrink/423/AmortizedAnalysisExplained_Fiebrink.pdf
但我仍然没有完全理解这些概念。
那么，有人可以为我简化一下吗？
回答：
摊销分析不会天真地将调用次数与一次调用的最坏情况相乘。
例如，对于需要时将大小增加一倍的动态数组，正常的渐近分析只会得出结论，将一个项目添加到该数组中会花费O（n），因为它可能需要增长并将所有元素复制到新数组中。摊销分析考虑到要进行增长，必须添加n / 2个项目，而自上一次增长以来就不会导致增长，因此添加项目实际上仅需O（1）（O（n）的成本为分摊到n / 2个操作中）。
摊销分析与“平均绩效”不同-摊销分析对如果您执行大量操作将对绩效产生什么影响提供了硬性保证。
以上是 什么是算法的摊销分析？ 的全部内容， 来源链接： utcz.com/qa/421129.html
