第1章 算法的基本概念.doc

《第1章 算法的基本概念.doc》由会员分享，可在线阅读，更多相关《第1章 算法的基本概念.doc（19页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第1章 算法的基本概念第1章 算法的基本概念计算机系统中的任何软件，都是由大大小小的各种程序模块组成，它们按照特定的算法来实现，算法的好坏直接决定了所实现软件性能的优劣。用什么方法来设计算法，所设计算法需要什么样的资源，需要多少运行时间、多少存储空间，如何判定一个算法的好坏在实现一个软件时，这些都是必须予以解决的。计算机系统中的操作系统、语言编译系统、数据库管理系统以及各种各样的计算机应用系统中的软件，都必须用一个个的具体算法来实现。因此，算法设计与分析是计算机科学与技术的一个核心问题。1.1 引 言“算法”这一术语是从Algorithm翻译而来的，但直到1957年，西方著名的韦伯斯特新世界词

2、典也未将其收录其中。据西方数学史家的考证，古代阿拉伯的一位学者写了一部名著Kitb al-jabr WalmuqbJla（复原和化简的规则），作者的署名是Ab Abd Allh Muhammad ibn Msa al-Khwrizm。从字面上看，其含义是“穆罕默德（Muhammad）的父亲，摩西（Moses）的儿子，Khwrizm地方的人”。后来，这部著作流传到了西方，结果从作品名称中的al-jabr派生出Algebra（代数）一词；从作者署名中的al-Khwrizm派生出Algorithm一词。随着时间的推移，Algorithm这个词的含义已变得面目全非了，成了本书要讨论的内容算法。1.1.

3、1 算法的定义和特征欧几里得曾在他的著作中描述过求两个数的最大公因子的过程。20世纪50年代，欧几里得所描述的这个过程被称为Euclides Algorithm for gcd，国内将其翻译为“求最大公因子的欧几里得算法”，Algorithm（算法）这一术语在学术上具有了现在的含义。下面通过一个例子来认识一下该算法。算法1.1 欧几里得算法输入：正整数m,n输出：m,n的最大公因子1. int euclid(int m,int n)2. 3. int r;4. do 5. r = m % n;6. m = n;7. n = r;8. while(r)9. return m;10. 在此用一种类

4、C语言来叙述最大公因子的求解过程。今后在描述其他算法时，还可能结合一些自然语言的描述，以代替某些繁琐的具体细节，从而更好地说明算法的整体框架。同时，为了简明、直观地访问二维数组元素，假定在函数调用时，二维数组可以直接作为参数传递，在函数中可以动态地分配数组。读者可以很容易地用其他方法来消除这些假定。在算法的第5行，把除以的余数赋予；第6行把的值赋予；第7行把的值赋予；第8行判断是否为0，若非0，继续转到第5行进行处理，若为0，就转到第9行处理；第9行返回，算法结束。按照上面这组规则，给定任意两个正整数，总能返回它们的最大公因子。读者可以自行证明该算法的正确性。根据上面这个例子，可以定义算法如下

5、。定义1.1 算法是解某一特定问题的一组有穷规则的集合。算法设计的先驱者唐纳德.E.克努特（Donald E.Knuth）对算法的特征作了如下的描述：（1）有限性。算法在执行有限步之后必须终止。算法1.1中，对输入的任意正整数、，在除以的余数赋予之后，再通过赋予，从而使值变小。如此往复进行，最终或者使为0，或者使递减为1。这两种情况都最终使，而使算法终止。（2）确定性。算法的每一个步骤都有精确的定义，要执行的每一个动作都是清晰的、无歧义的。例如，在算法1.1的第5行中，如果、是无理数，那么除以的余数是什么，就没有一个明确的界定。确定性的准则意味着必须确保在执行第5行时，和的值都是正整数。算法1

6、.1中规定了、都是正整数，从而保证了后续各个步骤中都能确定地执行。（3）输入。一个算法有0个或多个输入，它是由外部提供的，作为算法开始执行前的初始值或初始状态。算法的输入是从特定的对象集合中抽取的。算法1.1中有两个输入、，就是从正整数集合中抽取的。（4）输出。一个算法有一个或多个输出，这些输出与输入有着特定的关系，实际上是输入的某种函数。不同取值的输入，产生不同结果的输出。算法1.1中的输出是输入、的最大公约数。（5）能行性。算法的可行性指的是算法中有待实现的运算都是基本的运算，原则上可以由人们用纸和笔，在有限的时间里精确地完成。算法1.1用一个正整数来除另一个正整数、判断一个整数是否为0以

