第13次课

平摊分析

合计法分析

1.栈操作的例子

因为三个操作不是相互独立的，一个对象入栈后最多弹出一次

==>在非空栈上完成的pop次数(包括multipop操作)最多为push的次数

又因为初始栈为空，且n个操作中push的次数<=n

==>pop次数<=n

==>n次操作在最坏情况下的总时间<=2n = O(n)

==>每个操作的平摊时间(平均代价)为T(n)/n=O(1)

(在聚集分析中，把每个操作的平摊代价指派为平均代价)

2.二进制计数器

每次INCREMENT操作的代价都与被改变值的位数成线性关系.

最坏情况下，作用于一个初始为零的计数器上的n次INCREMENT操作的时间为O(n).

i从0到lgn, n / 2^i^

习题17.1-1 1-2

记账法分析

1.栈操作的例子

假定1元代表O(1)的工作量；

————————检查核定——————————

入栈核定2元，1元用于支付对象入栈的实际费用，1元作为存款放在该入栈对象的身上。

出栈核定0元。

任何时刻，平摊代价的总和>=实际代价的总和。

————————-检查核定—————————

最坏情况下n个操作均为push操作.==>n个操作的总费用T(n)<=2n=O(n)

==>n个push、pop、multipop操作的平摊时间为O(1)

势能法

第一步：验证势函数是否正确，即证明 Φ(Dn) >= Φ(D0)。

验证后，说明n个操作的总平摊代价即为总的实际代价的一个上界。

1.栈操作的例子

• 定义势函数Φ为栈中对象的个数，开始处理的是空栈D0 ,Φ(Di) >= Φ(D0)

• 然后计算各个操作的平摊代价 = 其实际代价+ 由于该操作所增加的势。

• ==>三种栈操作中每一种的平摊代价都是O(1), 进而总的平摊代价就是O(n),因此个操作的最坏情况代价为O(n)

1.在选择一个势函数时常要做一些平衡，可选用的最佳势函数的选择要拒绝与所需的时间界

2.不同的势函数可能会产生不同的平摊代价

3.3种方法中势函数是应用最广泛的

平摊分析应用-动态表

分析n次插入操作的平摊代价(表满时扩张)，开始时表是空的，size[T]=0

1.传统方法分析

一次操作的最坏情况代价为O(n), n次操作的总的运行时间的上界O(n^2^)

2.合计法分析

n次TABLE-INSERT操作的总代价为c1+c2+…cn <= 未扩张的总代价 + 扩张的总代价 < n + 2n = 3n,

故每一次操作的平摊代价为3

3.记账法分析

通过采用记账法，可以对为什么一次TABLE-INSERT操作的平摊代价会是3有一些认识。

对每一次插入操作收取3元。假设刚刚完成扩张后表的大小为16，那么表中共有8项。

• 随机发生的基本插入的代价为1元

• 另有1元放在刚刚插入的元素上作为存款

• 余下的1元放在已在表中的16/2个项上某一个作为存款

  到该表包含了16个项满时，每一项都有1元钱来支付在表扩张期间的再次插入.

4.势函数法

1. 定义势函数 装填因子>= 1 / 2
2. 验证势函数
3. 平摊分析 分为第i次操作未引起扩张和引起了扩张