什么是算法平摊分析？ [英] What is amortized analysis of algorithms?

问题描述

？它与渐近分析有什么不同？当你使用它，为什么？ 我读过一些文章，似乎已经写得好这样的：

How is it different from asymptotic analysis? When do you use it, and why? I've read some articles that SEEM to have been written well like these:

<一个href="http://www.ugrad.cs.ubc.ca/~cs320/2010W2/handouts/aa-nutshell.pdf">http://www.ugrad.cs.ubc.ca/~cs320/2010W2/handouts/aa-nutshell.pdf

<一个href="http://www.cs.princeton.edu/~fiebrink/423/AmortizedAnalysisExplained_Fiebrink.pdf">http://www.cs.princeton.edu/~fiebrink/423/AmortizedAnalysisExplained_Fiebrink.pdf

...但可能是我愚蠢的，所以任何人都可以请简化一下吗？

...but may be I'm dumb, so can anyone please simplify it for me?

推荐答案

平摊分析并不天真地乘调用的最坏情况下的数量一次调用。

Amortized analysis doesn't naively multiply the number of invocations with the worst case for one invocation.

例如，对于一个动态数组需要时增加一倍的大小，正常的渐进分析只能得出这样的结论将项目添加到它的成本为O（n），因为它可能需要成长和复制所有元素到新的数组。平摊分析考虑到为了有成长，N / 2项必须已经增加，而不会导致增长自previous增长，因此增加一个项目实际上只是利用了○○（1）（成本（ n）是的摊销的超过N / 2的操作）。

For example, for a dynamic array that doubles in size when needed, normal asymptotic analysis would only conclude that adding an item to it costs O(n), because it might need to grow and copy all elements to the new array. Amortized analysis takes into account that in order to have to grow, n/2 items must have been added without causing a grow since the previous grow, so adding an item really only takes O(1) (the cost of O(n) is amortized over n/2 actions).

平摊分析是不一样的表现平平 - 摊销分析得到什么，如果你做了这么多动作的表现会做的很难保证的

Amortized analysis is not the same as an "average performance" - amortized analysis gives a hard guarantee on what the performance will do if you do so much actions.

这篇关于什么是算法平摊分析？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！