7、及整数赋值等，这些运算都是能行的。因为整数可以用有限的方式表示，而且至少存在一种方法来完成一个整数除以另一个整数的运算。如果所涉及的数值必须由展开成无穷小数的实数来精确地完成，则这些运算就不是能行的了。必须注意到，在实际应用中，有限性的限制是不够的。一个实用的算法，不仅要求步骤有限，同时也要求运行这些步骤所花费的时间是人们可以接受的。如果一个算法需要执行数以百亿亿计的运算步骤，从理论上说，它是有限的，最终可以结束。但是，以当代计算机每秒数亿次的运算速度，也必须运行数百年以上时间。这是人们所无法接受的，因而是不实用的算法。同时也应注意到上述的确定性，指的是算法要执行的每一个动作都是确定的，并非指

8、算法的执行结果是确定的。大多数算法不管在什么时候运行同一个实例，所得结果都一样，这种算法称为确定性算法；有些算法在不同的时间运行同一个实例，可能会得出不同的结果，这种算法称为不确定的算法或随机算法。算法设计的整个过程，可以包含对问题需求的说明、数学模型的拟制、算法的详细设计、算法的正确性验证、算法的实现、算法分析、程序测试和文档资料的编制。本书所关心的是串行算法的设计与分析，其他相关的内容以及并行算法可参考专门的书籍。这里只在涉及有关内容时，才对相应的内容进行论述。1.1.2 算法设计的例子，穷举法例1.1 百鸡问题。公元5世纪末，我国古代数学家张丘建在他所撰写的算经中，提出了这样一个问题：“

9、鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一。百钱买百鸡，问鸡翁、母、雏各几何？”意思是公鸡每只5元、母鸡每只3元、小鸡3只1元，用100元钱买100只鸡，求公鸡、母鸡、小鸡的只数。令为公鸡只数，为母鸡只数，为小鸡只数。根据题意，可列出下面的约束方程：（1.1.1）（1.1.2）（1.1.3）其中，运算符“/”为整除运算，“%”为求模运算。式（1.1.3）表示被3除余数为0。这类问题用解析法求解有困难，但可用穷举法来求解。穷举法就是从有限集合中，逐一列举集合的所有元素，对每一个元素逐一判断和处理，从而找出问题的解。上述百鸡问题中，、的可能取值范围为0100，对在此范围内的、的所有组合进行测试

10、，凡是满足上述3个约束方程的组合，都是问题的解。如果把问题转化为用元钱买只鸡，为任意正整数，则式（1.1.1）、式（1.1.2）变成：（1.1.4）（1.1.5）于是，可用下面的算法来实现。算法1.2 百鸡问题输入：所购买的3种鸡的总数目n输出：满足问题的解的数目k,公鸡、母鸡、小鸡的只数g、m、s1. void chicken_question(int n,int &k,int g,int m,int s)2. 3. int a,b,c;4. k = 0;5. for (a=0;a=n;a+) 6. for (b=0;b=n;b+) 7. for (c=0;c=n;c+) 8. if (a+

11、b+c=n)&(5*a+3*b+c/3=n)&(c%3=0) 9. gk = a;10. mk = b;11. sk = c;12. k+; 13. 14. 15. 16. 17. 该算法有三重循环，主要执行时间取决于第7行开始的内循环的循环体的执行次数。外循环的循环体执行次，中间循环的循环体执行次，内循环的循环体执行次。当时，内循环的循环体执行次数大于100万次。考虑到元钱只能买到只公鸡或只母鸡，因此有些组合可以不必考虑。而小鸡的只数又与公鸡及母鸡的只数相关，上述的内循环可以省去。这样算法1.2可以改为：算法1.3 改进的百鸡问题输入：所购买的3种鸡的总数目n输出：满足问题的解的数目k,公鸡

