算法和算法分析.doc

算法和算法分析.doc:..(Algorithm)描述,讨论算法是数据结构课程的重要内容Z-,它是指令的有限序列。它以一个或多个值作为输入,并产生一个或多个值作为输出。(1) 一个算法町以被认为是用來解决一个计算问题的工具。(2) 一个算法是一系列将输入转换为输出的计算步骤。例如,冇这样一个排序问题:将一个数字序列排序为非降序。该问题的形式建义由满足下述关系的输入输出序列构成:输入:数字序列Sl,a2,,,,em〉。输出:输出序列的一个枚举〈al',a2',„,an,〉使得al'Wa2'W,,Wa3‘对于一个输入实例〈31,41,59,26,41,58〉,排序算法应返回输出序列〈26,31,41,41,58,59)o(1) 输入实例输入实例:一个问题的输入实例是满足问题陈述中所给出的限制、为计算该问题的解所需要的所有输入构成的。(2) 正确的算法和不正确的算法若一个算法对于每个输入实例均能终止并给出正确的结果,则称该算法是止确的。止确的算法斛决了给定的计算问题。一个不止确的算法是指对某些输入实例不终止,或者虽然终止但给出的结果不是所渴望得到的答案,一般只考虑」E确的算法。算法是在冇限步骤内求解某一问题所使用的一组定义明确的规则。通俗点说,就是计算机解题的过程。在这个过程中,无论是形成解题思路还是编写程序,都是在实施某种算法。前者是推理实现的算法,后者是操作实现的算法。一个算法应该具有以下五个重要的特征:①有穷性:一个算法必须保证执彳亍有限步Z后结束;②确切性:算法的每一步骤必须冇确切的定义;③输入:一个算法有0个或多个输入,以刻画运算对象的初始情况,所谓0个输入是指算法木身定除了初始条件;④输出:一个算法有一个或多个输出,以反映对输入数据加工后的结果。没有输出的算法是毫无意义的:⑤可行性:算法原则上能够精确地运行,而且人们用笔和纸做冇限次运算后即可完成。、计算机程序语言或其它语言来说明,惟一的要求是该说明必须精确地描述计算过程。一般而言,描述算法最合适的语言是介于自然语言和程序语言Z间的伪语言。它的控制结构往往类似于Pascal、C等程序语言,但其中可使用任何表达能力强的方法使算法表达更加淸晰和简洁,而不至于陷入具体的程序语言的某些细节。从易于上机验证算法和提高实际程序设计能力考虑,采用C语言描述算法。(1)评价算法好坏的标准求解同一计算问题对能有许多不同的算法,究竟如何來评价这些算法的好坏以便从中选出较好的算法呢?选用的算法首先应该是〃正确〃的。此外,主要考虑如下三点:①执行算法所耗费的时间;②执行算法所耗费的存储空间,其中主要考虑辅助存储空间;③算法应易于理解,易于编码,易于调试等等。(2)算法性能选择—个占存储空间小、运行时间短、其它性能也好的算法是很难做到的。原因是上述要求有时相互抵触:耍节约算法的执行时间往往耍以牺牲史多的空间为代价;而为了节省空间可能要耗费更多的计算时间。因此我们只能根据具体情况有所侧重:①若该程序使用次数较少,则力求算法简明易懂;②对于反复多次使用的程序,应尽可能选用快速的算法;③若待解决的问题数据量极人,机器的存储空间较小,则相应算法主要考虑如何节省空间。一个算法所耗费的时间二算法屮每条语句的执行时间之和。每条语句的执行时间二语句的执行次数(即频度(FrequencyCount))X语句执彳亍一次所需吋间。,是评价算法优劣的重要依据。一个算法的复杂性的高低体现在运行该算法所需要的计算机资源的多少上面,所需的资源越多,我们就说该算法的复杂性越高;反Z,所需的资源越低,则该算法的复杂性越低。计算机的资源,最重要的是时间和空间(即存储器)资源。因而,算法的复杂性有时间复杂性和空间复杂性之分。不言而喻,对于任意给定的问题,设计出复朵性尽对能低的算法是我们在设计算法是追求的一个重要目标;另一方面,当给定的问题已有多种算法时,选择具中复杂性最低者,是我们在选用算法适应遵循的一个重要准则。因此,算法的复杂性分析对算法的设计或选用有着重要的指导意义和实用价值。关于算法的复杂性,有两个问题要弄清楚:;,怎样具体计算它的复杂性。算法的复杂性是算法运行所需要的计算机资源的量,需要的吋间资源的量称作时间复杂性,需要的空间(即存储器)资源的量称作空间复杂性。这个量应该集中反映算法中所采川的方法的效率,而从运行该算法的实际计算机中抽象出來。换