1、第一章算法的概念1.11.1算法的概念和描述算法的概念和描述1.21.2算法的时间复杂度和空间复杂度算法的时间复杂度和空间复杂度1.1算法的概念和描述【1.1.11.1.1算法的概念算法的概念】算法是一系列解决问题的清晰指令，也就是对于符合一定规范的输入在有限步骤内求解某一问题所使用的一组定义明确的规则。通俗点说，就是计算机解题的过程。在这个过程中，无论是形成解题思路还是编写程序，都是在实施某种算法。前者是推理实现的算法，后者是操作实现的算法。这个定义可以用一幅简明的图来说明，如图1.1所示。一个算法应该具有以下五个重要的特征：有穷性：一个算法必须保证执行有限步之后结束，并且每一步都在有穷时间
2、内完成。确定性：算法的每一步骤都必须有确切的定义。输入：一个算法有零个或多个输入，以刻画运算对象的初始情况。输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的。可行性：算法应该是可行的，这意味着所有待实现的算法都是能够理解和实现的，并可通过有限次运算完成。为了阐明算法的概念，本节将以三种方法为例来解决同一个问题：计算两个整数的最大公约数。这些例子会帮助我们阐明以下几项要点：图图1.1 1.1 算法的概念算法的概念1.1算法的概念和描述算法的每一个步骤都必须没有歧义，不能有半点含糊。必须认真确定算法所处理的输入的值域。同一算法可以用几种不同的形式来描述。同一
3、问题，可能存在几种不同的算法。针对同一问题的算法可能会基于完全不同的解题思路而且解题速度也会有显著不同。还记得最大公约数的定义吗?将两个不全为0的非负整数m和n的最大公约数记为gcd（m，n），代表能够整除（即余数为0）m和n的最大正整数。亚历山大的欧几里得（公元前3世纪）所著的几何原本，以系统论述几何学而著称，在其中的一卷里，他简要地描述了一个最大公约数算法。用现代数学的术语来表述，欧几里得算法基于的方法重复应用下列等式，直到 m mod n 等于0。gcd（m，n）=gcd（n，m mod n）（m mod n表示 m 除以 n 之后的余数）因为gcd（m，0）=m，m 最后的取值也就是
4、m 和 n 的初值的最大公约数。举例来说，gcd（60，24）可以这样计算：gcd(60,24)=gcd(24,60 mod 24)=gcd(24,12)=gcd(12,24 mod 12)=gcd(12,0)=12下面是该算法的一个更加结构化的描述。1.1算法的概念和描述用于计算用于计算 gcdgcd（m m，n n）的欧几里得算法：）的欧几里得算法：第一步：如果 n=0，返回 m的值作为结果，同时函数结束；否则，进入第二步。第二步：m 除以 n，将余数赋给 r。第三步：将 n 的值赋给 m，将r 的值赋给 n，返回第一步。我们也可以使用伪代码来描述这个算法：算法 Euclid（m，n）/使
5、用欧几里得算法计算gcd（m，n）/输入两个不全为0的非负整数m，n/输出m，n的最大公约数while n0do rmmodnmnnrreturn m上面的伪代码也可以用流程图来加以描述，如图1.2所示。图图1.2 1.2 欧几里得算法的流程图欧几里得算法的流程图1.1算法的概念和描述我们怎么知道欧几里得算法最终一定会结束呢？通过观察，我们发现，每经过一次循环，参加运算的两个算子中的后一个都会变得更小，而且绝对不会变成负数。确实，下一次循环时，n的新值是m mod n，这个值总是比n小。所以，第二个算子的值最终会变成0，此时，这个算法也就停止了。就像其他许多问题样，最大公约数问题也有多种算法。
6、让我们看看解这个问题的另外两种方法。第个方法只基于最大公约数的定义；m和n的最大公约数就是能够同时整除它们的最大正整数。显然，这样一个公约数不会大干两数中的较小者，因此，我们先有：t=minm，n。现在可以开始检查t是否能够整除m和n：如果能，t就是最大公约数；如果不能，我们就将t减1，然后继续尝试（我们如何确定该算法最终一定会结束呢?）。例如，对于60和24这两个数来说，该算法会先尝试24，然后是23，这样一值尝试到12，算法就结束了。我们给这种算法命名为连续整数检测算法，下面是该算法的具体描述。用于计算gcd（m，n）的连续整数检测算法第一步将minm，n的值赋给t。第二步m除以t，如果余
7、数为0，进入第三步；否则，进入第四步。第三步n除以t，如果余数为0，返回t的值作为结果；否则，进入第四步。第四步把t的值减1。返回第二步。1.1算法的概念和描述注意：和欧几里得算法不同，按照这个算法的当前形式，当它的个输入为0时，计算出来的结果是错误的。这个例子说明了为什么必须认真、清晰地规定算法输入的值域。求最大公约数的第三种方法，我们应该在中学时就很熟悉了。中学里计算gcd（m，n）的方法：第一步：找到m的所有质因数。第二步：找到n的所有质因数。第三步：从第一步和第二步求得的质因数分解式中找出所有的公因数（如果P是一个公因数，而且在m和n的质因数分解式分别出现过Pm和pn次，那么应该将P重
8、复minpm，pn次）。第四步：将第三步中找到的公因数相乘，其结果作为给定数m和n的最大公约数。这样，对于60和24这两个数，我们得到：60=223524=2223 gcd(60,24)=223=12我们能够看到，第三种方法比欧几里得算法要复杂得多，也慢得多。撇开低劣的性能不谈，以这种形式表述的中学求解过程还不能称为一个真正意义上的算法。为什么?因为其中求质因数的步骤并没有明确定义。1.1算法的概念和描述【1.1.21.1.2算法的描述算法的描述】上一节中，我们已经用文字、伪代码及流程图分别描述了欧几里得算法。这是当今描述算法的三种最常用的做法。使用自然语言描述算法显然很有吸引力，但是自然语言
9、固有的不严密性使得要简单清晰地描述算法变得很困难。不过，这也是我们在学习算法的过程中需要努力掌握的一个重要技巧。伪代码是自然语言和类编程语言组成的混合结构。伪代码往往比自然语言更精确，而且用伪代码描述的算法通常会更简洁。令人惊讶的是，计算机科学家从来没有就伪代码的形式达成过共识，而是让教材的作者去设计他们自己的方言。幸运的是，这些方言彼此十分相似，任何熟悉一门现代编程语言的人都完全能够理解。在计算机应用早期，描述算法的主要工具是流程图。流程图使用一系列相连的几何图形来描述算法，几何图形内部包含对算法步骤的描述。实践证明，除了一些非常简单的算法以外，这种表示方法使用起来非常不便。如今，我们只能在
10、早期的算法教材里找到它的踪影。本书选择的描述方式力求不给读者带来困难，出于对简单性的偏好，我们忽略了对变量的定义，并使用了缩进来表示for、if和while语句的作用域。正像大家在前一节里看到的那样，我们将使用箭头“”表示赋值操作，用双斜线“表示注释。1.2 算法的时间复杂度和空间复杂度【1.2.11.2.1算法的评价算法的评价】这正是我们本节要讨论的问题算法的复杂度，即估计、评价算法运行时所需要花费的时间及空间。算法的时间复杂度和空间复杂度合称为算法的复杂度。那么，算法一旦确定，如何计算它的复杂度，衡量其优劣呢?通常从下面几个方面来考虑：（1）正确性：也称有效性，是指算法能满足具体问题的要求
11、。即对任何合法的输入，算法都会得出正确的结果。确认正确性的根本方法是进行形式化的证明。但对一些较复杂的问题，这是一件相当困难的事。许多计算机科学工作者正致力于这方面的研究，目前尚处于初级阶段。因此，实际中常常用测试的方法验证算法的正确性。测试是指用精心选定的输入（测试数据）去运行算法，检查其结果是否正确。但正如著名的计算机科学家E.Dijkstra所说的那样，测试只能指出有错误，而不能指出不存在错误。（2）可读性：指算法被理解的难易程度。人们常把算法的可读性放在比较重要的位置，主要是因为晦涩难懂的算法不易交流和推广使用，也难以修改、扩展与调试，而且可能隐藏较多的错误。可读性实质上强调的是越简单
12、的东西越美。1.2 算法的时间复杂度和空间复杂度（3）健壮性：对非法输入的抵抗能力。它强调的是：如果输入非法数据，算法应能加以识别并做出处理，而不是产生误操作或陷入瘫痪。（4）时间复杂度与空间复杂度。时间复杂度是算法的计算复杂性的时间度量，粗略地讲，就是该算法的运行时间。同一个问题，不同的算法可能有不同的时间复杂度。问题规模较大时，时间复杂度就变得十分重要。尽管计算机的运行速度提高很快，但这种提高无法满足问题规模加大带来的速度要求。所以追求高速算法仍然是件重要的事情。空间复杂度是指算法运行所需的存储空间的多少。相比起来，人们一般会更多地关注算法的时间复杂度，但这并不是因为计算机的存储空间是海量
13、的，而是由人们面临的问题的本质决定的。时间复杂度与空间复杂度往往是一对矛盾。常常可以用空间换取速度，反之亦然。1.2 算法的时间复杂度和空间复杂度【1.2.21.2.2算法的时间复杂度算法的时间复杂度】给定一个算法，如何确定该算法的时间复杂度呢?我们可以采用事后统计的办法得出执行算法所用的具体时间。因为很多计算机都有这种计时的功能，甚至可以获取精确到毫秒级的统计数据。但这种办法有两个缺陷：第一，必须先运行才能分辨出算法的好坏;第二，所得的时间的统计量过分依赖于计算机的硬件、软件等环境因素，这些因素容易掩盖算法本身的优劣，因为一个笨拙的算法在先进的大型机上运行可能比一个同功能的优化算法在微型机上
14、运行更省时间。因此，人们常常对算法进行事前的时间估算。可利用语句的频度和算法的渐进时间复杂度这两个与软、硬件无关的度量来讨论算法执行的时间消耗。设n称为问题的规模，当n不断变化时，算法中的基本语句执行的频度（我们且称为时间频度）T（n）也会不断变化。一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T（n）表示，若有某个辅助函数f（n），使得当n趋近于无穷大时，T（n）/f（n）的极限值为不等于零的常数，则称f（n）是T（n）的同数量级函数。记作T（n）=O（f(n)），称O（f(n)）为算法的渐进时间复杂度，简称时间复杂度。时间频度不同，但时间复杂度可能相同。如：T（n）=n
15、3n+4与T（n）=4n2n1它们的频度不同，但时间复杂度相同，都为O（n）。1.2 算法的时间复杂度和空间复杂度用两个算法A1和A2来求解同一问题，时间复杂度分别是T1（n）=100n，T2（n）=5n3。（1）当输入量nT2（n），后者花费的时间较少。（2）随着问题规模n的增大，两个算法的时间开销之比5n3/100n=n/20亦随着增大。即当问题规模较大时，算法Al比算法A要有效得多。它们的渐近时间复杂度O（n）和O（n）从宏观上评价了这两个算法在时间方面的质量。在算法分析时，往往对算法的时间复杂度和渐近时间复杂度不予区分，而经常是将渐近时间复杂度T（n）=O（f（n）简称为时间复杂度，其
16、中的f（n）一般是算法中频度最大的语句的频度。研究算法的时间复杂度，通常考虑的是算法在最坏情况下的时间复杂度。称为最坏时间复杂度。一般不特别说明，讨论的时间复杂度均是最坏情况下的时间复杂度。这样做的原因是;最坏情况下的时间复杂度T（n）=O（n），是算法在任何输入实例上运行时间的上界，即它表示对于任何输入实例，该算法的运行时间不可能大于O（n）。另一个衡量算法复杂度的指标是平均时间复杂度，它是指所有可能的输入实例均以等概率出现的情况下，算法的期望运行时间。1.2 算法的时间复杂度和空间复杂度1.2 算法的时间复杂度和空间复杂度1.2 算法的时间复杂度和空间复杂度1.2 算法的时间复杂度和空间复
17、杂度（4）算法的时间复杂度不仅仅依赖于问题的规模，还与输入实例的初始状态有关。例如：i=1；while(in)and(xai)#i=i+1；if ai=x then return(i)此程序段中语句#的频度不仅是 n的函数，而且与x及数组a 中各元素的具体值有关，在这种情况下，通常按最坏的情况考虑。由于 while 循环执行的最大次数为 n1，则语句#的频度的最大值为 f（n）=n1，则认为此程序段的时间复杂度为 T（n）=O（n）。（5）递归算法的频度不容易估算，须由递推公式计算求得。其基本方法是：方程右边较小的项根据定义被依次替代，如此反复扩展，直到得到一个没有递归式的完整数列，从而将复杂
18、的递归问题转化为了新的求和问题。以有名的 Hanoi 塔问题为例，其解是一个递归形式的算法：voidhanoi（int n,char A,char B,char C)if(n=1)move(n,A,C)；elsehanoi(n1,A,C,B)；move(n,A,C)；hanoi(n-1,B,A,C)；1.2 算法的时间复杂度和空间复杂度显见问题的规模是n，move（n，A，C）语句的频度为1，若整个算法的频度为f（n），则递归调用hanoi（n1，A，C，B）和hanoi（n1，B，A，C）语句的频度应为f（n一1），于是有f(n)=f(n1)1f(n1)即f(n)=2f(n1)1,进行递推，
19、有f(n)=2(2f(n2)1)1=4f(n2)3=4(2f(n3)1)3=8f（n一3）十7=2kf(nk)2k1当n=k1时，f（n）=2n1f（1）2n11。f（1）是n=1时算法的频度，它只有move（n，A，C）语句，其值为1。最后得到f（n）=2n1。时间复杂度T（n）=O（2n）。1.2 算法的时间复杂度和空间复杂度总之，频度和时间复杂度虽不能精确地确定一个算法或程序的执行时间，但可以让人们知道随着问题的规模增大，算法耗用时间的增长趋势。由于讨论算法的好坏不是针对某个特定大小的问题（这样做本身没有意义），因此，时间复杂度对算法来说是一个较恰当的量度。较常见的时间复杂度有O（1）（
20、常量型）、O（n）、O（n）、O（nk）（多项式型）、O（lbn）、O（nlbn）（对数型）和O（n!）（阶乘型）。显然，时间复杂度为O（2n）或O（en）的指数型算法的效率极低，在n较大时无法实用。如图1.3所示表明了各种时间复杂度的增长率。图图1.3 1.3 各种时间复杂度的增长率各种时间复杂度的增长率1.2 算法的时间复杂度和空间复杂度表1.1是我们所熟悉的各种排序算法的复杂度，读者可以分析思考。表表1.1 1.1 常用排序算法的时间复杂度和空间复杂度常用排序算法的时间复杂度和空间复杂度实践中我们可以把事前估算和事后统计两种办法结合起来使用，例如，若上机运行一个1010矩阵模型，执行时间
21、为12ms，则由算法的时间复杂度T（n）=O（n）可估算一个3131矩阵自乘的时间大约为（31/10）312ms358ms。这种办法很有实用价值，它用小模型可推得大尺寸问题的耗用机时。1.2 算法的时间复杂度和空间复杂度1.2 算法的时间复杂度和空间复杂度可见，这个简单的递归算法虽然正确，但却毫无效率。那么，fibl算法能改进吗?首先，我们分析fib1算法为什么如此之慢呢?如图1.4所示提示了由一个单独的fib1（n）调用过程触发的一系列递归操作。请注意很多计算步骤都是重复的！图图1.4 fib11.4 fib1（n n）递归调用的扩张过程）递归调用的扩张过程1.2 算法的时间复杂度和空间复杂
22、度正是由于重复计算才导致了fibl算法如此之慢。一种更合理的算法是随时存储中间计算结果F0，F1，Fn-1的值。void fib2(int n)if(n=0)return 0；f0=0；f1=1；for i=2 to n do fi=fi1+fi2；return fn；与 fibl 算法一样，由于该算法直接应用了Fn 的定义，其正确性是显而易见的。那么它的时间复杂度如何呢?由于其内层循环内包含了一个单独的操作，并且执行了n1次，因此，fib2的操作次数n是线性的。这就是说，现在我们从 fibl的指数时间降至 fib2 的多项式时间，我们在时间复杂度上取得了巨大的突破。现在我们完全可以在可接受的
23、时间内计算F200，甚至更大的n了。由此可见，一个好的算法将使问题的解决变得完全不同。1.2 算法的时间复杂度和空间复杂度【1.2.31.2.3算法的空间复杂度算法的空间复杂度】空间复杂度（SpaceComplexity）是对一个算法在运行过程中临时占用存储空间大小的量度，它也是问题规模n的函数。一个算法在计算机存储器上所占用的存储空间，包括存储算法本身所占用的存储空间，算法的输入/输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个方面。（1）固定部分。这部分空间的大小与输入/输出的数据的个数多少、数值无关。其主要包括指令空间（即代码空间）、数据空间（常量、简单变量）等所占的空
24、间。这部分属于静态空间。（2）可变空间。这部分空间主要包括动态分配的空间以及递归栈所需的空间等。这部分的空间大小与算法有关。一个算法所需的存储空间用f（n）表示。S（n）=O（f（n），其中n为问题的规模，S（n）表示空间复杂度。算法的输入/输出数据所占用的存储空间是由要解决的问题决定的，它不随着算法的不同而改变。存储算法本身所占用的存储空间与算法书写的长短成正比，要压缩这方面的存储空间，就必须编写出较短的算法。算法在运行过程中临时占用的存储空间随算法的不同而异，有的算法只需要占用少量的临时工作单元，而且不随问题规模的大小而改变，是节省存储空间的算法，可表示为O（1）。O（1）是说算法规模和临时变量数目无关，并不是说仅仅定义一个临时变量。
