算法导论Chapter 17.ppt

*,Robert提出在平摊分析中,在一数据结构上执行一个操作序列所需时间是所有操作执行时间的平均。它常用来证明在一个操作序列中,即使某个操作具有较大代价,当通过对所有操作求平均后,一个操作的平摊代价仍很小*,保证其平摊性能是每个操作在最坏情况下具有的平均性能三种平摊分析技术合计法、聚集方法(aggregate)记账法、会计法(accounting)势能法(potential)*,常用:先求出合计,然后摊薄先求出操作序列里所有n个操作的总代价上界T(n),每个操作的平摊代价T(n)/n记账法对操作序列中的各操作收费,以支付操作的实际代价数据结构——收费单位操作——付费单位*拦怖唆***(费用),对不同的操作收费可以不同对有的操作超额收费:即该操作实际成本低于该收费,余款作为“预付存款”存储在数据结构某些特殊对象上对有的操作收费不足:即该操作实际成本大于此收费,不足部分由特殊对象上的存款支付*(收费),对某些操作预先超额收费以补偿后续收费不足的操作不同之处是:存款是作为整个数据结构的“势能”加以维护,而不是将存款与数据结构中某些个体对象联系起来注意:为操作指定的费用只是为了分析之用,不应出现在代码中*)它是一种分析的方法,适用于分析一个彼此相关的操作序列其分析方法不是孤立地分析每个操作的时间界限,而是将整个操作序列作为一个整体考虑,利用各操作彼此的关系求整个操作序列的时间界限,然后摊薄得到各操作的平摊代价2)操作序列的总代价是序列长度的函数,而不是输入量规模的函数*锥棉澎杉北菱梗龋瞧社扯粳咙稀好鹰并坛尿驭界椅***)不仅是分析方法,也是设计算法和数据结构的一种思维方法因为设计算法与分析时间性能紧密相关,所以通过平摊分析可优化算法设计,加深对算法所操作的数据结构特性的认识,从而设计出时空性能更优的数据结构*,对所有的n,具有n个操作的序列在最坏情况下的总时间为T(n),因此,最坏情况下每个操作的平摊代价为T(n)/n注意n个操作可以是同一个操作,亦可以是不同的操作与后两种方法不同的是:各操作的平摊代价相同*、栈操作(不同种类)数据结构:栈S,初值为空操作Push(S,x): O(1)Pop(S): O(1)MultiPop(S,k): O(min(|S|,K))弹出min(|S|,K)个对象*垢营挪抢豺卜唤儡炔沂蔬钒诡藐原夫近莎届苛咨什詹亩吝屁横献插毅添励算法导论Chapter17算法导论Chapter17