“Mathematical Analysis of Algorithms” 阅读心得

2 minute read

Published:

原文首发于https://www.cnblogs.com/hehao98/p/8528206.html,如果公式显示不正常请参考原网页。

“Mathematical Analysis of Algorithms”是著名计算机界大神Knuth在1971年发表的论文。以前只是听说Knuth非常神,看了这篇论文才体会到Knuth到底有多神…Orz

此外,特别感谢 @solaaaaa 聚聚,没有他的指导我可能根本看不懂这篇论文……

这篇文章要解决什么问题?

作为算法分析这一领域的早期论文,这篇文章回答了以下两个问题:

  1. 算法分析的核心目的是什么?

    使用量化方法来衡量算法的“好坏”。

  2. 算法分析解决的是哪些类型的问题?

    A. 对一个特定算法的时间复杂度和空间复杂度的分析。

    B. 对解决一类问题的所有算法进行分析,试图找出“最好”的算法。

此外,本文特别指出,虽然B类的问题看上去比A类的问题更有价值去解决,但对(2)类问题的研究存在两个重大的问题:1、只要对“最好”的定义稍有改变,一个B类问题就会变成另一个完全不同的(2)类问题;2、B类问题往往过于复杂,难以进行有效的数学建模,而如果建立过于简化的模型,容易得到不合常理的结果。出于以上原因,只有少数B类问题(如基于比较的排序) 能得到有效的解决,绝大多数算法分析依然是对A类问题的研究。

之后本文的核心,就是通过两个例子,来展现算法分析的基本思路。

例一:In Situ Permutation

1. 问题定义

给定一个一维数组x1,x2,,xn和一个对1,2,,n的排列p(1),p(2),,p(n),我们需要将一维数组x根据函数p替换为一维数组xp(1),xp(2),,xp(n),有以下要求:

  1. 不能修改存储排列p(1),p(2),,p(n)的空间。
  2. 整个算法的空间复杂度必须为O(1)

2. 设计算法

对以下算法的设计基于以下一个重要的事实:在任意一个排列p(1),p(2),,p(n),我们总会存在若干个“环”,这个环形如p(i1)=i2,p(i2)=i3,,p(ik)=i1。学过抽象代数的同学可以对此给出一个严格证明。例如对于一个排列:

(p(1),p(2),,p(9))=(8,2,7,1,6,9,3,4,5)

通过观察我们发现了以下环:

