问题描述
它与渐近分析有何不同?你什么时候使用它，为什么?
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:
http://www.cs.princeton.edu/~fiebrink/423/AmortizedAnalysisExplained_Fiebrink.pdf
但我还没有完全理解这些概念.
but I've still not understood fully these concepts.
那么，谁能帮我简化一下?
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 个项目，而不会导致自前一个增长以来的增长，因此添加一个项目实际上只需要 O(1)(O(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.
这篇关于什么是算法的摊销分析?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！