12、、母鸡、小鸡的只数g、m、s1. void chicken_problem(int n,int &k,int g,int m,int s)2. 3. int a,b,c,i,j;4. k = 0;5. i = n / 5;6. j = n / 3;7. for (a=0;a=i;a+) 8. for (b=0;b=j;b+) 9. c = n a b;10. if (5*a+3*b+c/3=n)&(c%3=0) 11. gk = a;12. mk = b;13. sk = c;14. k+;15. 16. 17. 18. 算法1.3有两重循环，主要执行时间取决于第8行开始的内循环，其循环体的执

13、行次数是。当时，内循环的循环体的执行次数为次。这与算法1.2的100万次比较起来，仅是原来的万分之七，有重大的改进。例1.2 货郎担问题。货郎担问题是一个经典问题。某售货员要到若干个城市销售货物，已知各城市之间的距离，要求售货员选择出发的城市及旅行路线，使每一个城市仅经过一次，最后回到原出发城市，而总路程最短。如果对任意数目的个城市，分别用1的数字编号，则这个问题归结为在有向赋权图中，寻找一条路径最短的哈密尔顿回路问题。其中，表示城市顶点；边表示城市到城市的距离，。这样，可以用图的邻接矩阵来表示各个城市之间的距离，该矩阵称为费用矩阵。售货员的每一条路线，对应于城市编号的一个排列。用一个数组来存

14、放这个排列中的数据，数组中的元素依次存放旅行路线中的城市编号。个城市共有个排列，于是售货员共有条路线可供选择。采用穷举法逐一计算每一条路线的费用，从中找出费用最小的路线，便可求出问题的解。下面是用穷举法解这个问题的算法。算法1.4 穷举法版本的货郎担问题输入：城市个数n,费用矩阵c输出：旅行路线t,最小费用min1 #define MAX_FLOAT_NUM /* z最大的浮点数 */2. void salesman_problem(int n,float &min,int t,float c)3. 4. int pn,i = 1;5. floatcost;6. min = MAX_FLOAT

15、_NUM;7. while (i = n!) 8. 产生n个城市的第i个排列于p;9. cost = 路线p的费用;10. if (cost min) 11. 把数组p的内容复制到数组t;12. min = cost;13. 14. i+;15. 16. 该算法的执行时间取决于第7行开始的while循环，它产生一个路线的城市排列，并计算该路线所需要的时间。这个循环的循环体共需执行次。假定每执行一次，需要1s时间，则整个算法的执行时间随的增长而增长的情况如表1.1所示。从中可以看到，当时，运行时间是3.62s，算法是可行的；当时，运行时间是1.72h（小时），还可以接受；当时，运行时间是242d

16、（天），就不实用了；当时，运行时间是7万7千多年，这样的算法就不可取了。在一些书籍中，把穷举法归类为蛮力法（brute force method）。它不采用巧妙的技术，而是针对问题的描述和所涉及的概念，用简单、直接的方法来求解，看起来有点笨拙和蛮劲，几乎什么问题都能解决，而算法的效率往往很差。但对某类特定问题，当设计一个更为高效的算法要花费很大的代价时，在规模较小的情况下，蛮力法却往往是一个简单、有效的方法。有时，经常用蛮力法作为准绳，来衡量同样问题更为高效的算法。表1.1 算法1.4的执行时间随n的增长而增长的情况nn! nn!nn!nn!5120s9362ms131.72h1711.27y

17、*6720s103.62s1424h18203y*75.04ms1139.9s1515d193857y*840.3ms12479.0s16242d2077146y*：时间单位年，即year的缩写。1.1.3 算法的复杂性分析上面的第1个例子，说明了改进算法的设计方法对提高算法性能的重要性。第2个例子，说明了对一个不太大的，采用穷举法来解诸如货郎担一类的问题，都是行不通的。可以采用哪些算法设计方法，来有效地解决现实生活中的问题，就是本书所要叙述的一个问题。但是，如果不是通过上面的简单分析，就不知道改进版的百鸡问题算法比原来的算法效率高很多；更不会知道用穷举法来解诸如货郎担一类的问题，甚至对一个不

