2 算法分析—平摊分析【荐】.pdfVIP

平摊分析 Amortized Analysis 陈卫东 chenwd@scnu.edu.cn 华南师范大学计算机学院 2009-9-23 适用范围 平摊分析（Amortized Analysis ）适合： 需要对一组操作的时间复杂度进行分析 这组操作中每种操作所花费的时间差别可能较大 每种操作的次数可能不定 实际上费时间的操作次数可能不太多 如果都以最费时间的操作来能量，显然得到的是一 个不太精确的时间上界。但若采用平摊方法来分析，则 往往可以得到一个更精确的时间界。 W.D.Chen South China Normal University 1 常用方法 常用的平摊分析方法有三种： 聚集方法 会计方法 势能方法 W.D.Chen South China Normal University 2 聚集方法 要点： 全局考虑时间复杂度 把n条操作的耗费分为几类 分别计算每一类耗费的总和 然后再把各类耗费总加起来 W.D.Chen South China Normal University 3 聚集方法 [例1] 考虑由下列三种操作组成的长度为n 的操作序列： 栈操作：Push(x,S), Pop(S) 新栈操作MultiPop(S, k) ：若S中元素个数≥k, 则弹 出k个元素, 若小于k, 则弹出全部元素。 简单分析：Push(x,S), Pop(S), 均只需要O(1)时间。在最坏情况 下，MultiPop(S,k)执行一次需要O(n)时间。执行n个操作后最坏情 况时间复杂度是O(n2 2 ) 。O(n )是上界，但不紧。 如何分析可得更精确的时间界？ ——用平摊分析可得复杂度为Θ(n) W.D.Chen South China Normal University 4 聚集方法 [例2] 一程序从0开始用增1方法逐个生成长度为k 的二进制数。 问：从0开始生成n个数(0 n ≤2k-1) 在最坏情况下需要多少 次位操作（即从0变1及从1变0 ）？ 由当前数生成下一个数的算法：从最低位开始，如果当 前检测位为1，则将其改为0 ，直到碰见第一个0将其改为1时 一个数的生成工作完成。 简单分析：在最坏情况下，生成1个数时k位都要改，即需要O(k)时 间，故生成n个数需O(n*k)时间。这是一个上界，但不紧。 如何分析才能得到更为精确的时间界？ ——用平摊分析可得到：进位操作次数≤2n, 即复杂度Θ(n) W.D.Chen South China Normal University 5 会计方法 要点： 确定每个操作的平摊代价。当有一种以上的操作 时，每种操作都可有一个不同的平摊代价。这种方法对 操作序列中的某些操作先“多记帐” ，将多记的部分作为 对数据结构中的特定对象上预付的存款存起来。在该序 列中稍后要用到这些存款以补偿那些对它们记的“帐”少 于其实际代价的操作。 W.D.Chen South China Normal University 6 势能方法 要点： 这种方法与会计方法的相似之处在于要确定每个操 作的代价，且先对某些操作多记帐以补偿以后的不足记 帐。这种方法将存数作为数据结构的“势能”来维护，而 不是将存款与数据结