首页 > 代码库 > 简单理解算法篇--摊还分析

简单理解算法篇--摊还分析

    摊还分析是用来评价程序中的一个操作序列的平均代价,有时可能某个操作的代价特别高,但总体上来看也并非那么糟糕,可以形象的理解为把高代价的操作“分摊”到其他操作上去了,要求的就是均匀分摊后的平均代价。

 摊还分析有三种常用的技术;聚合分析,核算法,势能法。

 首先看个例子,现在有三种操作,push(s),pop(s),mutlipop(s,k),push(s),统称为栈操作 push(s)每次只能压一个数据,所以规定操作的代价为1pop(s)每次只能弹一个数据,所以也规定操作的代价为1,而mutlipop(s,k),内部实现的是一个循环弹出,每执行一次的代价为kk<n,n为栈的最大容量)。那么现在问题来了,我想分析下执行n栈操作最坏情况下的时间复杂度是多少?第一反应应该就是这样想的,mutlipop(s,k)的代价最高,最高位k=n;

执行n次的最坏情况当然就是o(n2)啦,当实际上并非如此。

 

 聚合分析要求我们要总体看问题,首先mutlipop(s,k)也是个弹栈的操作,当栈里有数据的时候才执行有效,所以上述提到的o(n2)是不科学的,而push(s),pop(s)的代价是1,可想而知最坏的情况当然是前n-1次操作都是压栈,而最后一次才执行mutlipop(s,n-1),这样的代价也只有2n-2,时间复杂度为o(n),平均下来每个操作的摊还代价就为o(1)了。

 

 核算法比较好理解,进行摊还分析时,摊还的代价有可能多于实际的代价,也有可能少于实际的代价,多于实际代价的差额会存进一个数据结构中,称为信用,而当遇到少于实际代价的时候就可以用这些信用来填充了。注意这些什么算法提供的只是思路,求出一系列操作代价的上界的思路,具体的做法还是要自己思考的。

 同样是压栈的例子,我们可以赋给Push(s)操作的摊还代价是2,相当于自己使用了1,而压进去的必定会弹出,剩下的1就作为弹出时的费用,这样pop(s)mutlipop(s,k)的摊还代价就为0,这样做有什么意义?试着现在思考下题目中的问题(标红色的部分),那么可想最糟糕的情况无非就是所有操作都是Push(s),代价为2n,并不像聚合代价那样需要考虑其他两个操作(摊还代价为0),时间复杂度为O(n)

 

 势能法

 势能法其实核算法有点相似,也有预付差额的,但不叫信用,而叫势能,势能法是从整体上看的,不像核算法那样具体到某个操作,而是整体的势能。

势能法定义了一条公式;

                     Ci(摊还)=Ci(实际)+f(Di)-f(Di-1)          1

累加可得总摊还代价的公式为;

                     Ci(总摊还)= Ci(总实际)+ f(Di)-f(D0)        2

其中Ci 为每步操作的代价,f(Di)表示执行了第i个操作后的势能,那个这个公式就可以理解为 i步操作的摊还代价等于第i步操作的实际代价加上从第i-1步操作到第i步操作的势能变化,理解这个后,再来看栈操作的例子。

同样Push(s)pop(s)的代价为1, mutlipop(s,k)的代价为k,我们规定入栈一个元素势能加1,弹出一个元素势能减1,那么f(Di)永远为非负,f(D0)等于0,再根据上面的公式(2)即可知道这个又这里就可以确定总摊还代价是总实际代价的上界,所以现在要求的就是总摊还代价。

根据公式(1)可以得到Push(s)的摊还代价为2pop(s)的摊还代价为0mutlipop(s,k)的摊还代价也为0 (因为弹栈势能要减,刚好和代价抵消,也可以看做势能都用来支付代价了,所以下降了),那么又回到了核算法了,可得时间复杂度为O(n)

书上还有个例子是关于表扩张的,虽然能看懂,但还是理解的不太透彻(不明白他为什么能这么定义),在这里跟大家分享,也请大家指点~

例子:表扩张

是这样的,有个程序,假设这个表只允许插入,当插入数据发现表满了,会自动新建一个表大小为原来的两倍,然后把已有的数据复制过去,再插入,在问题就是要求这个程序的代价,准确来说是摊还代价。

这里只写两个方法吧,写多我自己都晕了..首先是聚合分析

我们将插入一条数据的代价看为1,假设一开始表的大小为1,没有数据,可想除了表数据满的情况,其他情况的代价都为1,而表满时的大小都为2的幂。当表满时插入数据的代价就是原有的数据复制的代价k(假设有k条数据)加上新插入的1,又此可得总摊还代价为

C(总摊还代价)<=n+20 +21+..+2lgn<n+2n=3n;(其中lgn表示表共扩张了lgn次,可以算出),所以摊还代价至多为3n/n=3

 下面看看核算法,通过核算法能很好的理解为什么摊还付代价为3.

书上是这样分析的,假设现在表中有m/2条数据,表大小为m,而且没有信用,那么插一条数据要付出3的代价,为什么?看,1是为了插入时消耗了,1是保存起来作为自己的信用,还有1呢,就是捐赠跟原本就在表中但没有信用的数据,这样,但数据插入了m/2条,一共有m条数据时,这也刚好是表要扩张的时候,表中所有的数据都有1的信用,就可以用来支付扩展表时复制到新表的代价,从而表的大小变成2m,数据刚好又没了信用而且刚好是表大小的一半,这又到回了最初,就好像递归一样,也就是说1条数据支持3代价就可以保证它永远的扩展

 感叹算法的思想博大精深,想研究透并不容易也谈不上研究,只是偶尔读读会让人心旷心怡,大家有想法一定要评论啊….

   

 

  

简单理解算法篇--摊还分析