一、摊还分析         概念：是求数据结构中一个操作序列执行所有操作的平均时间，与平均复杂度不同，它不涉及输入概率，能够保证在最坏情况下操作的平均性能。         适用场景：用含 n 个操作的序列（o1，o2，,,,,on） 维护某数据结构         操作代价：单次操作代价可能会很大，在最坏情况下代价为 max(oi) 二、摊还分析的三种方法         以栈的操作

摊还分析中的势能法：原理、伪代码与C语言实现 一、势能法的基本概念二、势能法的伪代码示例：栈的MULTIPOP操作三、势能法的C代码示例：二进制计数器的INCREMENT操作 势能法是摊还分析中的一种技术，它通过将数据结构的某些状态视为具有“势能”，从而分析操作的代价。在势能法中，每个操作的摊还代价由其实际代价加上势能的变化量组成。这种方法允许某些操作以较低的代价完成，而节省下来的

每种摊还分析的方法，都已栈操作和二进制计数器递增来拿出来讲解。

在算法导论随笔(一): 操作计数与复杂度Big（O）中，我简单介绍了计算一个算法的时间复杂度的方法。该方法的计算结果虽然都是正确的，但有时不一定特别准确地代表复杂度函数的渐进上界。因此，人们创建了一个分析方式，可以更精确地表示一个复杂度函数的渐进上界。这个分析方式就是我今天要介绍的摊还分析。 1.为什么要引入摊还分析 前文说到，使用分析操作计数的方法来计算时间复杂度时，有的时候求出的渐进上限并

Amortized Analysis 摊还分析考察一个操作序列中所执行的所有操作的平均时间，来评价操作的代价。这个操作序列中也许某一操作的代价很高，但因为还有其他操作，所以这些操作的平均代价并没有那么高。 本文将首先将这种代价分析方式与最坏情况时间复杂度和平均时间复杂度两种方式进行区分，然后通过一篇其他人的博文说明摊还分析的三种方法，并对三种方法进行简要总结，最后对摊还分析方法进行实践。