《算法导论chapter 17》由会员分享，可在线阅读，更多相关《算法导论chapter 17（55页珍藏版）》请在金锄头文库上搜索。
1、Chapter 17. 平摊分析,1,Ch.17 平摊分析,1985年，Robert提出 在平摊分析中，在一数据结构上执行一个操作序列所需时间是所有操作执行时间的平均。它常用来证明在一个操作序列中，即使某个操作具有较大代价，当通过对所有操作求平均后，一个操作的平摊代价仍很小,2,Ch.17 平摊分析,与平均情况分析的区别平摊分析不涉及到概率，保证其平摊性能是每个操作在最坏情况下具有的平均性能 三种平摊分析技术 合计法、聚集方法（aggregate） 记账法、会计法（accounting） 势能法（potential）,3,Ch.17 平摊分析,合计法 简单，常用：先求出合计，然后摊薄先求出操作
2、序列里所有n个操作的总代价上界T(n)，每个操作的平摊代价T(n)/n 记账法 对操作序列中的各操作收费，以支付操作的实际代价 数据结构收费单位 操 作付费单位,4,Ch.17 平摊分析,记账法 先确定操作序列中各种操作的平摊代价（费用），对不同的操作收费可以不同 对有的操作超额收费：即该操作实际成本低于该收费，余款作为“预付存款”存储在数据结构某些特殊对象上 对有的操作收费不足：即该操作实际成本大于此收费，不足部分由特殊对象上的存款支付,5,Ch.17 平摊分析,势能法 与记账法类似之处是也须先确定每个操作的平摊成本（收费），对某些操作预先超额收费以补偿后续收费不足的操作 不同之处是：存款是
3、作为整个数据结构的“势能”加以维护，而不是将存款与数据结构中某些个体对象联系起来注意：为操作指定的费用只是为了分析之用，不应出现在代码中,6,Ch.17 平摊分析,平摊分析特点 1）它是一种分析的方法，适用于分析一个彼此相关的操作序列其分析方法不是孤立地分析每个操作的时间界限，而是将整个操作序列作为一个整体考虑，利用各操作彼此的关系求整个操作序列的时间界限，然后摊薄得到各操作的平摊代价 2）操作序列的总代价是序列长度的函数，而不是输入量规模的函数,7,Ch.17 平摊分析,平摊分析特点 3）不仅是分析方法，也是设计算法和数据结构的一种思维方法因为设计算法与分析时间性能紧密相关，所以通过平摊分析
4、可优化算法设计，加深对算法所操作的数据结构特性的认识，从而设计出时空性能更优的数据结构,8,17.1 合计法,该方法中，对所有的n，具有n个操作的序列在最坏情况下的总时间为T(n)，因此，最坏情况下每个操作的平摊代价为T(n)/n 注意 n个操作可以是同一个操作，亦可以是不同的操作 与后两种方法不同的是：各操作的平摊代价相同,9,17.1 合计法,1、栈操作（不同种类） 数据结构：栈S，初值为空 操作 Push(S, x): O(1) Pop(S): O(1) MultiPop(S, k): O(min(|S|, K)弹出min(|S|, K)个对象,10,17.1 合计法,栈上操作序列的时间
5、分析 通常分析方法得不到紧确界设有n个Push，Pop和Multipop操作构成的序列作用在初值为空的栈S上。一次Multipop的最坏时间为O(n)，因为|S| n，K=O(n)；最坏情况下可能有O(n)个Multipop。因此，该序列最坏时间为O(n2),11,17.1 合计法,栈上操作序列的时间分析（续） 合计法可得紧确界因为一个对象入栈后至多被弹出一次，所以在非空栈上调用Pop的次数（包括Multipop中调用的Pop）至多为Push的次数因此，当S初值为空时，Push次数至多为O(n)，而Pop次数至多为O(n)因为每个Pop和Push的实际代价均为O(1)，所以对任意整数n，操作序
6、列长度为n时，总时间T(n)=O(n)，三个操作的平摊代价均为O(n)/n=O(1) 注意：没有使用概率分析,12,17.1 合计法,2、二进制计算器（同一类操作） 数据结构设A0k-1数组作为二进制计数器，初值为0，Ai=0, 0 i k-1。A中存储二进制数x：操作：将二进制计数器A的值加1（模2k，0x 2k-1）,13,14,15,17.1 合计法,执行过程： 初值为0，做n次增量操作,16,方框部分表示为取得下一个值而将发生的翻转，每次增1操作代价为每次翻转的位数。总成本不超过增量操作执行的总次数的2倍。,17.1 合计法,时间分析 通常分析最坏时，Increment改变值的位数为(
7、K) (Ai=1, 0ik-1),n个增量作用在初值为0的计数器上，总代价为(nK) 合计法分析n次增量操作中，并非每次所有位都发生变化，上表告诉我们，无论n值为何，其总翻转位数lgn时 n的二进制表示最多有lgn+1位 Ai在n次增量操作中，始终不变(高位不翻转)。于是，n次操作总的翻转次数为：,18,17.1 合计法,即： 操作序列总代价(在最坏情况下)为O(n)每次操作的平摊成本为O(n)/n=O(1),19,17.2 记账法,费用分配（平摊代价）为不同的操作分配不同的费用，每一操作分配到的费用称为该操作的平摊代价，它可视作为数据结构对该操作预收的费用（或理解为是该操作对数据结构预付的费
8、用）,20,17.2 记账法,超额收费(overcharge)(平摊代价实际成本)当一个操作的平摊代价大于其实际成本时，数据结构对该操作预收的费用过多，其超额部分作为存款存储在数据结构的某个特定对象上 收费不足(undercharge)(平摊代价0：(D0)=b00 设(Dn)=bn0b0,bnk(k为计数器的长度)，改写(17.3)可得,38,17.3 势能法,注意：在上式中i 2, 与b0是否为0无关，故可利用它直接分析总的实际成本。这里要求k=O(n)，或执行Increment操作至少k次(n(k)，即可保证：无论计数器的初值为何，总的实际代价都是O(n),39,Exercise,Ex17.3-1 Ex17.3-3,40,17.4. 动态表,一个存储管理系统，须能根据实际需要来动态地分配与释放存储块 表扩张：表满时插入x引起扩张 申请更大的表 原表copy到新表 释放原表 插入x,
