加载中…
正文 字体大小:

【OI杂记】平摊分析

(2009-12-28 10:18:58)
标签:

杂谈

分类: OI-ACM

    平时分析算法的时间复杂度时,基本上就是看大的循环语句。其实,不然,对于有些操作,通过平摊分析,可以获得对某种特定的数据结构的新认识,这种认识有助于优化设计。

 

    1985年,Robert提出平摊分析。
    在平摊分析中,在一数据结构上执行一个操作序列所需时间是所有操作执行时间的平均。它常用来证明在一个操作序列中,即使某个操作具有较大代价,当通过对所有操作求平均后,一个操作的平摊代价仍很小。

    与平均情况分析的区别是,平摊分析不涉及到概率,保证其平摊性能是每个操作在最坏情况下具有的平均性能。

 

    平摊分析特点
    1)它是一种分析的方法,适用于分析一个彼此相关的操作序列。其分析方法不是孤立地分析每个操作的时间界限,而是将整个操作序列作为一个整体考虑,利用各操作彼此的关系求整个操作序列的时间界限,然后摊薄得到各操作的平摊代价。
    2)操作序列的总代价是序列长度的函数,而不是输入量规模的函数。
    3)不仅是分析方法,也是设计算法和数据结构的一种思维方法。
   因为设计算法与分析时间性能紧密相关,
   所以通过平摊分析可优化算法设计,加深对算法所操作的数据结构特性的认识,从而设计出时空性能更优的数据结构

    提出三种平摊分析的方法:

    合计法、聚集方法(aggregate):
    记账法、会计法(accounting):

    势能法(potential)。

 

    一、聚集分析

    该方法中,对所有的n,具有n个操作的序列在最坏情况下的总时间为T(n),因此,最坏情况下每个操作的平摊代价为T(n)/n。注意,n个操作可以是同一个操作,亦可以是不同的操作。与后两种方法不同的是:各操作的平摊代价相同。

 

    1、栈操作(不同种类)
    数据结构:栈S,初值为空。
    操作:
    Push(S, x): O(1)
    Pop(S):   O(1)
    MultiPop(S, k):  O(min(|S|, K)) 弹出min(|S|, K)个对象。

    栈上操作序列的时间分析:
    通常分析方法得不到紧确界。设有n个Push,Pop和Multipop操作构成的序列作用在初值为空的栈S上。一次Multipop的最坏时间为O(n),因为|S| ≤n,K=O(n);最坏情况下可能有O(n)个Multipop。因此,该序列最坏时间为O(n2)。

    合计法可得紧确界。因为一个对象入栈后至多被弹出一次,所以在非空栈上调用Pop的次数(包括Multipop中调用的Pop)至多为Push的次数。因此,当S初值为空时,Push次数至多为O(n),而Pop次数至多为O(n)。因为每个Pop和Push的实际代价均为O(1),所以对任意整数n,操作序列长度为n时,总时间T(n)=O(n),三个操作的平摊代价均为O(n)/n=O(1)。注意:没有实用概率分析。

    2、二进制计算器(同一类操作)
    数据结构:
    设A[0..k-1]数组作为二进制计数器,初值为0,A[i]=0, 0 ≤i ≤k-1。A中存储二进制数x:

    操作:将二进制计数器A的值加1(模2k,0≤x ≤ 2k-1)。

    INCREMENT(A)
      i<--0
      while i<length[A] and A[i]=1
        do A[i]<--1
           i<--i+1
      if i<length[A]
        then A[i]<--1

    执行过程:初值为0,做n次增量操作。