18、太大的，都是不可行的。把这个问题再引申一下，对所设计的算法，如何说明它是有效的；或者，如果有两个解同样问题的算法，如何知道这一个算法比那一个算法更有效？这就提出了另一个问题，如何分析算法的效率。这是本书所要叙述的另一个问题。一般来说，可以用算法的复杂性来衡量一个算法的效率。对所设计的算法，普遍关心的是算法的执行时间和算法所需要的存储空间。因此，也把算法的复杂性划分为算法的时间复杂性和算法的空间复杂性。算法的时间复杂性越高，算法的执行时间越长；反之，执行时间越短。算法的空间复杂性越高，算法所需的存储空间越多；反之越少。在算法的复杂性分析中，对时间复杂性的分析考虑得更多。1.2 算法的时间复杂性在

19、讨论算法的时间复杂性时，要解决两个问题，即用什么来度量算法的复杂性？如何分析和计算算法的复杂性？下面就来讨论这两个问题。1.2.1 算法的输入规模和运行时间的阶假定百鸡问题的第一个算法，其最内部的循环体每执行一次，需1s时间。当时，第1个算法的这个循环体共需执行100万次，约需执行1s时间。第2个算法最内部的循环体每执行一次，也需1s时间。当时，第2个算法的这个循环体共需执行714次，约需714s。当的规模不大时，两个算法运行时间的差别不太明显。如果把的大小改为10000，即10000元买10000只鸡，以同样的计算机速度执行第1个算法，约需11d零13h；而用第2种算法，则需s，约为6.7s

20、。当的规模变大时，两个算法运行时间的差别就很悬殊了。从上面的分析以及对“货郎担”问题运行时间的分析，可以看到下面两点事实。u 算法的执行时间随问题规模的增大而增长，增长的速度随不同的算法而不同。当问题规模较小时，不同增长速度的两个算法，其执行时间的差别或许并不明显。而当规模较大时，这种差别就会变得非常大，甚至令人不能接受。u 没有一种方法能准确地计算算法的具体执行时间。这一事实主要是基于如下原因：算法的执行时间，不但取决于算法是怎样实现的，也取决于算法是用什么语言编写的，用什么编译系统实现的，编译系统所生成代码的质量如何，在什么样的计算机上执行的不同计算机的性能、速度各不相同，即使在同一台计算

21、机上执行，加法指令和乘法指令的执行时间差别也很大，人们无法对所有这些都作出准确的统计。即使能够对某台特定计算机的执行性能作出准确的统计，由于软件规模很大、结构复杂，运行状态变化很大，每一种运行状态都有各种各样的条件判断，难以预知依条件而执行的各种操作，其执行时间也就难以确定。实际上，在评估一个算法的性能时，并不需要对其执行时间作出准确的统计（除非在实时系统中，时间是非常关键的因素时）。这是因为人们在分析算法的性能，或把两个算法的性能进行比较时，对时间的估计是相对的，而不是绝对的。此外，对一个算法来说，人们不仅希望算法与实现它的语言无关、与执行它的计算机无关，同时也希望对算法运行时间的测量能适应

22、技术的进步。而且，人们所关心的并不是较小的输入规模，而是在很大的输入实例下算法的性能，也就是算法的运行时间随着输入规模的增长而增长的情况。于是，可以假定算法是在这样的计算模型下运行的：所有的操作数都具有相同的固定字长；所有操作的时间花费都是一个常数时间间隔。我们把这样的操作称为一个初等操作。例如，下面就是一些初等操作：算术运算、比较和逻辑运算、赋值运算等。这样，如果输入规模为，百鸡问题的第1个算法的时间花费可估计如下：第4行需执行1个操作；第5行需执行个操作；第6行需执行个操作；第7行需执行个操作；第8行需执行个操作；第9、10、11、12行循环一次各执行一个操作，执行与否取决于第8行的条件语

23、句。因此，这4行的执行时间不会超过。于是，百鸡问题的第一个算法的时间花费可估算如下：（1.2.1）当增大时，例如当时，算法的执行时间主要取决于式（1.2.1）的第1项，而第2、3、4项对执行时间的影响只有其几十万分之一，可以忽略不计。这时，第1项的常数20，随着的增大，对算法的执行时间也变得不重要。于是，可把写成：（1.2.2）这时，称的阶是。同样，对百鸡问题的第2个算法，也可进行如下估计：第4行执行1个操作；第5、6行各执行2个操作；第7行执行个操作；第8行执行个操作，第9行执行个操作，第10行执行个操作；第11、12、13、14行循环一次各执行一个操作，执行与否取决于第10行的条件语句。因

