《算法设计与分析6.ppt》由会员分享，可在线阅读，更多相关《算法设计与分析6.ppt（27页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、Chapter 6 Amortized Analysis 平摊分析基本思想平摊分析基本思想 在平摊分析中，执行一系列数据结构操作所需要时间是通过对执行的所有操作求平均而得出的。平摊分析可用来证明在一系列操作中，即使单一的操作具有较大的代价，通过对所有操作求平均后，平均代价还是很小的.平摊分析与平均情况分析不同,不牵涉到概率。Chapter 6 Amortized Analysis 平摊分析的方法平摊分析的方法 聚集方法 会计方法 势能方法Chapter 6 Amortized Analysis 6.1 6.1 聚集方法聚集方法6.1.1 6.1.1 聚集方法的原理聚集方法的原理 首先证明n个操
2、作构成的序列在最坏情况下总的时间T(n)。在最坏情况下，每个操作的平均代价就是T(n)/n。*聚集方法为每个操作都赋予相同的平摊代价，即使序列中存在不同类型操作时也一样。*会计方法和势能方法对不同类型操作赋予不 同的平摊代价。Chapter 6 Amortized Analysis 1.1.普通栈操作分析普通栈操作分析 普通栈操作 PUSH(S,x)：将对象压入栈S；POP(S)：弹出并返回S的顶端元素。时间代价 两个操作的运行时间都是O(1)我们可把每个操作的代价视为1 n个PUSH和POP操作系列的总代价是n n个操作的实际运行时间为(n)。Chapter 6 Amortized Anal
3、ysis 新的栈操作新的栈操作操作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.Chapter 6 Amortized Analysis MULTIPOP总代价 设MULTIPOP(S,k)作用于一个包含s个对象的栈上 实际运行时间与实际执行的POP操作数成线性关系 只需按PUSH和POP具有代价1来分析MULTIPOP While循环执行的次数是从栈中弹出的对象数min(
4、s,k)执行一次While循环要调用一次POP MULTIPOP的总代价即为min(s,k)Chapter 6 Amortized Analysis 1.1.初始为空的栈上的初始为空的栈上的n n个栈操作序列的分析个栈操作序列的分析 设PUSH、POP和MULTIPOP构成n个栈操作序列 粗略分析 序列中一次MULTIPOP操作的最坏情况代价为O(n)（因为栈的大小至多为n）任意栈操作的最坏情况时间就是O(n),n个操作的总代价就是O(n2)（MULITPOP操作可能有O(n)个，每个代价为O(n)）虽然这个分析是正确的，O(n2)的结论却不够准确。Chapter 6 Amortized An
5、alysis 精细分析 一个对象在每次被压入栈后至多被弹出一次.所以在一个非空栈上调用POP的次数(包括在MULTIPOP内的调用)至多等于PUSH的次数，即至多为n.对 任 意 的 n值，包 含 n个 PUSH、POP和MULTIPOP操作的序列的总时间为O(n).每个操作的平摊代价为：O(n)/n=O(1)。Chapter 6 Amortized Analysis *我们想再一次强调一下，虽然我们已说明了每个栈操作的平均代价(或平均运行时间)为O(1)，但没有用到任何概率推理。实际上是给出了一列n个操作的最坏情况界O(n)。用n来除这个总代价即可得每个操作得平均代价(或说平摊代价)。Cha
6、pter 6 Amortized Analysis 6.2 6.2 会计方法会计方法6.2.1.2.1 会计方法的原理会计方法的原理首先定义每个操作的平摊代价然后计算总的平摊代价.执行不同的操作需要付出不同的费用.某些操作的费用可能比它们的实际代价多或少执行一个操作需要付出费用称为这个操作的平摊代价.当一个操作的平摊代价超过了它的实际代价时，两者的差值被作为存款赋给数据结构中一些特定的对象.Chapter 6 Amortized Analysis 存款在以后用于补偿那些平摊代价低于其实际代价的操作一个操作的平摊代价可看作为两部分：其实际代价与存款*会计方法不同于聚集方法，不同操作具有不同的平摊
7、代价。*在选择操作的平摊代价时要非常小心。如果我们希望通过对平摊代价的分析说明每次操作具有较小的最坏情况平均代价，则操作序列的总的平摊代价就必须是该序列的总的实际代价的一个上界。Chapter 6 Amortized Analysis 而且，像在聚集方法中一样，这种关系必须对所有的操作序列都成立。这样与该数据结构相联系的存款始终应该是非负的，因为它表示了总的平摊代价超过总的实际代价的部分。如果允许总的存款为负的的话(开始时对某些操作的费用记得过低)，则在某一时刻总的平摊代价就会低于总的实际代价。对到该时刻为止的操作序列来说，总的平摊代价就不会是总的实际代价的一个上界。所以，我们必须始终注意数据
8、结构中的总存款不能是负的。Chapter 6 Amortized Analysis 6.2.2 会计方法实例会计方法实例 1 栈操作栈操作为了说明平摊分析中的会计方法，我们再回过头看看栈的例子。1.各栈操作的实际代价各栈操作的实际代价：PUSH1,POP1,MULTIPOPmin(k,s)其中k为MULTIPOP的一个参数，s为调用该操作时栈的大小。Chapter 6 Amortized Analysis 2.各栈操作的平摊代价各栈操作的平摊代价：PUSH2,POP0,MULTIPOP0,*MULTIPOP的平摊代价是个常数0，而它的实际代价却是个变量。Chapter 6 Amortized
9、Analysis 3.栈操作序列代价分析栈操作序列代价分析假设我们用1元钱来表示代价的单位开始时栈是空的。栈数据结构与在餐馆中一堆迭放的盘子类似当将一个盘子压入堆上时，用元来支付该压入动作的实际代价，并有元的存款(记的是元的帐)，将该元钱放在刚压入的盘子的上面在任何一个时间点上，堆中每个盘子的上面都有元钱的余款盘中所存的钱是用来预付将盘从栈中弹出所需代价当执行一个POP操作时，对该操作不用收任何费，只要用盘中所存放的余款来支付其实际代价即可Chapter 6 Amortized Analysis 为弹出一个盘子，拿掉该盘子上的元余款，并用它来支付弹出操作的实际代价这样，在对PUSH操作多收了一
10、点费后，就无须对POP操作收任何费MULTIPOP操作也无须收费为弹出第一个盘子，取出其中的元余款并用它支付一次POP操作的实际代价为弹出第二个盘子，再取出该盘上的元余款来支付第二次POP操作，等等这 样，对 任 意 的 包 含 n次 PUSH、POP和MULTIPOP操作的序列，总的平摊代价就是其总的实际代价的一个上界。又因为总的平摊代价为O(n)，故总的实际代价也为O(n).Chapter 6 Amortized Analysis 6.3 势能方法势能方法6.3.1 势能方法的原理势能方法的原理势能方法不是将已预付的费用作为存储在数据结构特定对象中的存款来表示，而是表示成一种“势能”，或“
11、势”，它在需要时可释放出来以支付后面操作的代价。势是与整个数据结构而不是其中的个别对象发生联系的。Chapter 6 Amortized Analysis 势能方法的工作过程：设对一个初始数据结构D0执行n个操作，对每个i=1,2,.,n，ci为第i个操作的实际代价，Di为对数据结构Di-1执行第i个操作的结果。势函数将每个数据结构Di映射为一个实数(Di)，即与数据结构Di相联系的势。第i个操作的平摊代价ci定义为：cici+(Di)-(Di-1)*每个操作的平摊代价为其实际代价加上由于该操作所增加的势。Chapter 6 Amortized Analysis n个操作的总的平摊代价为：Ch
12、apter 6 Amortized Analysis Chapter 6 Amortized Analysis 如果势函数满足(Dn)(D0)，则总的平摊代价 就是总的实际代价的一个上界。*在实践中，我们定义(D0)为0，然后再证明对所有i有(Di)0.Chapter 6 Amortized Analysis 势能在平摊分析中的作用 如果第i个操作的势差(Di)-(Di-1)0，则平摊代价ci就表示对第i个操作多收了费，同时数据结构的势也随之增加了。如果第i个操作的势差(Di)-(Di-1)0,则平摊代价ci就表示对第i个操作的收费不足，这时就通过减少势来支付该操作的实际代价。Chapter
13、6 Amortized Analysis*平摊代价依赖于所选择的势函数。不同的势函数可能会产生不同的平摊代价，但它们都是实际代价的上界。Chapter 6 Amortized Analysis 6.3.2 6.3.2 势能方法实例势能方法实例 栈操作栈操作 为了说明势能方法，我们再一次来研究一下栈操作PUSH、POP和MULTIPOP。势函数定义 (D)=栈D中对象的个数 初始栈D0为，(D0)=0 因为栈中的对象数始终非负，第i个超作之后的栈DI满足(Di)0=(D0)以表示的n个操作的平摊代价的总和就表示了实际代 价的一个上界。Chapter 6 Amortized Analysis 作用
14、于包含s个对象的栈上的栈操作的平摊代价 如果第i个操作是个PUSH操作 实际代价：ci=1 势差：(Di)(Di-1)=(s+1)s=1 平摊代价：ci=ci+(Di)(Di-1)=1+1=2Chapter 6 Amortized Analysis 如果第i个操作是POP 实际代价：ci=1 势差：(Di)(Di-1)=1 平摊代价：ci=ci+(Di)(Di-1)=11=0如果第i个操作是MULTIPOP(S,k)且弹出了k=min(k,s)个对象 实际代价：ci=k 势差：为(Di)(Di-1)=k 平摊代价：ci=ci+(Di)(Di-1)=kk=0Chapter 6 Amortized Analysis 平摊分析 每个栈操作的平摊代价都是O(1)n个操作序列的总平摊代价就是O(n)因为(Di)(D0)，n个操作的总平摊代价即为总的实际代价的一个上界，即n个操作的最坏情况代价为O(n).EndThank you!Chapter 6 Amortized Analysis