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

《第1章 算法的基本概念.doc》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

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

2、57年，西方著名的《韦伯斯特新世界词典》也未将其收录其中。据西方数学史家的考证，古代阿拉伯的一位学者写了一部名著——《Kitābal-jabrWa’lmuqābJla》（《复原和化简的规则》），作者的署名是Abū‘AbdAllāhMuhammadibnMūsaal-Khwārizmī。从字面上看，其含义是“穆罕默德（Muhammad）的父亲，摩西（Moses）的儿子，Khwārizm地方的人”。后来，这部著作流传到了西方，结果从作品名称中的al-jabr派生出Algebra（代数）一词；从作者署名中的al-Khwārizmī派生出Alg

3、orithm一词。随着时间的推移，Algorithm这个词的含义已变得面目全非了，成了本书要讨论的内容——算法。1.1.1算法的定义和特征欧几里得曾在他的著作中描述过求两个数的最大公因子的过程。20世纪50年代，欧几里得所描述的这个过程被称为EuclidesAlgorithmforgcd，国内将其翻译为“求最大公因子的欧几里得算法”，Algorithm（算法）这一术语在学术上具有了现在的含义。下面通过一个例子来认识一下该算法。算法1.1欧几里得算法输入：正整数m,n输出：m,n的最大公因子1.inteuclid(intm,intn)2.

4、{3.intr;4.do{5.r=m%n;6.m=n;7.n=r;8.}while(r)9.returnm;10.}在此用一种类C语言来叙述最大公因子的求解过程。今后在描述其他算法时，还可能结合一些自然语言的描述，以代替某些繁琐的具体细节，从而更好地说明算法的整体框架。同时，为了简明、直观地访问二维数组元素，假定在函数调用时，二维数组可以直接作为参数传递，在函数中可以动态地分配数组。读者可以很容易地用其他方法来消除这些假定。在算法的第5行，把除以的余数赋予；第6行把的值赋予；第7行把的值赋予；第8行判断是否为0，若非0，继续转到第5行进

5、行处理，若为0，就转到第9行处理；第9行返回，算法结束。按照上面这组规则，给定任意两个正整数，总能返回它们的最大公因子。读者可以自行证明该算法的正确性。根据上面这个例子，可以定义算法如下。定义1.1算法是解某一特定问题的一组有穷规则的集合。算法设计的先驱者唐纳德.E.克努特（DonaldE.Knuth）对算法的特征作了如下的描述：（1）有限性。算法在执行有限步之后必须终止。算法1.1中，对输入的任意正整数、，在除以的余数赋予之后，再通过赋予，从而使值变小。如此往复进行，最终或者使为0，或者使递减为1。这两种情况都最终使，而使算法终止。（

6、2）确定性。算法的每一个步骤都有精确的定义，要执行的每一个动作都是清晰的、无歧义的。例如，在算法1.1的第5行中，如果、是无理数，那么除以的余数是什么，就没有一个明确的界定。确定性的准则意味着必须确保在执行第5行时，和的值都是正整数。算法1.1中规定了、都是正整数，从而保证了后续各个步骤中都能确定地执行。（3）输入。一个算法有0个或多个输入，它是由外部提供的，作为算法开始执行前的初始值或初始状态。算法的输入是从特定的对象集合中抽取的。算法1.1中有两个输入、，就是从正整数集合中抽取的。（4）输出。一个算法有一个或多个输出，这些输出与输入

7、有着特定的关系，实际上是输入的某种函数。不同取值的输入，产生不同结果的输出。算法1.1中的输出是输入、的最大公约数。（5）能行性。算法的可行性指的是算法中有待实现的运算都是基本的运算，原则上可以由人们用纸和笔，在有限的时间里精确地完成。算法1.1用一个正整数来除另一个正整数、判断一个整数是否为0以及整数赋值等，这些运算都是能行的。因为整数可以用有限的方式表示，而且至少存在一种方法来完成一个整数除以另一个整数的运算。如果所涉及的数值必须由展开成无穷小数的实数来精确地完成，则这些运算就不是能行的了。必须注意到，在实际应用中，有限性的限制是不

8、够的。一个实用的算法，不仅要求步骤有限，同时也要求运行这些步骤所花费的时间是人们可以接受的。如果一个算法需要执行数以百亿亿计的运算步骤，从理论上说，它是有限的，最终可以结束。但是，以当代计算机每秒数亿次的运