24、此，这4行的执行时间不会超过。上述的运算符“/”都表示整除操作。于是，百鸡问题的第2个算法的时间花费可估算如下：（1.2.3）同样，随着的增大，也可写成：（1.2.4）这时，称的阶是。把和进行比较，有：（1.2.5）当很大时，的作用很小。为了对这两个算法的效率进行比较，基于上面的观察，有如下的定义。定义1.2 设算法的执行时间为，如果存在，使得：（1.2.6）就称为算法的渐近时间复杂性。在算法分析中，往往对算法的时间复杂性和算法的渐近时间复杂性不加区分，并用后者来衡量一个算法的时间复杂性。在上面的例子中，百鸡问题的第1个算法的时间复杂性为，它的阶是。第2个算法的时间复杂性为，它的阶是。若时间复

25、杂性的阶为，当时，算法的渐近运行时间如表1.2所示。这里假定每一个操作是1ns。从表1.2中可以看到，当阶为、时，运行时间是以世纪衡量的。表1.2 不同时间复杂性下不同输入规模的运行时间nlognnnlognn2n32n83ns8ns24ns64ns512ns256ns164ns16ns64ns256ns4.096s65.536s325ns32ns160ns1.024s32.768s4294.967ms646ns64ns384ns4.096s262.144s5.85c1287ns128ns896ns16.384s1997.152sc续表nlognnnlognn2n32n2568ns256ns2

26、.048s65.536s16.777msc5129ns512ns4.608s262.144s134.218msc102410ns1.024s10.24s1048.576s1073.742msc204811ns2.048s22.528s4194.304s8589.935msc409612ns4.096s49.152s16.777ms68.719sc819213ns8.196s106.548s67.174ms549.752sc1638414ns16.384s229.376s268.435ms1.222hc3276815ns32.768s491.52s1073.742ms9.773hc6553616

27、ns65.536s1048.576s4294.967ms78.187hc13107217ns131.072s2228.224s17.180s25.983dc26214418ns262.144s4718.592s68.72s208dc52428819ns524.288s9961.472s274.88s4.569yc104857620ns1048.576s20971.52s1099.52s36.558yc说明：ns：纳秒；s：微秒；ms：毫秒；s：秒；h：小时；d：天；y：年；c：世纪。另一方面，假定是求解同一问题的6个算法，其时间复杂性的阶分别为，并假定在计算机和上运行这些算法，机的速度是机的1

28、0倍。若这些算法在机上运行时间为，可处理的输入规模是；在机上运行同样时间，可处理的输入规模扩大为，则对不同时间复杂性的算法，计算机速度提高后可处理的规模和的关系如表1.3所示。从表1.3中可以看到，当计算机速度提高10倍后，算法的求解规模可扩大10倍，而算法的求解规模只有微小增加，算法基本不变。可见，时间复杂性为或这类的算法，用提高计算机的运算速度来扩大它们的求解规模，其可能性是微乎其微的。表1.3中，前4种算法的时间复杂性与输入规模的一个确定的幂同阶，计算机运算速度的提高，可使解题规模以一个常数因子的倍数增加。这种算法的运行时间，可以用输入规模的一个多项式来表达，习惯上把这类算法称为多项式时

29、间算法，而把表1.3中的后两种算法称为指数时间算法。例如，上述百鸡问题的穷举算法是多项式时间算法，货郎担问题的穷举算法则是指数时间算法。一般把能够用多项式时间算法来求解的问题称为易解问题（easy problem），而用多项式时间算法求解的可能性非常微小的问题称为难解问题（difficalt problem）。货郎担问题就是一个难解问题。现实中有很多看起来容易而其实是难解的问题。例如，能否把一个整数集分割为两个子集和，使得中整数之和等于中整数之和。在公钥加密方案中就涉及这样的难解问题。表1.3 计算机速度提高后，不同算法复杂性求解规模的扩大情况算 法A1A2A3A4A5A6时间复杂性nn2和n

