算法导论_17.1-17.3平摊分析

平摊分析：执行一系列数据结构操作所需要的时间是通过对执行的所有单个操作求平均得出的；即单个操作所需的时间 = 所有操作消耗的时间/操作次数；
即便单个操作的代价很大， 但是平均代价很小；
平摊分析与平均情况分析的不同之处是平摊分析不涉及概率， 即使在最坏的情况下， 每个操作都具有平均性能；

举例说明平摊分析与平均情况分析的区别：
例如有三个操作，耗时是1， 2， 3； 三个操作被执行的频率是0.5， 0.2， 0.3;
平摊分析不考虑频率：（1+2+3）/3 = 2；
平均情况分析：1×0.5 + 2×0.2 + 3×0.3 = 2.2；
三种常用的平摊分析技术：
1） 聚集分析
用于确定一个操作序列（共n个序列）的总代价上界T(n),每个操作的平均代价是T(n)/n。将平均代价当作每个操作的平摊代价；（每个操作都具有相同的平摊代价）
2） 记账分析
当有一种以上的操作时， 每种操作都可能有一个不同的平摊代价。
记账分析技术对操作序列中某些操作先多记账，将多记的部分作为对数据结构中特定对象上的预付的存款存起来。在序列操作中，稍后的操作需要用到这些存款；
3） 势能方法
与记账方法的相似之处是要确定每个操作的平摊代价， 而且可能先对吃哦啊做多记账以补偿以后的不足记账。这种方法将存款作为数据结构整体的势能来维护，而不是将存款和数据结构中的单个对象联系；

一、聚集分析

注意理解平摊分析与平均情况分析的区别，注意聚集分析是使用操作的平均情况代价作为平摊代价的；
由n个操作序列的总时间是T(n), 其平均代价是T(n)/n, 即为平摊代价；平摊代价对于每次操作都是一样的，即使操作的类型不一样；
举例说明：
1） 栈操作
有三个栈操作：
PUSH(S, x)：将x压入栈，时间代价爱O(1)
POP(S)：弹出栈顶数据，时间单价(O(!)
MULTIPUSH(S, k)：一次弹出k个数据,时间代价O(k)
操作序列sequence是包含这三个操作的一个序列，假设操作系列中每个操作都是最坏情况，则总的时间代价是O(n) ×n = O(n^2)；
但是考虑平均情况分析， 考虑三种操作出现的概率， 其中MULTIPUSH操作出现的次数肯定很少， POP操作出现次数肯定大于PUSH。更进一步， 对于一个容量为n的空的栈，出战操作应当等于入栈操作；
因此操作序列sequence的总时间是O(n)， 单个操作的时间是O(1)；
记住：聚集分析中，将平均情况代价（考虑操作的频率）作为平摊分析；

2） 二进制计数操作
对k位的计数器进行计数，每一位由0变为1或是由1变为0 是一个操作，代价是O(1);
在计数的过程中， 最坏的情况是当1111 变为0000的时候，时间代价是O(n)；
一个操作序列sequence, 共有n个操作，最坏的时间代价是O(n)×n = O(n^2）；但是在计数过程中， 不是每一次操作都是最坏情况， 最坏情况的频率实际很小。
更进一步分析：
第0位每次操作时候都要变化，n次操作时间代价是O(n)；
第1位每2次操作时候才要变化，n次操作时间代价是O(n/2)；
第k位， 没2^k次操作才要变化，n次操作时间代价是O(n)/2 ^k；
总计， k位的计数器， n次操作时间代价是O(2n)， 单次操作时间代价是O(1）；

二、记账方法

区分不同的操作类型， 对不同类型的操作收取不同的费用。某些操作的费用多余实际代价，某些操作费用少于实际代价；
对一个操作的收费记作平摊代价， 当一个操作的平摊代价超过了实际代价时候，多余的差值当作存款，存款会在将来补偿平摊代价低于实际代价的操作；
将一个操作的平摊代价看作两个部分：实际代价 + 存款；
存款是放在数据结构中特定对象上的；

操作序列的总的平摊代价必须是该序列总的实际代价的一个上界。具体分析，单个操作的存款可以是正数或是负数，但是总的操作的存款不能是负数；
举例说明：
1） 栈操作
对于操作序列，设计3个操作的平摊代价如下
PUSH：2 （实际代价为1， 存款1）
POP：0 （实际代价为1， 存款为-1）
MULTIPOP：0 （实际代价是变量k， 存款为-k）
上述三个操作的平摊代价都是O(1)；
将一个盘子压入到栈中， 支付2元，其中一元支付压入操作的代价， 另外一元是存款，暂存在栈数据结构中，用于支付未来弹出盘子的代价；
因此， 对于n次PUSH， POP, MULTIPOP 操作，总的平摊代价就是其总的实际代价的一个上界。总的平摊代价是O(n)，因此实际代价是O(n)；
2） 二进制计数器递增1
计数器的一位从0变为1，平摊代价是2；从1变为0， 平摊代价是0；
0000
0001
0010
0011
从中看出， 每次递增， 最多只有1位被置位，其n次操作的平摊代价是O(2n)，所以单次操作的代价是O(1)；

三、势能方法

记账方法是将存款放在数据结构中特定对象上的，势能方法是将预付的代价表示成一种势能，在需要的时候释放出来， 已支付后面的操作。势能是存放在整个数据结构中的而不是个别对象中；
势能方法的工作过程：


举例说明
1） 栈操作
选择势能函数为栈中对象的个数， 势能是与整个数据结构有关的，所以势能函数的参数一般是数据结构的一个特征；
分操作讨论：
1.1 PUSH操作

1.2 MULTIPOP操作

1.3 POP操作
平摊代价是0

2） 二进制计数器
选择势能函数为计数器中n个位中， 被置位的位的数量；
INCREMENT操作的平摊代价：
一个第i次的INCREMENT操作最多进行1次置位， ti次复位，实际代价是ti+1；
设第(i-1)次操作，置位的数目是b(i-1), 则i次操作， 置位的数目是bi = b(i-1) -ti+1;
平摊代价 = 实际代价 + 势能函数差值。