见知乎专栏https://zhuanlan.zhihu.com/p/
摊还分析用来评价某个数据结构的一系列操作的平均代价，有时可能某个操作的代价特别高，但总体上来看也并非那么糟糕，可以形象的理解为把高代价的操作“分摊”到其他操作上去了，要求的就是均摊后的平均代价。
摊还分析有三种常用的技术：聚合分析，核算法，势能法。
下面讲两个简单的例子来说明。
PUSH(S,x):将对象x压入栈S中。
POP(S):将栈S的栈顶对象弹出，并返回该对象。对空栈调用POP会产生一个错误。
MULTIPOP(S,k):循环调用POP(S)，弹出栈顶的k个元素（k<n，n为栈的最大容量）。
其中，第三种操作的伪代码如下：
MULTIPOP(S,k)
while not STACK-EMPTY(S) and k>0
POP(S)
k=k-1
那么，现在需要分析：执行n次栈操作最坏情况下的时间复杂度是多少？
分析：
单独看三个操作，前两个都是 [公式] 的，第三个是 [公式] 的。这样直观的看，最
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/39838.html