06算法设计与分析---摊还分析

1 .东南大学计算机学院 方效林 摊还分析

2 .本章内容 聚合分析 核算方法 势能方法 2

3 .摊还分析 对一个数据结构执行 n 个操作 有些操作代价高 有些操作代价低 有些操作代价中等 将所有操作的代价平摊到每个操作上 不涉及概率 不同于平均情况 3

4 .聚合分析 栈的三种操作 对一个空栈，执行由 n 个 PUSH, POP, MULTIPOP 组成的操作，代价是多少？ 4 操作 代价 PUSH 1 POP 1 MULTIPOP( s,k ) min(s, k) 由于 multipop ( s,n ) 的代价最坏为 n ，因此 n 个操作最坏为 O(n 2 )? 一个元素要么入栈 ，要么出栈， 一个空栈中， n 个 PUSH, POP, MULTIPOP 组成的 操作最多与 PUSH 次数相当 即最多对 n 个元素操作，因此为 O(n)

5 .聚合分析 二进制计数器 (k 位 ) 初始值为 0 ，每次加 1 ，累加 n 次， 5 n A[7] A[6] A[5] A[4] A[3] A[2] A[1 ] A[0] 总代价 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 3 0 0 0 0 0 0 1 1 4 0 0 0 0 0 1 0 0 7 5 0 0 0 0 0 1 0 1 8 6 0 0 0 0 0 1 1 0 10 7 0 0 0 0 0 1 1 1 11 最坏情况代价为 k ， n 次累加代价是否为 O( kn )?

6 .聚合分析 二进制计数器 (k 位 ) 初始值为 0 ，每次加 1 ，累加 n 次， 6 n A[7] A[6] A[5] A[4] A[3] A[2] A[1 ] A[0] 总代价 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 3 0 0 0 0 0 0 1 1 4 0 0 0 0 0 1 0 0 7 5 0 0 0 0 0 1 0 1 8 6 0 0 0 0 0 1 1 0 10 7 0 0 0 0 0 1 1 1 11 第 0 位翻转，有 n 次 第 1 位翻转，有 n/2 次 第 2 位翻转，有 n/2 2 次 总共 因此为 O(n)  

7 .核算方法 栈的三种操作 对一个空栈，执行由 n 个 PUSH, POP, MULTIPOP 组成的操作，代价是多少？ 7 操作 代价 PUSH 1 POP 1 MULTIPOP( s,k ) min(s, k) 一个元素只有入栈后， 才能出栈，将代价全部 放到 PUSH 操作上 ( 预支付 将来出栈的代价 ) ， 出栈操作代价为 0 ， 因此 n 个操作代价为 O(n) 操作 代价 PUSH 2 POP 0 MULTIPOP( s,k ) 0

8 .核算方法 二进制计数器 (k 位 ) 初始值为 0 ，每次加 1 ，累加 n 次， 8 n A[7] A[6] A[5] A[4] A[3] A[2] A[1 ] A[0] 总代价 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 3 0 0 0 0 0 0 1 1 4 0 0 0 0 0 1 0 0 7 5 0 0 0 0 0 1 0 1 8 6 0 0 0 0 0 1 1 0 10 7 0 0 0 0 0 1 1 1 11 置位代价为 2( 预付将来复位代价 ) 复位代价为 0 n 次累加代价 O(2n)?

9 .势能 方法 数据结构 初始状态 ， 其势 执行第 个操作的状态 ，其势 第 个 操作的摊还 代价 ，真实代价 总摊还代价   9    

10 .势能 方法 栈的三种操作 PUSH, POP, MULTIPOP( s,k ) 对一个空栈，执行 n 个操作，代价是多少？ 定义势为栈中元素个数，则第 个操作 若是 PUSH ，势差 若是 POP ， 势差 若是 MULTIPOP ， 势差 摊 还代价 每种都是 O(1) ，总代价 O(n)   10 操作 摊还代价 PUSH 2 POP 0 MULTIPOP( s,k ) 0

11 .势能方法 二进制计数器 (k 位 ) 初始值为 0 ，每次加 1 ，累加 n 次， n A[7] A[6] A[5] A[4] A[3] A[2] A[1 ] A[0] 势 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 2 0 0 0 0 0 1 0 0 0 5 0 0 0 0 0 1 0 1 1 6 0 0 0 0 0 1 1 0 0 7 0 0 0 0 0 1 1 1 3

12 .势能方法 二进制计数器 (k 位 ) 初始值为 0 ，每次加 1 ，累加 n 次， 定义势 为计数器中 1 的个数 假设第 次累加要对 个位复位，则代价 若结果 k 位均为 0 ( 即前一次 k 位均为 1) ，则势差 否则，势差 无论哪种情况，摊 还代价   12 复位 位，置位 1 位