几种基本的摊还分析方法

1.聚合分析
这种方法用来确定一个n个操作的序列的总代价的上界T(n)。因而每个操作的平均代价为T(n)/n。我们将平均代价作为每个操作的摊还代价，因此所有操作具有相同的摊还代价。
聚集方法的目的
? 分析平摊代价的上界
分析方法
? 分析操作序列中每个操作的代价上界ci
? 求得操作序列的总代价的上界T(n)=c1+c2+…+cn
? 将T(n)平摊到每个操作上得到平摊代价T(n)/n
特点
? 每个操作获得相同的平摊代价
? 较准确地计算T(n)需要一定的技巧

2.会计法
此方法用来分析每个操作的摊还代价。当存在不止一种操作时，美中操作的摊还代价可能是不同的。
–不同类型操作赋予不同的平摊代价
–某些操作在数据结构的特殊对象上“预付”代价
? Accounting方法
– 目的是分析n个操作序列的复杂性上界
– 一个操作序列中有不同类型的操作
– 不同类型的操作的操作代价各不相同
– 于是我们为每种操作分配不同的平摊代价
? 平摊代价可能比实际代价大，也可能比实际代价小
? 如果平摊代价比实际代价高：一部分用于支付实际代价， 多余部分作为Credit附加在数据结构的具体数据对象上
? 当一个操作的平摊代价比实际代价低时： Credit用来补充 支付实际代价
3.势能法
Potential方法
– 目的是分析n个操作系列的复杂性上界
– 在会计方法中，如果操作的平摊代价比实际代价大， 我们将余额与数据结构的数据对象相关联
–Potential方法把余额与整个数据结构关联，所有的这 样的余额之和，构成数据结构的势能
? 如果操作的平摊代价大于操作的实际代价，势能增加
? 如果操作的平摊代价小于操作的实际代价，要用数据 结构的势能来支付实际代价，势能减少