第 6章平 摊分析（ Amortized analysis）.ppt

1、第 6章 平 摊 分 析 （ Amortized analysis）,基本思想,在平摊分析中，执行一系列 数据结构操作所需要时间是 通过对执行的所有操作求平 均而得出的,对一个数据结构 要执行一系列操作：有的代价很高有的代价一般有的代价很低,? 各个操作的代价？,将总的代价平摊到 每个操作上,平 摊 代 价,不涉及概率 不同于平均情况分析,平摊分析的方法,聚集方法会计方法势能方法,聚集分析法-原理,对数据结构共有n个操作 最坏情况下： 操作1： t1 操作2： t2 。 。 。 操作n: tn,T(n)=,平摊代价： T(n)/n,操作序列中的每个操作被赋予相同的代价，不管操作的类型,平摊分析

2、实例1-栈操作,普通栈操作PUSH(S,x)：将对象压入栈SPOP(S)：弹出并返回S的顶端元素 时间代价:两个操作的运行时间都是O(1)我们可把每个操作的代价视为1n个PUSH和POP操作系列的总代价是nn个操作的实际运行时间为(n),平摊分析实例1-栈操作,新的栈操作操作MULTIPOP(S,k)：去掉S的k个顶端对象或当S中包含少于k个对象时弹出整个栈,实现算法输入：栈S，k输出：返回S顶端k个对象MULTIPOP(S,k)1 While not STACK-EMPTY(S) and k0 Do2 POP(S);3 kk-1,实际运行时间与实际执行的POP操作数成线性关系,While循环

3、执行的次数是从栈中弹出的对象数min(s,k),执行一次While循环要调用一次POP,MULTIPOP的总代价即为min(s,k),平摊分析实例1-栈操作,初始为空的栈上的n个栈操作序列的分析 由PUSH、POP和MULTIPOP长为n的栈操作序列,操作1： t1 操作2： t2 。 。 。 操作n: tn,T(n)=?,最坏情况下，每个操作都是:MULTIPOP每个MULTIPOP的代价最坏是？,T(n)=n2,上面的分析太粗糙了！我们从元素进出栈的情况来分析,所以在一个非空栈上调用POP的次数(包括在MULTIPOP内的调用)至多等于PUSH的次数， 即至多为n,T(n)=2n,平摊代价

4、 =T(n)/n =O(1),一个对象在每次被压入栈后至多被弹出一次,！Note: 分析过程没有使用任何的概率！,于是：最坏情况下 这样的一个操作序 列的时间复杂度最 多为O(n),平摊分析实例2-二进计数器,1. 问题定义实现一个由开始向上计数的k位二进计数器。输入：k位二进制变量x，初始值为0。输出：x+1 mod 2k。数据结构：A0k-1作为计数器，存储xx的最低位在A0中，最高位在Ak-1中x =,平摊分析实例2-二进计数器,2. 计数器加1算法输入：A0k-1，存储二进制数x输出：A0k-1，存储二进制数x+1 mod 2k,INCREMENT(A)1 i02 while ilen

5、gthA and Ai=1 Do3 Ai0;4 ii+1;5 If ilengthA Then Ai1,平摊分析实例2-二进计数器,3.初始为零的计数器上n个INCREMENT操作的分析,Counter total N A7 A6 A5 A4 A3 A2 A1 A0 0 0 0 0 0 0 0 0 0 0,Counter total N A7 A6 A5 A4 A3 A2 A1 A0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1,Counter total N A7 A6 A5 A4 A3 A2 A1 A0 0 0 0 0 0 0 0 0 0 00 0 0 0

6、 0 0 0 1 1 2 0 0 0 0 0 0 1 0 3,Counter total N A7 A6 A5 A4 A3 A2 A1 A0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 1 10 0 0 0 0 0 1 0 3 3 0 0 0 0 0 0 1 1 4,Counter total N A7 A6 A5 A4 A3 A2 A1 A0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 1 10 0 0 0 0 0 1 0 30 0 0 0 0 0 1 1 4 4 0 0 0 0 0 1 0 0 7,Counter total N A7 A6 A5

