本章内容：
1.聚合分析
2.核算法
3.势能法
4.动态表
一 聚合分析
1. 在摊还分析中，我们求数据结构的一个操作序列中所执行的所有操作的平均时间，来评价操作的代价，它不涉及概率，可以保证最坏情况下每个操作的平均性能。
2. 摊还代价：对所有n，一个n个操作的序列最坏情况下话费时间为T(n)，从而摊还代价（平均代价）为 T(n) / n.
3. 栈操作中加入MULTIPOP(S, k)，可以同时删除栈顶的k个元素，总元素少于k则全部删除。
下面分析一个由n个PUSH, POP, 和MULTIPOP组成的操作序列在一个空栈上的执行情况。假设栈的大小最大为n，那么MULTIPOP的最坏情况代价是O(n)。因此任意一个操作的最坏情况是O(n)，从而n个操作的序列的最坏情况代价为O(n ^ 2)。
上面并不是一个确界，用聚合分析考虑整个序列的n个操作可以得到更好的上界。在一个空栈上执行n个PUSH, POP, MULTIPOP操作，考虑到每个对象PUSH进入后最多只能POP一次，因此执行POP的次数不会多于PUSH的次数，因此最多有n次，即操作序列最多花费O(n)时间，平均代价即为O(n) / n = O(1).
4. k位二进制计数器递增：
用一个length为k的位数组A[0..K - 1]作为计数器。当保存值为x时，最低位在A[0]，最高位在A[k - 1]，有
初始x为0，为了实现计数器加1，使用如下过程：
粗略分析发现执行一次最坏情况需要将k个位置由1变为0，所以n此操作最坏情况似乎是O(nk)
进一步分析，每次INCREMENT时A[0]确实都要翻转，但是A[1]只需要2次执行翻转一次，A[2]则4次执行翻转一次...因此n个操作的序列，A[i]会翻转n
/ 2 ^ i 次，因此执行序列的翻转操作总数：
显然摊还代价为O(n) / n = O(1).
二 核算法
1. 对不同的操作赋予不同的费用，将赋予一个操作的费用称为它的摊还代价。当一个操作的摊还代价超出实际代价时，将差额存入数据结构中，称为信用，可以用来支付别的操作摊还代价比实际代价少的差额。
2. 
左边表示摊还代价总和，右边表示真实代价总和。总的信用等于上面左边减去右边，由于要保证摊还代价为实际代价上界，所以当前的总信用要保持为非负值。
3. 同聚合分析中的栈操作：
操作的实际代价为： 其中s为调用时栈的元素个数
我们给这些操作赋予如下的摊还代价：
可以这样进行考虑，每个元素PUSH进去的时候，需要支付2个单位的代价，其中PUSH操作实际用了一个，剩下的一个代价存起来。这样栈中的每个存在的元素其实自身都含有一个单位可用的代价，在出栈时无论是POP还是MULTIPOP都可以支付自己的出栈代价。由于栈里面的元素个数始终非负，所以可以保证信用始终非负。
因此，对任意n个操作序列的总摊还代价为实际代价的上界，即O(n).
4. 二进制计算器递增:
执行INCREMENT操作的运行时间与翻转的位数成正比，所以用翻转的位数作为操作的代价。
对一次置位操作（将该位由0变为1），设其摊还代价为2。进行置位时，用1来支付置位操作的实际代价，剩下的1存起来作为信用，该以后复位（变为0）的时候用。任何时刻信用值非负，因为计算器中1的个数始终非负。由于每次操作最多只进行一次置位（第6行），所以总摊还代价为O(n)，为实际代价的上界。
三 势能法
1. 对一个初始数据结构D0执行n个操作。Di为在数据结构Di-1上执行第 i 个操作得到的结果数据结构。势函数将Di映射到一个实数Φ(Di)，表示数据结构Di的势能，类似于前面的信用。有：
可以理解为摊还代价减去实际代价等于势能的增量。
n个操作总摊还代价：
将初始势能简单定义为0，然后要保证对所有 i
有Di的势能大于等于0.
2. 栈操作：
这里将势函数定义为一个栈中元素的数量，同时保证了永远非负。
第 i 个操作如果是PUSH，此时栈中有s个元素，则：
由此得到PUSH的摊还代价：
第 i
个操作如果是MULTIPOP，势能的减少恰好等于元素个数的减少，也等于实际操作的代价，有：
由此每个操作摊还代价都是O(1)，所以也可以得到总摊还代价O(n)
四 动态表
1.
原文：http://www.cnblogs.com/jolin123/p/3624588.html