算法的基本概念

《算法的基本概念》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第1章算法的基本概念第1章算法的基本概念计算机系统中的任何软件，都是由大大小小的各种软件组成部分构成，各自按照特定的算法来实现，算法的好坏直接决定所实现软件性能的优劣。用什么方法来设计算法，所设计算法需要什么样的资源，需要多少运行时间、多少存储空间，如何判定一个算法的好坏，在实现一个软件时，都是必须予以解决的。计算机系统中的操作系统、语言编译系统、数据库管理系统以及各种各样的计算机应用系统中的软件，都必须用一个个具体的算法来实现。因此，算法设计与分析是计算机科学与技术的一个核心问题。1.1引言在20世纪50年代，西方某些著名的词典中，还未曾收录过算法（Algorithm）一词。

2、根据西方数学史家的考证，古代阿拉伯的一位学者写了一部名著，名字为“Kitābal-jabrWa’lmuqābJla”（《复原和化简的规则》），作者的署名是Abū‘AbdAllāhMuhammadibnMūsaal-Khwārizmī，从字面看，意思是“穆罕默德（Muhammad）的父亲，摩西（Moses）的儿子，Khwārizm地方的人”。后来，这部著作流传到了西方，结果，从作者署名中的al-Khwārizmī派生出Algorithm（算法）一词，而从作品名字中的al-jabr派生出Algebra（代数）一词。随着时间的推移，Algorithm（算法）这个词的含义，已经完全与它

3、原来的含义不同了。1.1.1算法的定义和特征欧几里德曾在他的著作中描述过求两个数的最大公因子的过程。20世纪50年代，欧几里德所描述的这个过程，被称为欧几里德算法，算法这个术语在学术上便具有了现在的含义。下面是这个算法的例子及它的一种描述。算法1.1欧几里德算法输入：正整数m,n输出：m,n的最大公因子1.inteuclid(intm,intn)2.{3.intr;4.do{5.r=m%n;6.m=n;·33·第1章算法的基本概念7.n=r;8.}while(r)9.returnm;10.}在此用一种类C语言来叙述最大公因子的求解过程。今后，在描述其他算法时，还可能结合一些自然

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

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

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

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