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

本章主要讲述摊还分析,其中包括对一个数据结构执行n个操作:有些操作代价高,有些操作代价低,有些操作代价中等;聚合分析;核算方法;势能方法 :二进制计数器(k位),定义势为计数器中 1 的个数,栈的三种操作:PUSH, POP, MULTIPOP(s,k),等
展开查看详情

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 位