30、1的关系1.2.2 运行时间的上界，O记号百鸡问题的第1种算法和第2种算法所执行的初等操作数，分别至多为和。当的规模增大时，常数和对运行时间的影响不大。此时，如果用记号来表示这两个算法的运行时间的上界，则可分别写成和。在一般情况下，当输入规模大于或等于某个阈值时，算法运行时间的上界是某个正常数的倍，就称算法的运行时间至多是。记号的定义如下：定义1.3 令N为自然数集合，R+为正实数集合。函数f : NR+，函数g : NR+，若存在自然数和正常数，使得对所有的，都有，就称函数的阶至多是。因此，如果存在，则：即意味着这个定义表明：的增长最多像的增长那样快。这时称是的上界。例如，对百鸡问题的第2个

31、算法，由式（1.1.8）有：取=28，对，有：令，并令，有：所以，。这说明，百鸡问题的第2个算法，其运行时间的增长最多像那样快。这时，如果有一个新算法，其运行时间的上界低于以往解同一问题的所有其他算法的上界，就认为建立了一个解该问题所需时间的新上界。1.2.3 运行时间的下界，记号记号表示算法运行时间的上界，同样也可以用记号来表示算法运行时间的下界。仍以百鸡问题的第2个算法为例，第11、12、13、14行仅在条件成立时才执行，其执行次数未知。假定条件都不成立，这些语句一次也没有执行，该算法的执行时间至少为：当取时，存在常数，使得：这时，就认为百鸡问题的第2个算法的运行时间是。它表明了这个算法的

32、运行时间的下界。在一般情况下，当输入规模等于或大于某个阈值时，算法运行时间的下界是某一个正常数倍，就称算法的运行时间至少是。记号的定义如下：定义1.4 令N为自然数集合，R+为正实数集合。函数f : NR+，函数g : NR+，若存在自然数和正常数，使得对所有的，都有，就称函数的阶至少是。因此，如果存在，则：即意味着：这个记号表明一个算法的运行时间随规模的增长至少像那样快。它被广泛地用来表示解一个特定问题的任何算法的时间下界。例如，在个大小不同、顺序零乱的数据中，寻找一个最小的数据，至少需要次比较操作，因此它的阶是。以后还将说明：基于比较的排序算法，它的阶为，这也表明，再也不能设计出一个基于比

33、较的排序算法，其运行时间的阶能够低于。由记号和记号的定义，可得到下面的结论：结论1.1 的阶是，当且仅当的阶是。1.2.4 运行时间的准确界，记号百鸡问题的第2个算法的运行时间的上界是，下界是，这表明不管输入规模如何变化，该算法的运行时间都界于和之间。这时，用记号来表示这种情况，认为该算法的运行时间是。记号表明算法的运行时间有一个较准确的界，它可以准确到一个常数因子。在一般情况下，如果输入规模等于或大于某个阈值，算法的运行时间以为其下界，以为其上界，其中，就认为该算法的运行时间是。记号的定义如下：定义1.5 令N为自然数集合，R+为正实数集合。函数f : NR+，函数g : NR+，若存在自然

34、数和两个正常数，使得对所有的，都有：就称函数的阶是。因此，如果存在，则：即意味着：其中，是大于0的常数。由定义1.5，可得到下面的结论。结论1.2 如果，且，则。下面是一些函数的记号、记号和记号的例子。例1.3 常函数。令= 0，使得对= 1，对所有的有：所以，。同样：所以，。又因为：所以，。例1.4 线性函数。令= 0，当时，有，使得：所以，。令= 2，当时，有：所以，。同时，有：所以，。例1.5 平方函数。令= 0，当时，有，使得：所以，。令= 2，当时，有：所以，。同时，有：所以，。通过上面的例子，可得出下面的结论。结论1.3 令：则有：，且因此，有：例1.6 指数函数。令= 0，当时，