{p(1)=8,p(8)=4,p(4)=1p(2)=2p(3)=7,p(7)=3p(5)=6,p(6)=9,p(9)=5

我们就可以定义这个环中最小的值为这个环的头元素。那么只要我们发现了一个环的头元素k,就可以将原来的数组中的xk空出来,将紧随其后的元素xp(k)填入,然后xp(k)的位置就会被空出来可以填入xp(p(k))……最后将头元素xk填入环尾部那个排列对应的x数组的位置即可。

对应的伪代码描述如下:

for j = 1 to n: # 外循环
    # 判断 j 是不是环的头元素
    # 从p(j)开始遍历这个环
    k = p(j)    
    # 如果j不是环的头元素,那么就会存在一个环上点k<j
    while k > j: # 循环1 a
        k = p(k)
    if k == j:   # 语块2 b
        # k就是环的头元素
        y = x[j], l = p(k)
        while l != j: # 循环3 c 
            x[k] = x[l], k = l, l = p(k)
        x[k] = y
        # 到这一步为止一个环上的元素全部按照排列置换完毕

3. 算法分析

对一个特定算法分析(A类问题)而言,最重要的是证明算法的正确性。在正确的基础上,我们讨论它的最好情况复杂度,最坏情况复杂度和平均情况复杂度。对平均情况的分析往往有更重要的意义。但就算法分析而言,一般对平均情况的分析会复杂得多,最后常常归结为某个很难的数学问题。

就这个问题而言,为了便于讨论,我们将内层循环和语句块如上面伪代码注释所示进行标号a,b,。

正确性

事实上,算法的设计过程已经简单说明了这个算法的正确性。要给出一个严谨的证明非常麻烦这里不再赘述。

最好情况与最坏情况

显然,外层循环无论如何都会被执行n次,因此我们主要考虑内层ab的执行次数。

我们先构造只有一个长n的环的情况。令

(p(1),p(2),,p(n))=(2,3,...,n,1)

那么a就进入了最坏情况,这样,对于第i个外层循环,a循环需要执行ni次,总共执行次数为

ni=1(ni)=O(n2)

巧妙的是,此时刚好是b的最好情况!因此b只用执行一次,这一次执行的复杂度为O(n)

因此,这个最坏情况的执行时间为O(n2)

我们再构造有n个环的情况。令

(p(1),p(2),...,p(n))=(1,2,...,n)

这时b进入了最坏情况,a进入了最好情况,类似分析可得这种情况的执行时间为O(n)

平均情况

我们首先对这个问题进行重新建模。依然是对之前举过的排列

(p(1),p(2),,p(9))=(8,2,7,1,6,9,3,4,5)

我们可以将它的环写成(5,6,9)(3,7)(2)(1,8,4),满足:1、每个环开头是其最小的元素。2、每个环的头元素从大到小递减,那么就可以直接表示成另一个排列(q(1),q(2),,q(9))=(5,6,9,3,7,2,1,8,4),因为我们只要找到其中的数qk使得qk=minq1,q2,,qk,那么这个数就是一个环的头元素,这个环从这个元素开始直到下一个具有相同性质的元素之前为止。比如,由于3=min5,6,9,3,我们就发现了q(4)=3是一个环的头元素,这个环是(3,7),因为我们发现了7之后的2比前面所有数都小,所以2就是下一个环的元素了。这样,我们就建立了从一个排列p到另一个排列q的映射。

我们对q这个排列,首先研究a循环在平均情况下的执行次数。

对于任意一个a循环,它从一个随机的环上的元素开始向后遍历,也就是说,如果外循环中j=q(i)k就会一直往后进入q(i+1),q(i+2),,直到找到一个位置q(i+r)使得q(i+r)<q(i),或者q(i)就是环的头元素。所以,当外循环j=q(i)时,就会从q(i)q(i+r)执行这么多次。这样我们可以用以下方式来表示循环a的执行次数。令

yij={1,if q(i)<q(k) for i<kj0, otherwise

那么

a=1i<jnyij

对于上面的例子而言第一行只有y12=y13=1,因为当外循环中的变量j=q(1)时,循环a会被执行2次,直到遍历回到q(1)发现q(1)就是头元素为止,由于我们构造q的时候让头元素递减,所以如果考虑成因为发现q(1)<q(4)而退出,不会对研究循环a的执行次数造成影响。同样地对于外循环变量j=q(2)的情况,只会往后执行1次就会发现q(2)<q(4),因此第二行只有y23=1。类似分析还能找到 y45=y78=y79=1

为什么要定义这么一个yij呢?因为我们非常容易就可以发现yij的平均值$\bar{y}{ij} n! y{ij}=1 q(i)=min(q(k)\mid i \le k \le j) {1}/({j-i+1}) $(给K神跪了)因此

ˉa=1i<jnˉyij=1i<jn1ji+1  (iji)=(121+1+131+1+...+1n1+1)+(132+1+142+1+...+1n2+1)+...+(1n(n1)+1)=n12+n23+...+1n=2rnn+1rr  (r=ji+1)=(n+1)(Hn1)(n1)=(n+1)Hn2n

其中Hn是调和级数,使用积分法可以证明

Hn=ni=11i=O(logn)

所以我们得到a循环的平均执行次数为O(logn)

下面分析b的执行次数。显然,环有多少个,b就会被进入多少次。这所有次数加起来的循环c的执行代价为O(n)固定不变。因此我们需要考虑b平均会被进入多少次,也就是所有长度为n排列中平均有多少个环。在Knuth的TAOCP, 1.2.10中已经对此有过分析,因此原文没有写出。(因为我没有TAOCP有大概也看不懂)所以我们只写一个结论:有k个环的排列共有[n,k]个,这个[n,k]是第一类Stirling数。最后可以得到b的平均值刚好是调和级数!(我推了推死活推不出来…)

ˉb=Hn=O(logn)

通过以上讨论我们就严格证明了平均情况下这个算法的复杂度是O(nlogn)

原文还有关于a,b的方差讨论,由于计算极其繁杂在此就不写了。重要的结论是,它的方差证明了O(n2)的最坏情况是非常罕见的。

算法的改进空间

我们可以通过增加一个变量来避免全部元素移动完成后的不必要的遍历,但这不会改善平均情况和最坏情况的复杂度。但是有一个方法可以将最坏情况复杂度降低到O(nlogn),这个方法的关键是对于外循环遍历到的一个j,我们同时搜索p(j),p1(j),p(p(j)),p1(p1(j)),,其中p1(j)是其反函数。这样,我们重新考虑最坏情况,显然就是整个排列只有一个长度为n的环,例如排列(1,2,,n)。这样,最坏情况就是我们从j开始向环的两边搜索到头元素的时间,再加上j在环前面和环后面的长度分别为knk的部分都处在最坏情况的时间之和。设最坏情况为f(n),就得到如下递推式:

{f(n)=max1k<n{min{k,nk}+f(k)+f(nk)}f(1)=0

(内心OS:这种东西TM也能解?!)

K神拒绝回答你的提问并直接把答案甩在了你脸上:

f(n)=0n<nv(k)  (v(k)k1)f(2a1+2a2+...+2ar)=12(a12a1+(a2+2)2a2+...+(ar+2r2)2ar)a1>a2>...>ar

在其他几篇由Bush、Mirsky、Drazin、和Griffith发表的论文里有对其复杂度的详细分析。通过这些分析我们知道了这个解法在最坏情况下的复杂度为O(nlogn)。(我的内心已经崩溃了)

例二:Selecting the t-th largest

1. 问题定义

给定一个数组a1,a2,,an,试用尽可能小的比较次数找出其中第t大的值。

2. 设计算法

这个问题相对比较常见一些,甚至曾经出现为数据结构作业题……但是其实这个问题想到算法容易,算法的分析并没有那么容易。首先一个O(nlogn)的排序算法总能解决我们的问题,但有没有复杂度更低的方法呢?通过快速排序思路的启发我们可以想到这样一个算法,假如我们对数组ai,ai+1,,aj搜索,首先调用其中的Partition()方法将数组头元素ai的位置放到一个位置使得他左边的元素都比他小,右边的元素都比他大;然后根据他的位置k来缩小我们搜索第t大数的范围:如果k=t我们就找到了这个元素;k<t则对ak+1,,aj搜索;kt就对ai,,ak1搜索。这是一个标准的分治算法。可以写出以下伪代码:

FindtthNumber(a, i, j, t):
    key = a[i]
    # Partition的实现请参考快速排序相关资料
    # Partition返回的是分割后的数组下标
    # 减去数组开头的位置得到a[k]是a[i]-a[j]里第几大的数
    k = Partition(key, a, i, j) - i + 1 
    if k == t:
        return a[k]
    else if k < t:
        return FindtthNumber(a, k + 1, j, t - k)
    else:
        return FindtthNumber(a, i, k - 1, t)

3. 分析算法

通过伪代码我们可以看出,影响一个子问题的变量有两个:ntn是这个子问题中数组的长度,t是这个子问题中我们要找的第t大的数。不妨设这个子问题为C(n,t)。假设我们的分割到什么位置完全随机,即这个子问题分割找到第1大、第2大、…、第n大的数的个数完全相等,均为1/n,我们就能分析得到以下递推方程:

{C(1,1)=0C(n,t)=n1+1n(A(n,t)+B(n,t))其中A(n,t)=C(n1,t1)+C(n2,t2)+...+C(nt+1,1)B(n,t)=C(t,t)+C(t+1,t)+...+C(n1,t)

显然A(n,t)对应于递归函数中k<t的情况,B(n,t)对应于递归函数中k>t的情况。

之后我们任务就是求解这个递推方程了。一般人看到这个递推方程大概就会放弃了吧,然而Knuth发现这个递推方程是可以求解的(跪了跪了)!依然是使用差消迭代法。首先通过观察我们看到

A(n+1,t+1)=A(n,t)+C(n,t)B(n+1,t)=B(n,t)+C(n,t)

这样我们就可以把C(n+1,t+1),C(n,t+1),C(n,t),C(n1,t)按如下方式相减:

(n+1)C(n+1,t+1)nC(n,t+1)nC(n,t)+(n1)C(n1,t)=(n+1)nn(n1)n(n1)+(n1)(n2)+A(n+1,t+1)A(n,t+1)A(n,t)+A(n1,t)+B(n+1,t+1)B(n,t+1)B(n,t)+B(n1,t)=2+C(n,t)C(n1,t)+C(n,t+1)C(n1,t)

推出来

C(n+1,t+1)C(n,t+1)C(n,t)+C(n1,t)=2n+1(C(n+1,t+1)C(n,t))(C(n,t+1)C(n1,t))=2n+1

之后需要列出边界条件,类似之前的推导

C(n,1)=n1+1n(C(1,1)+C(2,1)+...+C(n1,1))(n+1)C(n+1,1)nC(n,1)=(n+1)nn(n1)+C(n,1)C(n+1,1)C(n,1)=2nn+1=22n+1C(n,1)=2n2HnC(n,n)=2n2Hn  ()

由上述两式可以计算得到

C(n+1,t+1)C(n,t)=2n+1+2n+...+2t+2+C(t+1,t+1)C(t,t)=2(Hn+1Ht+1)+22t+1

不断迭代

C(n,t)=2tk=2(Hnt+kHk+11k)+C(n+1t,1)=2((n+1)Hn(n+3t)Hn+1t(t+2)Ht+n+3)

由于调和级数Hn=O(logn),我们就严格证明了无论n,t取什么值,平均情况下算法的复杂度C(n,t)=O(n)。我们的算法比较次数已经足够小了,那么如何寻找最少的比较次数?这就从一个A类问题变成了B类问题,并且非常难,感兴趣的读者可以参考相关论文了解对这方面的进展。

总结

被前面两个算法搞晕了之后,相信大家已经了解算法分析是个什么样的过程了(笑)。最后Knuth对算法分析做了如下总结:

  1. 算法分析对计算机科学领域十分重要
  2. 算法分析与离散数学密切相关
  3. 算法分析正在形成科学方法
  4. 算法分析领域还有很多问题没有解决

参考文献

[1] “Mathematical Analysis of Algorithms” Donald Knuth, 1971.

Leave a Comment