7、 A4 A3 A2 A1 A0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 1 10 0 0 0 0 0 1 0 30 0 0 0 0 0 1 1 40 0 0 0 0 1 0 0 7 5 0 0 0 0 0 1 0 1 86 0 0 0 0 0 1 1 0 107 0 0 0 0 0 1 1 1 11,每次INCREMENT操作的代价与被改变值的位数成线性关系,粗略地讲：每次INCREMENT最多改变k位 共nk,每次操作发生一次变化 共n次,每隔2次发生一次改变 共n/2,每隔4次发生一次改变 共n/4,每隔8次发生一次改变 共n/8,总共发生的改变为： n/2i (

8、i=0,2,log2n 2n,会计方法-基本原理,一个操作序列中有不同类型的操作 不同类型的操作的操作代价各不相同 于是我们为每种操作分配不同的平摊代价,平摊代价可能比实际代价大，也可能比实际代价小,操作被执行时，支付了平摊代价,如果平摊代价比实际代价高：平摊代价的一部分用于支付实际代价，多余部分作为存款附加在数据结构的具体数据对象上,如果平摊代价比实际代价低：平摊代价及数据对象上的存款用来支付实际代价,只要我们能保证：在任何操作序列上，存款的总额非负,则所有操作平摊代价的总和就是实际代价总和的上界,平摊代价的总和 ？实际代价的总和,于是：我们在各种操作上定义平 摊代价使得任意操作序列上存款

9、总量是非负的，将操作序列上平 摊代价求和即可得到这个操作序 列的复杂度上界,会计方法实例 1 栈操作,1. 各栈操作的实际代价：PUSH 1,POP 1,MULTIPOP min(k,s),2. 各栈操作的平摊代价： PUSH 2,POP 0,MULTIPOP 0,会计方法实例 1 栈操作,3. 栈操作序列代价分析,只要我们的操作序列市合理的，则可以保证 存款总和非负,于是所有操作的平摊代价总和就是操作 序列的是及代价总和的上界 =？,长度为n的操作序列中: PUSH操作的个数=n 于是： 平摊代价的总和=2n,会计方法实例 2 -二进计数器,1. 计数器加1算法输入：A0k-1，存储二进制数

10、x输出：A0k-1，存储二进制数x+1 mod 2kINCREMENT(A) 1 i0 2 while ilengthA and Ai=1 Do 3 Ai0; 4 ii+1; 5 If ilengthA 6 Then Ai1,会计方法实例 2 -二进计数器,初始为零的计数器上n个INCREMENT操作的分析,显然：这个操作序列的代价与0-1或者 1-0翻转发生的次数成正比,定义：0-1翻转的平摊代价为 21-0翻转的平摊代价为0,任何操作序列，存款余额是计数器中1的个数，非负因此，所有的翻转操作的平摊代价的和是这个操作序列代价的上界,对每个INCREMENT操作 ：找到左起的第一个0，将他翻转

11、成1支付平摊代价2将这个0之前的所有1翻转成0支付平摊代价0对这个INCREMENT操作而言，支付了凭摊代价2,对于长度为n的INCREMENT操作序列：支付的评摊代价的总和为2n因此，这样一个操作序列的复杂度上界为2n,任何操作序列，存款余额是计数器中1的个数，非负因此，所有的翻转操作的平摊代价的和是这个操作序列代价的上界,势能分析基本原理,在会计方法中，如果操作的平摊代价比实际代价大，我们将余额与具体的数据对象关联 如果我们将这些余额都与整个数据结构关联，所有的这样的余额之和，构成数据结构的势能 如果操作的平摊代价大于操作的实际代价-势能增加 如果操作的平摊代价小于操作的实际代价，要用数据

12、结构的势能来支付实际代价-势能减少,势能分析基本原理,势能的定义： 对一个初始数据结构D0执行n个操作 对操作i:实际代价Ci, 将数据结构Di-1 变为Di 势函数将每个数据结构Di映射为一个实数(Di) 平摊代价ci定义为：cici + (Di)-(Di-1),势能分析基本原理,n个操作的总的平摊代价为：,于是势函数满足(Dn)(D0)，则总的 平摊代价就是总的实际代价的一个上界,在实践中，我们定义(D0)为0，然后再证明对所有i有(Di)0,平摊代价依赖于所选择的势函数。不同的势函数可能会产生不同的平摊代价，但它们都是实际代价的上界,势能方法实例1 栈操作,(D)=栈D中对象的个数初始栈

13、D0为，(D0)=0因为栈中的对象数始终非负，第i个超作之后的栈DI满足(Di)0=(D0) 于是： 以表示的n个操作的平摊代价的总和就表示了实际代价的一个上界,势能方法实例1 栈操作,作用于包含s个对象的栈上的栈操作的平摊代价,如果第i个操作是个PUSH操作实际代价：ci=1势差：(Di) (Di-1)=(s+1) s=1，平摊代价：ci =ci+(Di)(Di-1)=1+1=2,如果第i个操作是MULTIPOP(S, k)且弹 出了k=min(k,s)个对象实际代价：ci=k势差：为(Di) (Di-1)= k平摊代价：ci=ci+(Di)(Di-1)=k k=0,如果第i个操作是POP实

14、际代价：ci=1势差：(Di) (Di-1)= 1平摊代价：ci=ci+(Di)(Di-1)=11=0,平摊分析 ：,每个栈操作的平摊代价都是O(1),n个操作序列的总平摊代价就是O(n),因为(Di)(D0)， n个操作的总平摊代 价即为总的实际代价的一个上界，即n 个操作的最坏情况代价为O(n),势能方法实例 2 -二进计数器,(D)=计数器D中1的个数 计数器初始状态D0中1的个数为0，(D0)=0 因为栈中的对象数始终非负，第i个超作之后的栈Di满 足(Di)0=(D0) 于是：n个操作的平摊代价的总和就表示了实际代价的一个上界,势能方法实例 2 -二进计数器,第i次INCREMENT

15、操作的平摊代价,设第i次INCREMENT操作对ti个位进行了置0, 至多将一位置1该操作的实际代价：ci=ti+1在第i次操作后计数器中1的个数为bi bi-1- t i+1势差：(Di)-(Di-1)(bi-1- t i+1)-bi-1=1- t i，平摊代价：ci = ci+(Di)-(Di-1)( t i+1)+(1- t i)=2,计数器初始状态为0时的平摊分析 ：,每个栈操作的平摊代价都是O(1),n个操作序列的总平摊代价就是O(n),因为(Di)(D0)， n个操作的总平摊代 价即为总的实际代价的一个上界，即n 个操作的最坏情况代价为O(n),势能方法实例 2 -二进计数器,开始

16、时不为零的计数器上n个INCREMENT操作的分析 设：开始时有b0个1 0b0 在n次INCREMENT操作之后有bn个1,因为(D0)=b0，(Dn)=bn，n次INCREMENT操 作的总的实际代价为：,如果我们执行了至少n=(k)次INCREMENT操作， 则无论计数器中包含什么样的初始值，总的实际 代价都是O(n),正是势能法，给我们这样的分析带来了方便!,动态表,动态表的概念 本节的目的： 研究表的动态扩张和收缩的问题 利用平摊分析证明插入和删除操作的平摊代价为O(1)，即使当它们引起了表的扩张和收缩时具有较大的实际代价 研究如何保证一动态表中未用的空间始终不超过整个空间的一部分,

17、动态表-基本术语,动态表支持的操作TABLE-INSERT：将某一元素插入表中TABLE-DELETE：将一个元素从表中删除数据结构:用一个（一组）数组来实现动态表 非空表T的装载因子(T)= T存储的对象数/表大小,空表的大小为0，装载因子为1,如果动态表的装载因子以一个常数为下界，则表中未使用的空间就始终不会超过整个空间的一个常数部分,设T表示一个表: tableT是一个指向表示表的存储块的指针 numT包含了表中的项数 sizeT是T的大小 开始时，numT=sizeT=0,动态表-表的扩张,向表中插入一个数组元素时，分配一个包含比原表更多的槽的新表，再将原表中的各项复制到新表中去 一种

18、常用的启发式技术是分配一个比原表大一倍的新表，如果只对表执行插入操作，则表的装载因子总是至少为1/2，这样浪费掉的空间就始终不会超过表总空间的一半,算法：TABLEINSERT(T, x) 1 If sizeT=0 2 Then allocate tableT with 1 slot; 3 sizeT1; 4 If numT=sizeT Then 5 allocate new table with 2sizeT slots; 6 insert all items in tableT into new-table; 7 free tableT; 8 tableTnew-table; 9 size

19、T2sizeT; 10 Insert x into tableT; 11 numTnumT+1,复杂插入操作,基本插入操作,开销为常数,开销由sizeT决定,动态表-表的扩张,初始为空的表上n次TABLE-INSERT操作的代价分析-粗略分析,算法：TABLEINSERT(T, x) 1 If sizeT=0 2 Then allocate tableT with 1 slot; 3 sizeT1; 4 If numT=sizeT Then 5 allocate new table with 2sizeT slots; 6 insert all items in tableT into new

20、-table; 7 free tableT; 8 tableTnew-table; 9 sizeT2sizeT; 10 Insert x into tableT; 11 numTnumT+1,第i次操作的代价Ci:,如果i=1,ci=1,如果表有空间,ci=1,如果表是满的,ci=i,如果以共有n次操作： 最坏情况下,每次进行n次操作,总的代价上界为n2,这个界不精确，因为执行n次TABLEINSERT操作的过程中并不常常包括扩张表的代价。仅当i-1为2地整数幂时第i次操作才会引起一次表地扩张,动态表-表的扩张,初始为空的表上n次TABLE-INSERT操作的代价分析-聚集分析,算法：TABL

21、EINSERT(T, x) 1 If sizeT=0 2 Then allocate tableT with 1 slot; 3 sizeT1; 4 If numT=sizeT Then 5 allocate new table with 2sizeT slots; 6 insert all items in tableT into new-table; 7 free tableT; 8 tableTnew-table; 9 sizeT2sizeT; 10 Insert x into tableT; 11 numTnumT+1,第i次操作的代价Ci:,如果i=2m,ci=i,否则,ci=1,n

22、次TABLEINSERT操作 的总代价为：,每一操作的平摊代价为 3n/n=3,动态表-表的扩张,初始为空的表上n次TABLE-INSERT操作的代价分析-会计法分析,算法：TABLEINSERT(T, x) 1 If sizeT=0 2 Then allocate tableT with 1 slot; 3 sizeT1; 4 If numT=sizeT Then 5 allocate new table with 2sizeT slots; 6 insert all items in tableT into new-table; 7 free tableT; 8 tableTnew-tab

23、le; 9 sizeT2sizeT; 10 Insert x into tableT; 11 numTnumT+1,每次执行TABLEINSERT平摊代价为3,1支付第11步中的基本插入操作的实际代价,1作为自身的存款,1存入表中第一个没有存款的数据上,当发生表的扩张时，数据的复制的代价由 数据上的存款来支付,任何时候，存款总和非负,初始为空的表上n次TABLE-INSERT操作的 平摊代价总和为3n,动态表-表的扩张,初始为空的表上n次TABLE-INSERT操作的代价分析-势能法分析,算法：TABLEINSERT(T, x) 1 If sizeT=0 2 Then allocate tab

24、leT with 1 slot; 3 sizeT1; 4 If numT=sizeT Then 5 allocate new table with 2sizeT slots; 6 insert all items in tableT into new-table; 7 free tableT; 8 tableTnew-table; 9 sizeT2sizeT; 10 Insert x into tableT; 11 numTnumT+1,?势怎么定义 才能使得表满发生扩张时 势能能支付扩张的代价,如果势能函数满足： 1 刚扩充完，(T)=0 2 表满时 (T)=size(T),(T)=2*nu

25、mT-sizeT,势能函数满足要求并且： 由于numTsizeT/2，(T)0 n次TABLEINSERT操作的总的平摊代价 就是总的实际代价的一个上界,第i次操作的平摊代价：,如果发生扩张：,ci= 3,否则,ci= 3,初始为空的表上n次TABLE-INSERT操作的 平摊代价总和为3n,动态表-表的扩张和收缩,表的扩张 表的收缩,理想情况下，我们希望表满足：,表具有一定的丰满度,表的操作序列的复杂度是线性的,动态表-表的扩张和收缩,表的收缩策略,根据表的扩张策略，很自然地想到下满的收缩策略,但表的装载因子小于1/2时，收缩表委员表的一半,n是2的方幂，下面的一个长度为n的操作序列： 前n

26、/2个操作是插入 ，后跟I D D I I D D I I,每次扩张和收缩的代价为O(n)，共有O(n)扩张或收缩,总代价为O(n2)，而每一次操作的平摊代价为O(n),每个操作的平摊代价太高,方法：当向满的表中插入一项时，还是将表扩大一倍,但当删除一项而引起表不足1/4满时，我们就将表缩小 为原来的一半,这样，扩张和收缩过程都使得表的装载因子变为1/2 但是，表的装载因子的下界是1/4,动态表-表的扩张和收缩,由n个TABLEINSERT和TABLE-DELETE操作构成的序列的代价的分析-势能法,操作序列过程中的表T,有：势总是非负的 ；这样才能保证一列操作的总平摊代价即为其实际代价的一个

27、上界,表的扩张和收缩过程要消耗大量的势,这样我们的是满足： 1 num(T)=size(T)/2时，势最小 2 当num(T)减小时，势增加直到收缩 3 当num(T)增加时，势增加直到扩充,空表的势为0，且势总是非负的。这样，以表 示的一列操作的总平摊代价即为其实际代价的 一个上界,势函数的某些性质 : 当装载因子为1/2时，势为0。 当装载因子为1时，有numT=sizeT，这就意 味着(T)=numT。这样当因插入一项而引起一 次扩张时，就可用势来支付其代价。 当装载因子为1/4时，sizeT=4numT。它意味 着(T)=numT。因而当删除某项引起一次收缩 时就可用势来支付其代价。,第i次操作是TABLEINSERT ：未扩张,ci 3,第i次操作是TABLEINSERT ：扩张,ci 3,第i次操作是TABLEDELETE ：未收缩,ci3,第i次操作是TABLEDELETE ：收缩,ci3,所以作用于一动态表上的n个操作的实际时间为O(n),summary,