章平摊分析 - Read.PPT

第 6章平 摊 分 析（ Amortized analysis） 基本思想 平摊分析的方法 聚集方法 会计方法 势能方法 聚集分析法-原理 平摊分析实例1-栈操作 普通栈操作 PUSH(S,x)：将对象压入栈S POP(S)：弹出并返回S的顶端元素 时间代价: ·两个操作的运行时间都是O(1) ·我们可把每个操作的代价视为1 ·n个PUSH和POP操作系列的总代价是n ·n个操作的实际运行时间为?(n) 平摊分析实例1-栈操作 新的栈操作 操作MULTIPOP(S,k)： 去掉S的k个顶端对象 或当S中包含少于k个对象时弹出整个栈 平摊分析实例1-栈操作 初始为空的栈上的n个栈操作序列的分析 由PUSH、POP和MULTIPOP长为n的栈操作序列 平摊分析实例2-二进计数器 1. 问题定义 ?实现一个由０开始向上计数的k位二进计数器。 输入：k位二进制变量x，初始值为0。 输出：x+1 mod 2k。 数据结构： A[0..k-1]作为计数器，存储x x的最低位在A[0]中，最高位在A[k-1]中 x = 平摊分析实例2-二进计数器 2. 计数器加1算法 输入：A[0..k-1]，存储二进制数x 输出：A[0..k-1]，存储二进制数x+1 mod 2k 平摊分析实例2-二进计数器 3.初始为零的计数器上n个INCREMENT操作的分析 会计方法-基本原理 一个操作序列中有不同类型的操作 不同类型的操作的操作代价各不相同 于是我们为每种操作分配不同的平摊代价 会计方法实例 1 — 栈操作 会计方法实例 1 — 栈操作 3. 栈操作序列代价分析 会计方法实例 2 -二进计数器 1. 计数器加1算法 输入：A[0..k-1]，存储二进制数x 输出：A[0..k-1]，存储二进制数x+1 mod 2k 　　INCREMENT(A) 1????? i?0 2????? while ilength[A] and A[i]=1 Do 3????? A[i]?0; 4????? i?i+1; 5????? If ilength[A] 6????? Then A[i]?1 会计方法实例 2 -二进计数器 初始为零的计数器上n个INCREMENT操作的分析 势能分析—基本原理 在会计方法中，如果操作的平摊代价比实际代价大，我们将余额与具体的数据对象关联 如果我们将这些余额都与整个数据结构关联，所有的这样的余额之和，构成——数据结构的势能 如果操作的平摊代价大于操作的实际代价-势能增加 如果操作的平摊代价小于操作的实际代价，要用数据结构的势能来支付实际代价-势能减少 势能分析—基本原理 势能的定义： 对一个初始数据结构D0执行n个操作 对操作i: 实际代价Ci, 将数据结构Di-1 变为Di 势函数?将每个数据结构Di映射为一个实数?(Di) 平摊代价c’i定义为：c’i＝ci + ?(Di)-?(Di-1) 势能分析—基本原理 n个操作的总的平摊代价为： 势能方法实例1 — 栈操作 ?(D)=栈D中对象的个数 初始栈D0为，?(D0)=0 因为栈中的对象数始终非负，第i个超作之后的栈DI满足?(Di)?0=?(D0) 于是： 以?表示的n个操作的平摊代价的总和就表示了实际代价的一个上界 势能方法实例1 — 栈操作 作用于包含s个对象的栈上的栈操作的平摊代价 势能方法实例 2 -二进计数器 ·?(D)=计数器D中1的个数 ·计数器初始状态D0中1的个数为0，?(D0)=0 ·因为栈中的对象数始终非负，第i个超作之后的栈Di满 足?(Di)?0=?(D0) ·于是：n个操作的平摊代价的总和就表示了实际代价的一个上界 势能方法实例 2 -二进计数器 第i次INCREMENT操作的平摊代价 势能方法实例 2 -二进计数器 开始时不为零的计数器上n个INCREMENT操作的分析 设：开始时有b0个1 0?b0 在n次INCREMENT操作之后有bn个1 动态表 动态表的概念 本节的目的： 研究表的动态扩张和收缩的问题 利用平摊分析证明插入和删除操作的平摊代价为O(1)，即使当它们引起了表的扩张和收缩时具有较大的实际代价 研究如何保证一动态表中未用的空间始终不超过整个空间的一部分 动态表-基本术语 动态表支持的操作 ·TABLE-INSERT：将某一元素插入表中 ·