【OI杂记】平摊分析

    方框部分表示为取得下一个值而将发生的翻转,每次增1操作代价为每次翻转的位数。总成本不超过增量操作执行的总次数的2倍。
    时间分析:
    通常分析:最坏时,Increment改变值的位数为Θ(K) (A[i]=1, 0≤i≤k-1),n个增量作用在初值为0的计数器上,总代价为Θ(nK)。
    合计法分析:n次增量操作中,并非每次所有位都发生变化,上表告诉我们,无论n值为何,其总翻转位数<2n,即总代价为O(n),更严格证明如下:
   当位i ≤ ceil(lgn)时
   A[0], 每调用1次翻转1次,共n次翻转
   A[1], 每调用2次翻转1次,共ceil(n/2)次翻转
   A[2], 每调用4次翻转1次,共ceil(n/4)次翻转
      ……
   A[i], 每调用2i次翻转1次,共ceil(n/2i)次翻转
 当位i>ceil(lgn)时
   ∵n的二进制表示最多有ceil(lgn)+1位
   ∴A[i]在n次增量操作中,始终不变(高位不翻转)。于是,n此操作总的翻转次数为:【OI杂记】平摊分析
    即:操作序列总代价(在最坏情况下)为O(n),每次操作的平摊成本为O(n)/n=O(1)。

 

    二、记账方法

    费用分配(平摊代价):为不同的操作分配不同的费用,每一操作分配到的费用称为该操作的平摊代价,它可视作为数据结构对该操作预收的费用(或理解为是该操作对数据结构预付的费用)。

    【OI杂记】平摊分析
  

   超额收费(overcharge)(平摊代价>实际成本):当一个操作的平摊代价大于其实际成本时,数据结构对该操作预收的费用过多,其超额部分作为存款存储在数据结构的某个特定对象上。
   收费不足(undercharge)(平摊代价<实际成本):当一操作的平摊代价小于其实际成本时,数据结构对该操作预收的费用不足,其差额部分可由数据结构的特定对象(是该操作操作的对象)上的存款支付。
   以丰补歉:与合计法不同,这里不同的操作平摊代价可能不同,原则是以丰补歉。
  

   正确选择各操作的平摊代价(平摊代价的正确性):
   要说明每个操作的平摊代价是最坏情况下的平均代价,则必须保证对任意长度n的操作序列,总平摊代价是总的实际代价的一个上界:
    【OI杂记】平摊分析
    或者说:与数据结构相关的总存款在任何时刻都必须非负: 
    【OI杂记】平摊分析
    否则,若某一时刻总存款为负,则对于该时刻为止的操作序列(即对某个n),其总平摊代价不是总实际代价的上界。因此,各操作的平摊代价就不是最坏情况下的平均代价。

    1、栈操作(不同种类操作)

    【OI杂记】平摊分析

    平摊代价的正确性:说明对任何n,总平摊代价是总的实际成本的上界。等价于:任何时候栈中元素的总存款≥0。

    证明:任何时候栈中元素的总存款≥0。
          设每个代价单位:1元
          栈——餐馆的盘子
          Push:将一盘子放入栈中,该操作付出的2元钱1元用来支付入栈操作的实际成本,剩余1元作为存款放到刚刚入栈的盘子上。
          Pop和Multipop:平摊成本为0,但因为栈中每个盘子上均有1元存款,故可用该存款支付每个盘子出栈所需的实际成本。
         综上所述:
         任意时刻,栈中盘子总存款≥0,故任意长度n的操作序列,总平摊成本是总实际成本的一个上界。
         ∴每个操作平摊成本是O(1),n个由Push,Pop和Multipop组成的操作序列总平摊成本是O(n),因此总实际成本亦为O(n)。

 

    2、二进制计数器的增量(同种操作)
    Increment的实际成本——翻转位数,设每位翻转代价:1元
    平摊成本:  置位(0→1)收费2元
                 复位(1→0)收费0元
    正确性:当某位被置位时,2元收费中1元用于支付实际成本,另1元存在该位上,则计数器中,值为1的位上均有1元存款。当某位复位时,用该位上1元存款来支付复位的实际成本。
    ∵任意时刻,计数器中值为1的位数非负,故总存款数≥0。
    ∴n次增量操作的总平摊成本是总实际成本的一个上界。即一次增量操作的平摊成本是最坏情况的平均成本。
    ∵一次操作平摊成本为O(1)。
    ∴n次增量操作的总平摊成本为O(n)。

 

    三、势能方法

    与记账法的区别:存款——作为势能保存在整个数据结构上,而非其中的特定的对象上。需要时通过释放能量来支付操作的实际代价。
    势能、势差、势函数、各操作的平摊成本。
    数据结构:D,初态记为D0。
    操作:n个,n可变。
    ith操作OPi的结果:Di-1→Di,Di-1和Di表示操作前后D的状态(1≤i≤n)。


    势函数Φ(Di):将每个Di映射为一个实数(1≤i≤n),函数值看作势能。
    OPi的实际成本为Ci。
    OPi的平摊成本为Ĉ=Ci+Φ(Di)-Φ(Di-1) (17.2)
    操作的平摊代价由两部分构成:实际成本Ci和势差(操作所引起的势能变化)。
    【OI杂记】平摊分析

    总的平摊代价及势函数的选择(正确性):

    【OI杂记】平摊分析

    即n个操作后,势差为:序列最终的势能和最初的势能之差。此势差≥0或Φ(Dn) ≥Φ(D0),则总的平摊代价是总的实际成本的一个上界,但须对任意的n成立,故有:
    ∀i∈I,Φ(Di)≥Φ(D0),通常定义Φ(D0)=0
    则有:∀i∈I, Φ(Di)≥0
    满足上式保证平摊代价的正确性。
    势函数选择常常需要某种折衷,根据相应的时间界来选定,最佳选择往往使界尽量紧致。

    1、栈操作
    势函数Φ:栈中对象数目。
    初始:设D0表示空栈,Φ(D0)=0
    对任意i, Φ(Di) ≥ 0 = Φ(D0),即任意时刻,栈中对象数非负
    结论: Φ定义保证了n个操作的总平摊代价是总的实际代价的一个上界
    各栈操作的平摊成本:
    设当前栈中对象数|S|=s,OPi是:
    ①Push
      势差: Φ(Di)-Φ(Di-1)=(s+1)-s=1 //多收费
      平摊成本: Ĉ=Ci+Φ(Di)-Φ(Di-1)=1+1=2 //Ci=1
    ②Pop
      势差: Φ(Di)-Φ(Di-1)=(s-1)-s = -1 //少收费
      平摊成本: Ĉ=Ci+Φ(Di)-Φ(Di-1)=1-1=0 //Ci=1
    ③Multipop(S,k): 弹出对象数k’=min(s,k)
      势差: Φ(Di)-Φ(Di-1)=(s-k’)-s = -k’
      平摊成本: Ĉ=Ci-k’ = 0  // Ci = k’
    总的平摊成本:T(n)=O(n) //各操作的平摊成本为O(1)
    【OI杂记】平摊分析

 

    2、二进制计数器的增量操作
    势函数Φ:计数器中1的数目。
    1)初始势能为0
      Φ(D0)=0,计数器初值为0
      ∀i, Φ(Di)≥0=Φ(D0),即任一时刻,计数器中1的数目非负
      ①实际成本
        设OPi中复位数目为ti,置位至多有1个,即 Ci≤ti+1
      ②势差
        设OPi操作之后,计数器中1的数目为bi,即:
        Φ(Di)= bi。
        则:
          bi≤bi-1-ti+1 //若有置位,左右应相等
          ∴ Φ(Di)-Φ(Di-1) ≤(bi-1-ti+1)-bi-1=1-ti
      ③平摊成本:

        【OI杂记】平摊分析

    2)初始势能>0:Φ(D0)=b0>0
      设Φ(Dn)=bn
      ∵0≤b0,bn≤k(k为计数器的长度),改写(17.3)可得:

      【OI杂记】平摊分析
      注意:在上式中Ĉi ≤2, 与b0是否为0无关,故可利用它直接分析总的实际成本。
      这里要求k=O(n),或执行Increment操作至少k次(n≥Ω(k)),即可保证:无论计数器的初值为何,总的实际代价都是O(n)。

0

阅读 评论 收藏 转载 喜欢 打印举报
已投稿到:
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

      

    新浪BLOG意见反馈留言板 不良信息反馈 电话:4006900000 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有