摊还分析，是用一个数据结构在一个操作序列当中所有操作的平均时间，来评价操作代价的一种方法。摊还分析，不同于平均情况分析，不涉及任何概率，可以保证最坏(worst-case)下每个操作的平均性能。
一般认为，摊还分析得到的界比平均分析(average analysis)得到的界更紧，比最坏情况分析(worst-case analysisi)得到的界松。
在摊还分析当中，可以细分成三个子类：
ps：为了避免第二种尴尬的翻译，下文提到这三种方法均使用其英文。
在aggregate analysis当中，定义一个包含n的操作的操作序列，最坏情况下花费的总时间为$T(n)$，因此，在最坏情况下，每个操作的平均代价(或者称为摊还代价，amortized cost)为$\frac{T(n)}{n}$。这个摊还代价适用于操作序列里的所有操作，即使序列里有不同类型的操作。
在accounting method当中，不同的操作赋予不同的摊还费用。某些操作的代价(费用)可能高于实际费用，某些则可能低于实际。高于实际费用的差额，我们称之为信用。信用，存在数据结构的特定对象当中，用来支付那些低于实际费用的操作的差额。如果用$c_i$表示第i个操作的真实费用，用$\hat c_i$表示第i个操作的摊还费用，则对于任意n的操作的序列，应满足： \(\sum^{n}_{i=1}{\hat c_i}\ge\sum^{n}_{i=1}{c_i}\) 并且摊还代价和实际代价的差值，即数据结构当中的信用，应该永远大于等于零。如若允许信用为负，那么当时的摊还代价就会低于实际代价，总的摊还代价将不再是总实际代价的上界。
在potential method当中，不再将注意力放在数据结构的某些特定对象上，而是将目光放在整个数据结构上。或许你可以这样理解，将accounting method当中，该数据结构所有特定对象的信用全部加在一起，形成这个数据结构的“势能”。势能的释放，可以用来支付该数据结构未来操作的代价。
势能法的工作方式如下。对一个数据结构$D_0$执行n个操作，令$c_i$表示每个操作的实际代价，令$D_i$为在数据结构$D_{i-1}$上执行第i个操作所得到的结果数据结构。势能函数$\Phi$将每个数据结构$D_i$映射到一个实数$\Phi(D_i)$，这个值就是关联到数据结构$D_i$的势。令$\hat c_i$表示第i个操作的摊还代价，用势函数$\Phi$定义为：$\hat c_{i}=c_{i}+\Phi(D_i)-\Phi(D_{i-1})$，即每个操作的摊还代价等于实际代价加上此操作引起的势能变化。根据此式，可以推导出一个含有n的操作的序列的总摊还代价表达式：
\[\sum^{n}_{i=1}{\hat c_i}=\sum^{n}_{i=1}(c_i+\Phi(D_i)-\Phi(D_{i-1}))=\sum^n_{i=1}c_i+\Phi(D_n)-\Phi(D_0)\]观察上式，明显地如果$\Phi(D_n)-\Phi(D_0) \ge 0$，则这个式子给出了一个上界: \(\sum^{n}_{i=1}{\hat c_i} \ge \sum^{n}_{i=1}c_i\)。现在的问题是，是否存在一个$\Phi$函数，使得$\Phi(D_n)-\Phi(D_0) \ge 0$。实际当中，我们并不知道一个操作序列里有多少个操作，如果可以满足这个条件，则可以像accounting method那样，总能保证提前支付。
通常来说，为了保证这个条件，我们通常令$\Phi(D_0)$为零，然后证明对于所有的i，有$\Phi(D_i)\ge0$。
在算法界的名著CLRS (Introduction to Algorithm)当中，每种方法都用两个同样的例子展示了一次，它们分别是：
书中这一章节的最后，还有一个动态表 (dynamic tables)的例子。本文将叙述stack operation以及dynamic tables。
假设，对于一个栈S，我们有以下的操作：
最坏的情况是，一个操作序列里面所有的操作都是multipop，单个操作的复杂度是O(n)，那么有n个这样的操作的话，总复杂度就是O($n^2$)了。这么分析，没有错误，但是样分析得到的界，并不是紧的。因为，我们不可能执行n个multipop操作。一个对象入栈一次，我们至多只能将其弹出一次。也就是说，对于一个含有n个元素的栈，执行pop操作(包含常规的pop和multipop)的次数，最多只能等于执行push操作的次数，即至多n次。因此，对于一个由push、pop、multipop共n个操作组成的序列，最多花费O(n)的时间，任意单个操作时间为$\frac {O(n)}{n}=O(1)$。
在前面的分析当中，栈操作的每一个操作的代价都是O(1)。但是，实际上栈操作的代价应该是 (为了更好理解，这里用货币单位来表示，$(X)后面括号里的数X，理解成X任意货币，例如X美元、X人民币)：
| push | pop | multipop |
|---|---|---|
| $(1) | $(1) | $(min(k, s)) |
回顾accounting method的理论部分，我们人为的给每个操作赋予一个摊还代价，一些可能大于实际值，一些可能小于实际值，在这个例子当中，赋值如下：
| push | pop | multipop |
|---|---|---|
| $(2) | $(0) | $(0) |
问题来了，为什么要这么赋值呢？原因是这样的，push操作收取用户2美元，这个钱的用法如下：
因为，每个元素压入栈后，不论是被常规的pop方法弹出还是被multipop方法弹出，总共只能被弹出一次。所以，只需1美元存在该元素当中即可。
另外，栈中的元素一直都是非负的，所以，保证了信用值也总是非负的，满足accounting method的条件。因此，对任意n个push、pop、multipop操作组成的序列，总摊还代价是总实际代价的上界。由于总摊还代价为O(n)，所以总实际代价也是。
为了应用势能法，首先定义一个栈的势能为：栈中元素的数量。对于空栈，令其势能为零，即$\Phi(D_0)=0$。由于栈中的元素数量不可能为负，因此第i次操作得到的栈势能$D_i \ge 0 = \Phi(D_0)$。
下面，分别计算上述三个操作的摊还代价 (实际代价如下表，和上文的表相同，$c_i$从表中得到)：
| push | pop | multipop |
|---|---|---|
| $(1) | $(1) | $(min(k, s)) |
如果第i个操作是push，此时栈中有s个元素，则势能差为：
\[\Phi(D_i)-\Phi(D_{i-1})=(s+1)-s=1\]所以，push操作的摊还代价为：
\[\hat{c}_i=c_i+\Phi(D_i)-\Phi(D_{i-1}) =1+1=2\]如果第i个操作是pop，此时栈中有s个元素，则势能差为：
\[\Phi(D_i)-\Phi(D_{i-1})=(s-1)-s=-1\]所以，pop操作的摊还代价为：
\[\hat{c}_i=c_i+\Phi(D_i)-\Phi(D_{i-1}) =1+(-1)=0\]如果第i个操作是multipop，将k‘=min(k, s)个元素弹出，则势能差为：
\[\Phi(D_i)-\Phi(D_{i-1})=-k’\]所以，multipop操作的摊还代价为：
\[\hat{c}_i=c_i+\Phi(D_i)-\Phi(D_{i-1})=k'-k'=0\]显然，对于上述的三种操作，我们都有$\Phi(D_n)-\Phi(D_0) \ge 0$，所以\(\sum^{n}_{i=1}{\hat c_i}\ge\sum^{n}_{i=1}{c_i}\)，即总摊还代价是实际代价的上界。由aggregate analysis知，每个操作的摊还代价为O(1)，当然也可以使用accounting method当中设定的摊还代价，所以由n个操作组成的序列，其最坏情况的时间为O(n)。
动态表的意思是，这个表可以根据表中元素的数量自动扩张或者缩小。数据结构的这个特性可以合理的利用空间，减少对空间的浪费。首先，对表的扩张和收缩的方法做出如下定义：
每当一个表的容量发生变化时(扩张、收缩)，唯一的做法是向内存申请一个定值空间用来新建一个表(不存在直接把某段内存拼接到当前表后面的方法)，然后把表中的所有元素“复制”到新的表上，最后将当前表指向新表，释放旧表的空间。
为了更清晰地说明动态表的操作，需要先给出装载因子(load factor)的定义。假设有一个表T，规定当表为空，即T.size = 0时$\alpha=1$。其他情况下则有： \(\alpha=\frac{T.num}{T.size}\)
什么时候，表需要扩张呢？很明显，是表里的元素满了的时候。表的扩张可以有很多种方法，比较常见的做法是把表的大小翻倍，然后把旧表里的元素拷贝到新表上。通过这个方法可以保证，表的装载因子始终大于$\frac{1}{2}$，即可以保证表中的空间得到较为充分的利用，每次表中最多只有一半的空间是空的。
从摊还分析的角度来看，我们首先要保证每次表扩张后，整个表(数据结构)的势能应该是零。因为要求是非负，为了得到最低的摊还代价，所以至少是零。每次往表中插入一个新的元素，我们收取用户$3 (常数代价)：
其中第三点，每次新表里都有一半元素没有任何信用。但是当新表满了的时候，刚好多了一半元素，每个元素贡献多了1美元，这些钱刚好可以用于表下一次扩张。
有了上面的方法，很容易会想到，表的收缩也是同样的道理。当表里的元素少过表的大小的$\frac{1}{2}$时，把表收缩成原来大小的一半。但是很遗憾，这个想法是不可行的。考虑下面一个例子：假设有一个n个操作的序列，前$\frac{n}{2}$个操作当中把表的大小变成了$\frac{n}{2}$满，然后依次执行：
insert, delete, delete, insert, delete, delete, insert, delete, delete, insert, delete, delete … …
这样的话，每次insert之后，表就要扩张，每两次delete之后，表就要收缩。但是，每次表扩张或者收缩后，表里的信用和 (势能)为零。然而，紧接的操作就要表再次改变表容量，在这种情况下，表(数据结构)里并没有足够的信用去支持表的这些操作，这会导致摊还代价很大的情况发生。
要解决这个问题也很简单。表的扩张策略不变，依旧是表里元素装满后，将表的大小翻倍。但是，只有当表里的元素小于$\frac{1}{4}$满时，才对表进行收缩。这就很好理解了，如果表里的元素少于一半就收缩的话，新表里的元素仍然是满的，再来一个插入的操作就得表扩张，但是如果是少于四分之一再收缩的话，新表里的元素就是一半满的，这样可以再插入一半新表的容量的元素后，表再扩张。通过这个策略，可以保证表的任意一种操作都可以在常数的时间内完成。
最后，来一个思考题。请你希望设计一个数据结构，要求该数据所有操作的摊还代价是常数时间，需要提供下列三种操作：