南开大学计算机算法设计与分析

计算机算法设计与分析引子DonaldKnuth,算法学历史上最卓越的计算机科学家之一,如此论述:受过良好训练的计算机科学家知道怎样处理算法:如何构造算法,操作算法,理解算法以及分析算法。这些知识远不止为了编写良好的计算机程序而准备的。算法是一种一般性的智能工具,它必定有助于我们对其他学科的理解,不管是化学,语言学,音乐,还是另外的科学。为什么算法会有这种作用呢?我们可以这样理解:人们常说,一个人只有把知识教给别人，才能真正掌握它。实际上,一个人只有把知识教给“计算机”，才能“真正”掌握它，也就是说，将知识表述为一种算法……比起简单地按照常规去理解事物，用算法将其形式化会使我们的理解更加深刻。Knuth,D.E.SelectedPapersonComputerScience,CSLIPublicationsandCambridgeUniversityPress,NewYork,1996有趣的问题1.西雅图附近一家著名软件公司主考官面试题：

4个人过桥，时间为晚上，只有一只手电筒，最多只能两个人同时过桥，且必须带手电，只能步行将手电简带来带去，而不能扔来扔去。每个人走路的速度不同，甲过桥要１分钟，乙过桥需要２分钟，丙需要５分钟，丁需要１０分钟，两个一起走，则速度等于其中较慢的人的速度。2.关于验证一个数是否为素数的问题3.旅行商问题：如何走最短的路，经过所有的城市。4.汉诺塔问题汉诺塔问题voidhanoi(intn,charone,chartwo,charthree)/*将n个盘子从one座借助two座，移到three座*/{if(n==1)move(one,three);else {hanoi(n-1,one,three,two); move(one,three); hanoi(n-1,two,one,three); }}main(){intm;printf(inputthenumberofdiskes:);scanf(“%d”,&m);printf(“Thesteptomoving%3ddiskes:\n”,m);hanoi(m,’A’,’B’,’C’);}ABC每个盘子有三个位置,n个共有3n绪论

1.1 交通信号灯问题

1.2 什么是算法

1.3 算法的评价

1.4 基本概念

1.5 算法研究与Moore定律

1.6 MAXMIN的问题1.1交通信号灯问题1.1.1

问题

⑴每一车辆通过路口时都不会与其它车辆发生冲突； ⑵车辆在路口等待通过的时间尽可能少。1.1.2实例共有13条路线：ab,ac,adba,bc,bdda,db,dcea,eb,ec,ed1.1.3

图着色问题

