算法导论自学笔记(2-2)

接上一小节,继续我们的平摊分析(Amortized algorithm)。

为什么我们需要平摊分析,这应该是首先要问的问题。前面的最好、最坏、平均情况分析还不够好吗?

网上有很多人讲平摊分析,也有一些平摊分析的例子。但是,很少有人来说为什么我们需要平摊分析。

其实我们肯定知道,之所以需要平摊分析,肯定是以前的分析方法有不好的地方,分析出来的时间复杂度没有平摊分析的有参考价值。

让我们以一个例子来开始我们的平摊分析——二进制计数器(Binary counter)。就是用二进制的方式计数,python代码实现如下。

    import math
    def Increment(counter):
        length = len(counter)
        i = 0
        while i<length and counter[i] == 1:
            counter[i] = 0
            i += 1
        if i<length:
            counter[i] = 1
        return counter
    if __name__ == '__main__':
        N = 8
        length = int(math.ceil(math.log(N,2)))
        counter = [ 0 for i in range(length) ]
        for i in range(N):
            print Increment(counter)

这就是一个简单的二进制计数器,N=8即计8次数,具体需要的二进制位数通过$\lceil log_2(8) \rceil$得到,就是求个对数然后再上取整。注意,这个计数器是从counter[0]开始加一的,和平时的二进制加一反着。(PS:该例子主要参考这里。)

现在已经实现了一个二进制计数器。我们来求一下我们最擅长的最坏情况下的时间复杂度。

当$N=n$时,需要$log_2 n$位来存储二进制数。而我们每一次执行Increment的时候,最多需要$log_2 n$次来改变所有的位,如11111这样的数,改变为00000。

所以,我们开开心心的得到了最坏情况下的时间复杂度:$O(nlog_2 n)$。我们是开心了,算法不开心啊!算法肯定在怒骂我们,凭什么都按照最坏的来计数啊,人家明明只有很少的情况下需要$log_2 n$次来改变所有的位好吧!太冤了,比窦娥还冤!

我们想想,也对啊,我们是不是太鲁莽了啊。我们是想知道算法最坏情况下执行的时间,所以我们喜欢计算最坏情况下的时间复杂度。但是,当这种所谓的最坏情况出现的次数很少的时候,我们用它来算还合适吗?你可能会说,我们有平均情况分析呢,不是考虑到所有的输入了吗,求平均还不合适?可是平均情况分析的输入分布是不确定的,等会儿,对于二进制计数这个问题,输入就是n啊,没有什么输入的顺序啊。

怎么办!?当输入有多种情况的时候,我们试图把输入给平均。现在,我们把程序看成是由一系列操作组成的,有些操作花的时间多,有些操作花的时间少,而我们试图把操作平均,即把总的花费平摊到每一个操作身上。

所以,最坏情况分析得到的时间复杂度不准(太大了,不用把上界定的那么大),比较粗略(Cursory analysis)。而我们当然希望越精确越好(Tighter analysis)。

如何精确的分析(Tighter analysis)?当然需要一些方法,是的,先人也曾考虑过这个问题,并且有了几种平摊分析的方法:聚集分析(Aggregate analysis)、记账方法(Accounting method)、势能方法(Potential method)。是的,你没有看错,平摊分析又包含这么多技术。那就拿二进制计数问题开刀吧,看看几种平摊分析的方法有多好。

Aggregate analysis

前面我们得到了粗略的分析结果$nlog_2 n$,现在,我们试图得到更加精确的结果。假设我们前面的counter数组存放了8个二进制数字,用C[i]表示其中的一个元素。我们可以得到下图。

从图中我们可以很容易得到规律,二进制低位(即C[0])在每一次计数的时候都会改变,C[1]有一半的次数会改变,以此类推。可以得到$T(n)=n+\frac{n}{2}+\frac{n}{8}+... \leq 2n$。(为什么会是2n呢?可以用等比数列的求和公式求一下,一共$log_2 n$项。)

怎么样?结果不一样了吧?我们的平摊分析之聚集分析得到了更精确的上界,而此时一次操作的平摊成本为$O(1)$,总的平摊成本为$O(n)$,这差别还是很大的,如下图所示!

哇,这就是平摊分析(聚集分析)!通过记录每个操作的代价,然后求和得到总的平摊成本!

Accounting method

我们继续考察二进制计数问题。经过仔细揣摩,换角度思考,我们发现:置位操作(0 → 1)在每次计数的时候都会出现且仅出现一次,而某个位的复位操作(1 → 0)会在置位后发生,如果事前不置位肯定就不会复位。

所以,我们可以这样计算总的平摊成本:

置位:收费2元;复位:收费0元。相当于我们每次置位的时候都预先支付未来可能发生的复位。

所以,$T(n) \leq n + n \leq 2n = O(n)$,第一个n表示总的置位操作,而复位操作肯定小于等于置位操作。

Potential method

第一种方法很好理解,就是求各个代价的和。第二种也还凑合,预先支付,留待以后使用,预先支付的肯定是够以后用的,多的部分就存银行,在公式里体现的是小于等于符号,表示有冗余的钱在银行呢。

相比而言,第二种抽象出来一种记账的思想,对于平摊分析很有用。而第三种方法则抽象出一种势的思想,对于平摊分析也很有帮助。貌似这样想更好接受一些。

记账方法的特点是预先考虑,多付点钱没问题,以后出了问题什么的就不用再掏钱了。而势能方法则是针对于每次的操作,如果花多了,就扣一点(势能减少),如果花少了,就补一些(势能增加),每一个操作的平摊代价为:${\widehat{C_i}} = C_i + \Phi(i) - \Phi(i-1)$

当然,如果要求解出平摊代价,我们还需要两个已知条件(观察得出):

$\Phi(i) = \Phi(i-1) + a - b$

$C_i = a + b$

其中a表示每次计数时置位操作的次数,显然是1啦,b表示复位操作的次数,未知。把两个式子相加即可得到我们想要的结果啦,即${\widehat{C_i}} \leq 2$。总的操作的平摊代价仍然是$O(n)$。

有一个疑问,为什么第一个公式里是$a-b$?是不是通过每次计数变成1的个数减去变成0的个数来表示势差的呢?势差该如何选择呢?

暂且只是学习下二进制计数的平摊分析吧,有点无聊。还是赶紧进入期待已久的Divide and conquer!

一些平摊分析的学习链接:

  1. http://blog.sina.com.cn/s/blog_51cea4040100gs31.html
  2. http://wenku.baidu.com/link?url=fQlJe4DOKwH85HZUNGioI_ry9uORrJ_koG4OFVOSsswWmB0OK1g0wgLVd_si3V2nsyBP80iacdOAX6vo4rv5q9VMDH479aLomOFbhn_XOzq
  3. http://functionspace.org/articles/50
  4. http://acm.miyuoo.com/2011/02/04/zz%E5%B9%B3%E6%91%8A%E5%88%86%E6%9E%90.html
  5. http://blog.csdn.net/touzani/article/details/1696399

-- EOF --