35、有，使得：所以，。令= 4，当时，有：所以，。同时，有：所以，。例1.7 对数函数。因为：令= 1，有：所以：。例1.7表明，在一般情况下，对任何正常数，都有：例1.8 函数因为：令= 1，有：所以，另一方面，假定是偶数，因此，令= 4，对所有的，都有：因此，有：所以，由此可以证明：1.2.5 O记号、记号、记号的性质记号、记号、记号具有如下一些性质：定理1.1（1）如果，且，则。（2）如果，且，则。证明：（1）由，存在某个正常数和，对所有的自然数，有；而由，存在某个正常数和，对所有的自然数，有。因此，存在正常数，对所有的自然数，有。所以，。（2）的证明类似（1）的证明。由定理1.1，可得到下

36、面的推论：推论1.1 如果，且，则。定理1.1和推论1.1说明记号、记号、记号具有传递性质。如果一个算法运行时间的上界是，而，则可以说是该算法运行时间的上界，但是更接近于它的上界。同样，如果一个算法运行时间的下界是，而，则可以说是该算法运行时间的下界，但是更接近于它的下界。定理1.2 对任意给定的函数和，存在函数和，满足，则。证明：由，存在某个正常数和，对所有的自然数，有。而由，存在某个正常数和，对所有的自然数，有。因此，对所有的自然数，有：令，则有：所以有：定理1.3 对任意给定的函数和，存在函数和，满足，则。证明：类似定理1.2的证明。由定理1.2，可以得到下面的推论。推论1.2 如果，则

37、。推论1.3 如果存在某个正常数，有函数，对所有的（ ），都有，则。定理1.4 如果和是非负函数，且，则。证明：显然，对所有的自然数，都有，因此，存在，使得。所以，有。此外，由，有。根据推论1.2，有。所以，。上述性质说明：如果某个算法是由若干个算法所组成的，而且其中每一个算法的时间复杂性都已经知道，那么就可以利用上述的性质来确定该算法的时间复杂性。1.2.6 复杂性类型和o记号不同的函数具有不同的复杂性，因此可对复杂性进行分类。定义1.6 令R是函数集合上的一个关系，R，有R则R是自反、对称、传递的等价关系，它诱导的等价类，称阶是的复杂性类型的等价类。因此，所有常函数的复杂性类型都是；所有线

38、性函数的复杂性类型都是；所有的2阶多项式函数的复杂性类型都是，如此等等。令函数，函数，则存在=1，使得对所有的，有。因此，。又因为：因此，则。所以，和是属于不同复杂性类型的函数。因为，且，由此可以推出。又因为：因此，即。所以，和是属于不同复杂性类型的函数。类似地，因为，而，所以，而。所以，。这两个函数也是属于不同复杂性类型的函数。为了表示两个函数具有不同类型的复杂性，可使用如下定义的记号。定义1.7 令N为自然数集合，R+为正实数集合。函数f : NR+，函数g : NR+，若存在自然数和正常数，使得对所有的，都有就称函数是。由此，如果存在，则即意味着这个定义表明，随着趋于非常大，相对于变得不

39、重要。由这个定义可以推出下面的结论：结论1.4 当且仅当而。例如：=，等价于=，而。同样，等价于，而。，等价于，而。可以用偏序关系来表示。例如，。在算法分析中，经常遇到如下一些类型的复杂性，它们的阶分别是1、。如果用“”来表示它们之间的复杂性关系，就可以组成如下的一个体系结构。习 题1算法有哪些特点？为什么说一个具备了所有特征的算法，不一定就是实用的算法？2证明算法1.1的正确性。3用穷举法求2500之间的所有亲密数对。所谓亲密数对，指的是如果的因子（包括1，不包括本身）之和为，的因子之和为，则和称为亲密数对。4算法的时间复杂性是如何度量的？5若 证明。6证明下面的关系成立：（1）（2）（3）（4）（5）7给定下列函数和，确定关系、是否成立，并证明。（1），（2），（3），（4），8给下面表格的空栏填上true或false。f(n) g(n)f=O(g)f=(g)参 考 文 献文献1给出了算法的定义和特征。文献2对算法的时间复杂性和空间复杂性问题，以及对算法运行时间的记号、记号、记号等记号的用法进行了讨论。记号、记号、记号以及记号的详细用法，可在文献3、4中看到。几乎所有的算法设计与分析书籍都涉及算法的时间复杂性和空间复杂性问题，以及对算法运行时间的记号、记号、记号的介绍。19