已知：n点无向图G=<V,E>,||V||=n。求：G的最小色数(colornumber)k，使得用k种颜色对G的顶点着色，可令任二相邻顶点着色不同。地图着色问题，交通信号灯问题都可以归结为图的顶点着色问题无向图顶点着色问题：顶点，边最小色数k地图着色问题：国家，相邻关系最小色数k交通信号灯问题：路线，交叉关系最小相位（组）数k2.图着色(GraphColoring）问题

图着色问题是一个经典的组合算法问题，源于地图着色问题。在绘制地图时，总是要求相邻的国家着上不同的颜色以示区别。1852年一位英国大学生古德里（F.Guthrie）提出了一个猜测：为了给任一个平面地图着色，并使任何有公共边界的区域颜色不同，至多需要四种颜色。这就是四色问题，又称四色猜想。古德里仅仅是提出了这个猜想，他和他的老师未能证明。2.图着色(GraphColoring）问题

二十几年后的1878年，著名数学家凯莱（A.Kayley）发表了一篇“论地图着色”的文章，虽然仍没有解决这个问题，却掀起了四色猜想的研究热。经过一百年的探索，美国伊利诺大学的哈肯（W.Haken）与阿佩尔（K.Appel）通过改进算法，借助计算机（共用了1200个机时）终于在1976年完成了四色猜想的证明。当地的邮局在寄出的信上除了通常的邮戳(postmark)外，还要加盖“四色是足够的”一句话以表示自豪。2.图着色(GraphColoring）问题

当把地图(Map)上的一个国家与图(Graph)上的一个顶点对应，两个国家的相邻关系对应于无向图上的边，于是，上面关于地图的“四色问题”实际上是无向图的顶点着色问题的特例。无向图的顶点着色问题是一个有名的NP完全问题，这类问题属于“计算机难解”问题，关于着色问题算法的研究已有许多学者的大量成果。

Fig.1.2给出的无向图对应于五叉路口实例，该图有13个结点和20条边，其中ba,dc,ed三个顶点是孤立点，说明这三条路线与其它所有路线不相交，就是所谓的“拐小弯”。

c1.1.4算法设计讨论1.穷举法令色数k从2开始，用k种颜色分别对13个顶点着色，共有k13种情形，当K＝5时，需要进行

20×(213+313+413+513)次比较。413=2262.剪枝法对穷举法的改进。不必穷举所有可能的着色法，例如：顶点ab着色为c1，则点ab的所有邻点ea,da,bc,bd都不必着色为c1；…

第一个点，例如ab，可以只着一种颜色，因颜色的对称性，ab取其它(k–1)种颜色的情形可不必再检查。此剪枝法一项可以把计算量缩小到原来的1/k。3.启发式(Heuristic)算法依赖于人的直觉知识：为了用最小色数为所有顶点着色，也就是要每一种颜色在不出现冲突的条件下为尽量多的顶点着色。算法1.1启发式算法实现图着色用k=1,2,3,…来表示颜色1#,2#,3#,…,Color[i]=3表示对i顶点着3#色，<i,j>∈E表示顶点i,j相邻，Color[i]=0表示顶点i未着色此法又称贪心法，比穷举算法和剪枝算法快得多，当n不太小时，其计算量比前者要少千万倍甚至更多，不过它不一定总是得到最优解。例如Fig.1.3中的5点无向图，用贪心法着色需要用红(R)、黄(Y)、蓝(B)三种颜色，但实际上，这不是该图的最小色数，显然，两种颜色已可满足要求。即：顶点1、3、4着红色，顶点2、5着黄色。(不同编号顺序)1.1.4讨论1.权衡(trade-off)的概念穷举法：思想最简单、最直观，但计算量最大。改进的穷举法：比前者要快，容许的n值可以再大一些，不过对于大的n，计算量仍会很大，它比穷举法有所改进的代价是程序较为复杂。启发式的贪心算法：简单，快速，但不能保证总是得到最优解。2.最优性(Optimality)GreedyColor算法是一种“近似最优”算法。执行的结果是，

k=4，13条路线分为4组：（括号里的路线为补充的不冲突项）ab,ac,ad,ba,dc,ed;bc,bd,ea,(ba,dc,ed);da,db,(ba,dc,ed,ad);eb,ec,(ba,dc,ed,ea).一般的说可能还有更好的分组方法，例如分为三组。不过，在这个实例中，却不难证明分为4组已不能改进。这是因为从Fig.1.2中发现ac,bd,da,eb4个顶点组成一个完全子图（又称团，Clique），4点的无向完全图至少需4色，因此这个解已不可改进。c3.算法设计讨论·算法的研究与许多实际应用问题直接相关，它不仅是个理论问题；·一些典型的算法问题的研究，如着色问题、旅行商问题、背包问题等等，常常在应用算法的设计中发挥作用；·用来解一个问题，可以有多种不同的算法，它们的效果可能差别很大，如何设计有效的算法是算法理论的主要目标。1.2什么是算法1.2.1算法1.Webster辞典定义：算法即在有限步骤内解一个数学问题的过程，步骤中常常包括某一操作的重复。更广义地说，一个算法就是为解一个问题或实现某一目标的逐步过程。2.D.E.Knuth定义：一个算法，就是一个有穷规则的集合，其中之规则规定了一个解决某一特定类型的问题的运算序列；此外，它还应有五个重要特性：·有穷性：一个算法必须总是在执行有穷步之后结束；·确定性：算法的每一步骤，必须是确切地定义的；·输入：有0或多个输入值；·输出：有1或多个输出值；·能行性：算法中要做的运算都是相当基本的，能够精确地进行的。3.形式化定义：算法就是一个对任一有效输入能够停机的Turing机。1.2.2算法与问题

例：整数乘法问题全部可能输入集合：{<a,b>|a,b∈Z}，其中Z表示整数集；一个实例：<2,4>,求：2×4=?旅行商问题(TravelingSalesmanProblem)实例集为：{n,Wn*n=[Wij]|n∈Z,Wij∈R,i,j∈[1,…,n]}；一个实例：n=4,该实例（n,W）就是求环游4个城市(1,2,3,4)且代价和最小的周游路线，其中权矩阵W给出了4个城市之间的距离（代价），Wij表示由城市i到城市j的距离（代价）。语言L<G,Σ>的识别问题其中G为文法，Σ为一字符集。L(G)为Σ上由G生成的语言，L(G)∈Σ*，Σ*表示由Σ中的字符组成的所有字符串集合。语言L的识别问题{G,Σ,ω|ω∈Σ*}的一个实例ω∈Σ*，识别算法判断ω∈L(G)是否成立。算法研究对象：问题。问题由所有实例组成。一般对于问题P，总有其相应的实例集I，那么，一个算法A是问题P的算法，意味着把P的任一实例input∈I作为A的输入，都能得到问题P的正确的输出。一个问题可以有许多个不同的算法。1.2.3算法与程序程序(Program)可以用来描述算法，同一个算法可以用不同的语言编写的程序来描述。程序不一定是算法。程序设计可以分为四个层次：算法、方法学、语言和工具。

抽象级更新速度算法程序设计方法程序设计语言编程工具1.3算法的评估1.3.1正确性算法的正确性是评估的前提。有些算法，特别是一些十分精致巧妙的算法，其正确性需要证明，有的证明难度较大，例如无向图单源最短路径问题的Dijkstra算法，构造最优二分搜索树的动态规划算法的Knuth改进。有些算法，其正确性是明显的，例如：算法1.2选择排序算法SelectSort

1.3.2时间代价

评估算法的时间代价是算法分析的核心。算法的时间代价的大小用算法的时间复杂度(TimeComplexity)来度量。但要考虑到以下因素：

·用来运行算法的计算机的性能的差别；

·算法运行的软件平台和描述语言的差别；

·算法所解的问题是多种多样的；

·同一问题的算法对不同的实例，所花的时间开销也可能有很大的差别。1.3.3空间代价

空间消耗是衡量算法优劣的另一重要因素。不过算法的空间复杂性分析的重要性常常列于时间复杂性分析之后。在许多应用问题中，人们往往以适当增加算法的空间代价来减少时间代价。空间复杂度的分析类似于时间复杂度的分析，其有关的概念和方法几乎是平行的。1.3.4最优性

一个算法不一定是最优的。所谓最优算法是指在某一种度量标准之下，优于该问题的所有（可能的）算法。一般，某一问题的最优算法是指在时间复杂度的计算基础上的最优性。算法1.3求n个不同整数中的最大元MaxElement对于任何n个整数，要求其最大元，至少需进行n-1次比较，因此，可以说上述算法Max(S)是最优的。为了证明在n个不同元中求出最大元，至少需n-1次比较，可以把n个元划分为三个动态的组A,B,C。

A：未知元的集合

B：已肯定不是最大元的元素集合

C：最大元的集合。

不难证明，任何一个通过二元比较求最大元的算法都是要从三个集合的元数为(n,0,0)（即|A|=n,|B|=0,|C|=0）状态开始，经过运行，最终达到(0,n-1,1)状态，即：

这实际上是元素从集合A向B和C中移动的过程。但每次两个元的比较至多只可把一个较小的元素从集合A移至集合B。因此，任何最大元算法至少要进行n-1次比较，从而证明了上述最大元算法Max(A)是最优的。

ABCABC|A|=n|B|=0|C|=0|A|=n-1|B|=0|C|=1|A|=n-2|B|=1|C|=11.4算法理论的基本概念1.4.1基本操作算法的时间代价的度量不应依赖于算法运行的硬件和软件平台，因此不能从下面几个方面来度量时间代价：

•算法运行的实际执行时间；

•运行过程中所执行的指令条数；(不同语言,不同编程风格)•运行过程中程序循环的次数。(循环体差别大)

因此需要引入基本操作的概念来度量时间代价。基本操作就是指算法运行中起主要作用且花费最多时间的操作。例如：两个实数矩阵的乘法问题中，矩阵的实数元素之间的数乘是基本操作；对N个整数进行排序的算法中，整数间的比较是基本操作；移动操作；移动与比较。1.4.2问题实例长度

算法运行的时间（或空间）代价还与问题实例长度，即输入规模有关，这称为问题实例长度。

问题实例长度是指作为该问题的一个实例的输入规模大小。例如：

排序问题：问题实例长度是待排序元素序列的长度n；

矩阵乘积：问题实例长度是矩阵（指n阶方阵）的阶数n；

图的最短路径问题：图G=<V,E>的顶点数n=||V||和边数m=||E||是问题实例长度；

字符串匹配问题：文本T的长度n，亦可再加上样本P的长度m为问题实例长度。算法的时间（或空间）代价由该算法用于问题长度为n的实例所需要的基本操作次数来刻画。一般一个算法的时间复杂度用函数T(n)(或T(n,m))表示，空间复杂度用S(n)表示。1.4.3复杂度的渐进性质算法的比较是根据复杂度函数的渐进性质的比较进行的。例如：算法A和算法B，其时间复杂度函数为TA(n)和TB(n)，在Fig.1.4中，虽然当n<n0时TB(n)<TA(n)，但在n>n0时，或说n充分大时(n->∞)，有TA(n)<TB(n)，因此认为算法A优于算法B。㊣算法B有条件优于算法A：在实际应用中问题规模是给定的1.4.4最坏情形和最好情形例：算法1.4插入排序算法Insertsortn=10时，有三种输入：正序：123456789109次比较逆序：1098765432145次比较（9+1）9/2随机：3745102961828次比较同一算法，相同的问题长度，不同的输入，其时间代价一般不同。因此在实际的算法分析中，复杂度函数值T(n)不是唯一的，在大多数情况下取其最大值，即最坏情形的时间（空间）复杂度。设Dn为问题P的所有长度为n的实例集合，输入实例I∈Dn

，||I||=n，而t(I)为用来解问题P的算法A在以I为输入时的执行代价（基本操作次数），则W(n)=MAX{t(I)}

I∈DnW(n)称为算法A的最坏情形(WorstCase)时间复杂度。类似的，还可以定义最好情形（BestCase）时间复杂度，B(n)=MIN{t(I)}---最好与最坏复杂度有何用,何时用?

I∈Dn

平均复杂度何时用

1.4.5平均情形和算法的期望复杂度设算法A的输入为I∈Dn的概率为P(I)，则

其中P(I)满足为实例输入I出现的概率，t(I)为算法A完成实例I的耗费值（即基本操作次数）。

期望复杂度比最坏情形复杂度更好的刻画了算法的性能，但是，由于Dn一般很大，P(I)和t(I)较难计算，因此，平均情形的复杂度分析比较难。例如：在数组L[1,…,n]中搜索，求使L[j]=X的位置j。算法1.5顺序搜索算法SeqSearch因为L[1,…,n]长度为n，不同的输入实例由X的值决定，实例集Dn由下列实例组成：（1）X在L中，共有n种情况：I1,…,In

，Ii表示X=L[i] (i=1,…,n)；（2）X不在L中，这时X有许多可能值，把它们统记为In+1

。因为当X=L[k]时，t(Ik)=k，(k=1,…,n)，X不在L中时，t(In+1)=n。这时W(n)容易计算：W(n)=MAX{t(Ik)|k=1,2,…,n,n+1}=n。但计算A(n)则应首先设定I在Dn中的分布：设X在L中的概率为q，故X不在L中的概率为1-q，假定X在L中，它等于L的n个元素是等可能的，即P(Ik)=Pk=q/n,(k=1,…,n),P(In+1)=Pn+1=1-q，当q=1，即已知X在L中，A(n)=(n+1)/2，q=1/2，即X有一半可能在L中，A(n)=3n/4+1/4。也就是说，在上面的假设条件下，我们的顺序搜索的平均代价大约是n/2次比较和3n/4次比较。1.4.6复杂度函数的表示

各种复杂度函数的表示方法大致可按表达的精确程度分为下面的三个等级:(何种情况下用相应的复杂度函数)

1.解析表达式。用解析表达式刻画复杂度函数是最精确的表达方式。例如·求n元中之最大元算法MaxElement的复杂度为T(n)=W(n)=A(n)=n–1。·顺序搜索算法的最坏情形时间复杂度为W(n)=n；在指定分布条件及q=1情形下的期望时间复杂度为

A(n)=(n+1)/2。2.阶（Order）表达式。为了简化算法复杂度分析的方法，往往只需计算当问题规模较大时算法的渐进复杂度的阶。定义1.1

称（复杂度）函数T(n)是O(f(n))的，即

T(n)=O(f(n))，如果存在常数c>0与n0

，当n>n0时有T(n)≤cf(n)。例如：T1(n)=(n+1)/2=O(n),T2(n)=3n2+4n+5=O(n2)定义1.2

称（复杂度）函数T(n)是Ω(f(n))的，即T(n)=Ω(f(n))，如果存在常数c>0与n0

，当n>n0

时有T(n)≥cf(n)。例如：T1(n)=(n+1)/2=Ω(n),T2(n)=3n2+4n+5=Ω(n2)定义1.3

称（复杂度）函数T(n)是θ(f(n))的，即T(n)=θ(f(n))，如果存在常数c1,c2>0与n0，当n>n0时有c1f(n)≥T(n)≥c2f(n)。例如：T1(n)=(n+1)/2=θ(n),T2(n)=3n2+4n+5=θ(n2)显然，如果T(n)=O(f(n))且T(n)=Ω(f(n))，则T(n)=θ(f(n))。3.多项式函数和指数函数。多项式函数指T(n)为自变量n的多项式函数，例如T1(n)=n/2+1/2，T2(n)=3n2+4n+5等。而指数函数如T3(n)=2n+5，T4(n)=3n/2–8等等，自变量n出现在