第6章平摊分析Amortizedanalysis.ppt

《第6章平摊分析Amortizedanalysis.ppt》由会员分享，可在线阅读，更多相关《第6章平摊分析Amortizedanalysis.ppt（34页珍藏版）》请在三一办公上搜索。

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

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

3、n(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,平摊代价=T(n)/n=O(1),一个对象在每次被压入栈后至多被

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

5、;5 If ilengthA Then Ai1,平摊分析实例2-二进计数器,3.初始为零的计数器上n个INCREMENT操作的分析,Counter totalN A7 A6 A5 A4 A3 A2 A1 A0 0 0 0 0 0 0 0 0 0 0,Counter totalN A7 A6 A5 A4 A3 A2 A1 A0 0 0 0 0 0 0 0 0 0 01 0 0 0 0 0 0 0 1 1,Counter totalN A7 A6 A5 A4 A3 A2 A1 A0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 12 0 0 0 0 0 0 1 0 3,C

6、ounter totalN A7 A6 A5 A4 A3 A2 A1 A0 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 33 0 0 0 0 0 0 1 1 4,Counter totalN A7 A6 A5 A4 A3 A2 A1 A0 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 44 0 0 0 0 0 1 0 0 7,Counter totalN A7 A6 A5 A4 A3 A2 A1 A0 0 0 0 0 0 0 0 0

7、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 75 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,每次INCREMENT操作的代价与被改变值的位数成线性关系,粗略地讲：每次INCREMENT最多改变k位 共nk,每次操作发生一次变化共n次,每隔2次发生一次改变共n/2,每隔4次发生一次改变共n/4,每隔8次发生一次改变共n/8,总共发生的改变为：n/2i(i=0,2,log2n2n,会计方法-基本原理,一个操作序列中有不

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

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算法 输入：A0.k-1，存储二进制数x 输出：A0.k-1，存储二进制数x+1 mod 2kINCREMENT(A)1 i02 while

10、 ilengthA and Ai=1 Do3 Ai0;4 ii+1;5 If ilengthA6 Then Ai1,会计方法实例 2-二进计数器,初始为零的计数器上n个INCREMENT操作的分析,显然：这个操作序列的代价与0-1或者1-0翻转发生的次数成正比,定义：0-1翻转的平摊代价为 21-0翻转的平摊代价为0,任何操作序列，存款余额是计数器中1的个数，非负因此，所有的翻转操作的平摊代价的和是这个操作序列代价的上界,对每个INCREMENT操作：找到左起的第一个0，将他翻转成1支付平摊代价2将这个0之前的所有1翻转成0支付平摊代价0对这个INCREMENT操作而言，支付了凭摊代价2,对于

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

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

13、就表示了实际代价的一个上界,势能方法实例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 实际代价：ci=1 势差：(Di)(Di-1)=1 平摊代价：ci=ci+(Di)(Di-1)=11=0,平摊分析：,每个栈操作的平摊代价

14、都是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操作的平摊代价,设第i次INCREMENT操作对ti个位进行了置0,至多将一位置1 该操作的实际代价：ci=ti+1 在第i次操作后计数器中1的个数为bi

15、 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-二进计数器,开始时不为零的计数器上n个INCREMENT操作的分析 设：开始时有b0个1 0b0 在n次INCREMENT操作之后有bn个1,因为(D0)=b0，(Dn)=bn，n次INCR

16、EMENT操作的总的实际代价为：,如果我们执行了至少n=(k)次INCREMENT操作，则无论计数器中包含什么样的初始值，总的实际代价都是O(n),正是势能法，给我们这样的分析带来了方便!,动态表,动态表的概念本节的目的：研究表的动态扩张和收缩的问题利用平摊分析证明插入和删除操作的平摊代价为O(1)，即使当它们引起了表的扩张和收缩时具有较大的实际代价研究如何保证一动态表中未用的空间始终不超过整个空间的一部分,动态表-基本术语,动态表支持的操作 TABLE-INSERT：将某一元素插入表中 TABLE-DELETE：将一个元素从表中删除 数据结构:用一个（一组）数组来实现动态表非空表T的装载因子

17、(T)=T存储的对象数/表大小,空表的大小为0，装载因子为1,如果动态表的装载因子以一个常数为下界，则表中未使用的空间就始终不会超过整个空间的一个常数部分,设T表示一个表:tableT是一个指向表示表的存储块的指针numT包含了表中的项数sizeT是T的大小开始时，numT=sizeT=0,动态表-表的扩张,向表中插入一个数组元素时，分配一个包含比原表更多的槽的新表，再将原表中的各项复制到新表中去一种常用的启发式技术是分配一个比原表大一倍的新表，如果只对表执行插入操作，则表的装载因子总是至少为1/2，这样浪费掉的空间就始终不会超过表总空间的一半,算法：TABLEINSERT(T,x)1 If

18、sizeT=02 Then allocate tableT with 1 slot;3 sizeT1;4 If numT=sizeT Then5 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,复杂插入操作,基本插入操作,开销为常数,开销由sizeT决定,动态表-表的扩张,初始为空的表上n次TABLE-INSERT操

19、作的代价分析-粗略分析,算法：TABLEINSERT(T,x)1 If sizeT=02 Then allocate tableT with 1 slot;3 sizeT1;4 If numT=sizeT Then5 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=1,ci=1,如果表

20、有空间,ci=1,如果表是满的,ci=i,如果以共有n次操作：最坏情况下,每次进行n次操作,总的代价上界为n2,这个界不精确，因为执行n次TABLEINSERT操作的过程中并不常常包括扩张表的代价。仅当i-1为2地整数幂时第i次操作才会引起一次表地扩张,动态表-表的扩张,初始为空的表上n次TABLE-INSERT操作的代价分析-聚集分析,算法：TABLEINSERT(T,x)1 If sizeT=02 Then allocate tableT with 1 slot;3 sizeT1;4 If numT=sizeT Then5 allocate new table with 2sizeT sl

21、ots;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次TABLEINSERT操作的总代价为：,每一操作的平摊代价为3n/n=3,动态表-表的扩张,初始为空的表上n次TABLE-INSERT操作的代价分析-会计法分析,算法：TABLEINSERT(T,x)1 If sizeT=02 Then allocate tableT

22、 with 1 slot;3 sizeT1;4 If numT=sizeT Then5 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,每次执行TABLEINSERT平摊代价为3,1支付第11步中的基本插入操作的实际代价,1作为自身的存款,1存入表中第一个没有存款的数据上,当发生表的扩张时，数据的复制的代价由数据上的

23、存款来支付,任何时候，存款总和非负,初始为空的表上n次TABLE-INSERT操作的平摊代价总和为3n,动态表-表的扩张,初始为空的表上n次TABLE-INSERT操作的代价分析-势能法分析,算法：TABLEINSERT(T,x)1 If sizeT=02 Then allocate tableT with 1 slot;3 sizeT1;4 If numT=sizeT Then5 allocate new table with 2sizeT slots;6 insert all items in tableT into new-table;7 free tableT;8 tableTnew-

24、table;9 sizeT2sizeT;10 Insert x into tableT;11 numTnumT+1,?势怎么定义才能使得表满发生扩张时势能能支付扩张的代价,如果势能函数满足：1 刚扩充完，(T)=0 2 表满时(T)=size(T),(T)=2*numT-sizeT,势能函数满足要求并且：由于numTsizeT/2，(T)0 n次TABLEINSERT操作的总的平摊代价就是总的实际代价的一个上界,第i次操作的平摊代价：,如果发生扩张：,ci=3,否则,ci=3,初始为空的表上n次TABLE-INSERT操作的平摊代价总和为3n,动态表-表的扩张和收缩,表的扩张表的收缩,理想情况

25、下，我们希望表满足：,表具有一定的丰满度,表的操作序列的复杂度是线性的,动态表-表的扩张和收缩,表的收缩策略,根据表的扩张策略，很自然地想到下满的收缩策略,但表的装载因子小于1/2时，收缩表委员表的一半,n是2的方幂，下面的一个长度为n的操作序列：前n/2个操作是插入，后跟I D D I I D D I I,每次扩张和收缩的代价为O(n)，共有O(n)扩张或收缩,总代价为O(n2)，而每一次操作的平摊代价为O(n),每个操作的平摊代价太高,方法：当向满的表中插入一项时，还是将表扩大一倍,但当删除一项而引起表不足1/4满时，我们就将表缩小为原来的一半,这样，扩张和收缩过程都使得表的装载因子变为1

26、/2但是，表的装载因子的下界是1/4,动态表-表的扩张和收缩,由n个TABLEINSERT和TABLE-DELETE操作构成的序列的代价的分析-势能法,操作序列过程中的表T,有：势总是非负的；这样才能保证一列操作的总平摊代价即为其实际代价的一个上界,表的扩张和收缩过程要消耗大量的势,这样我们的是满足：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,