《算法与算法分析》PPT课件

《《算法与算法分析》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第一章绪论1.1引言1.2算法及算法分析（算法评价）1什么是算法？算法是对解决问题的方法的一种精确描述。并非所有问题都有算法，有些问题经研究可行，则可能有相应算法；而有些问题经研究不可行，则没有相应算法。因此，算法研究在某种意义上就是可行性研究。2算法的性质算法可以理解为动作序列的有限集合仅有一个初始动作每个动作的后继动作是确定的算法的终止表示问题得到解答或问题没有解答3算法是为了解决某类问题而规定的一个有限长的操作序列。一个算法必须满足以下五个重要特性：1．有穷性2．确定性3．可行性4．有输入5．有输出算法的性质41．有穷性对于任意一组合法输入值，在执行有穷步骤之后一定能结束，即：算法中的每

2、个步骤都能在有限时间内完成。2．确定性对于每种情况下所应执行的操作，在算法中都有确切的规定，使算法的执行者或阅读者都能明确其含义及如何执行。并且在任何条件下，算法都只有一条执行路径。53．可行性算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算有限次实现之。4．有输入作为算法加工对象的量值，通常体现为算法中的一组变量。有些输入量需要在算法执行过程中输入，而有的算法表面上可以没有输入，实际上已被嵌入算法之中。65．有输出它是一组与“输入”有确定关系的量值，是算法进行信息加工后得到的结果，这种确定关系即为算法的功能。7算法设计的原则设计算法时，通常应考虑达到以下目标：1．正确性2.可

3、读性3．健壮性4．高效率与低存储量需求81．正确性首先，算法应当满足以特定的“规格说明”方式给出的需求。其次，对算法是否“正确”的理解可以有以下四个层次：a．程序中不含语法错误；b．程序对于几组输入数据能够得出满足要求的结果；9c．程序对于精心选择的、典型、苛刻且带有刁难性的几组输入数据能够得出满足要求的结果；通常以第c层意义的正确性作为衡量一个算法是否合格的标准。d．程序对于一切合法的输入数据都能得出满足要求的结果；102.可读性算法主要是为了人的阅读与交流，其次才是为计算机执行，因此算法应该易于人的理解；另一方面，晦涩难读的程序易于隐藏较多错误而难以调试。113．健壮性当输入的数据非法时，

4、算法应当恰当地作出反映或进行相应处理，而不是产生莫名奇妙的输出结果。并且，处理出错的方法不应是中断程序的执行，而应是返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理。124．高效率与低存储量需求通常，效率指的是算法执行时间；存储量指的是算法执行过程中所需的最大存储空间，两者都与问题的规模有关。13第一章绪论1.1引言1.2算法及算法分析（算法评价）14算法分析与算法复杂度算法分析的任务是对设计出的每一个具体的算法，利用数学工具，讨论其复杂度，探讨具体算法对问题的适应性算法的复杂度分时间复杂度和空间复杂度。计算机理论科学中，按照计算复杂性研究问题求解的难易性，可把问题分为P类、NP

5、类和NP-完全类。15算法的效率对于一个问题通常有多种解法（算法），应该选择哪一种呢？计算机程序设计的核心有两个目标（有时它们互相冲突）设计一种容易理解、编码和调试的算法设计一种能有效利用计算机资源的算法16算法的效率(cont)目标1涉及到软件工程原理目标2涉及到数据结构与算法分析本课程主要讲的是与目标2有关的问题怎样度量算法的代价、效率呢？17如何度量效率?实验比较（运行程序）渐近算法分析AsymptoticAlgorithmAnalysis关键资源:影响运行时间的因素:对很多算法而言，运行时间依赖与输入的规模执行算法所需要的时间T写成输入规模n的函数，记为T(n)18怎样比较两种算法解决

6、问题的效率呢？实验比较用源程序分别实现这两种算法，然后输入适当的数据运行，测算两个程序各自的开销这是一种事后统计的方法渐近算法分析(asymptoticalgorithmanalysis)，简称算法分析(algorithmanalysis)可以估算出当问题规模变大时，一种算法及实现它的程序的效率和开销这是一种事前分析估算的方法19“规模”与“基本操作”判断算法性能的一个基本考虑是处理一定“规模”(size)的输入时该算法所需执行的“基本操作”(basicoperation)数“规模”一般是指输入量的数目比如，在排序问题中，问题的规模可以用被排序元素的个数来衡量20“规模”与“基本操作”（续）一

7、个“基本操作”必须具有这样的性质：完成该操作所需时间与操作数的具体取值无关在大多数高级语言中，下列操作是基本操作：赋值运算简单算术运算简单布尔运算简单I／O操作函数返回n个整数累加不是基本操作因为其代价依赖于n的值(即大小)21运行时间和增长率由于影响运行时间的最主要因素一般是输入的规模，所以经常把执行算法所需要的时间T写成输入规模n的函数，记为T(n)我们总是假设T(n)为非负值算法的增长率(g