第一章(算法和算法分析)

《第一章(算法和算法分析)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、解答341．有穷性对于任意一组合法输入值，3．可行性算法中的所有操作都必须足在执行有穷步骤之后一定能结束，即：够基本，都可以通过已经实现的基本操作算法中的每个步骤都能在有限时间内完成。运算有限次实现之。2．确定性对于每种情况下所应执行的4．有输入作为算法加工对象的量值，操作，在算法中都有确切的规定，使算法通常体现为算法中的一组变量。有些输入的执行者或阅读者都能明确其含义及如何量需要在算法执行过程中输入，而有的算执行。并且在任何条件下，算法都只有一法表面上可以没有输入，实际上已被嵌入条执行路径。算法之中。561算法设计的原则5．有输出它是一组与“输入”有确

3、设计算法时，通常应考虑达到以下目标：定关系的量值，是算法进行信息加1．正确性工后得到的结果，这种确定关系即2.可读性为算法的功能。3．健壮性4．高效率与低存储量需求781．正确性c．程序对于精心选择的、典型、苛刻且首先，算法应当满足以特定的“规格带有刁难性的几组输入数据能够得出满足说明”方式给出的需求。要求的结果；其次，对算法是否“正确”的理解可以d．程序对于一切合法的输入数据都能得有以下四个层次：出满足要求的结果；a．程序中不含语法错误；通常以第c层意义的正确性作为衡b．程序对于几组输入数据能够得出满足要求的结果；量一个算法是否合格的标准。9103．健

4、壮性2.可读性当输入的数据非法时，算法应当恰当算法主要是为了人的阅读与交流，地作出反映或进行相应处理，而不是产其次才是为计算机执行，因此算法应该易生莫名奇妙的输出结果。并且，处理出于人的理解；另一方面，晦涩难读的程序错的方法不应是中断程序的执行，而应易于隐藏较多错误而难以调试。是返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理。111224．高效率与低存储量需求&第一章绪论通常，效率指的是算法执行时间；1.1引言存储量指的是算法执行过程中所需的1.2数据结构的有关基本概念；1.3算法及算法分析（算法评价）最大存储空间，两者都与问题的规模有关

5、。1314算法分析与算法复杂度算法的效率•算法分析的任务是对设计出的每一个具体的算法，利用数学工具，讨论其对于一个问题通常有多种解法（算法），复杂度，探讨具体算法对问题的适应应该选择哪一种呢？性计算机程序设计的核心有两个目标（有时它们互相冲突）•算法的复杂度分时间复杂度和空间复1.设计一种容易理解、编码和调试的算法杂度。2.设计一种能有效利用计算机资源的算法•计算机理论科学中，按照计算复杂性研究问题求解的难易性，可把问题分为P类、NP类和NP-完全类。1516如何度量效率?算法的效率(cont)1.实验比较（运行程序）目标1涉及到软件工程原理2.渐近算法

6、分析AsymptoticAlgorithmAnalysis目标2涉及到数据结构与算法分析关键资源:本课程主要讲的是与目标2有关的问题影响运行时间的因素:怎样度量算法的代价、效率呢？对很多算法而言，运行时间依赖与输入的规模执行算法所需要的时间T写成输入规模n的函数，记为T(n)17183怎样比较两种算法解决问题的效“规模”与“基本操作”率呢？•实验比较–用源程序分别实现这两种算法，然后输入适•判断算法性能的一个基本考虑是处理一当的数据运行，测算两个程序各自的开销定“规模”(size)的输入时该算法所需执–这是一种事后统计的方法行的“基本操作”(basico

7、peration)数•渐近算法分析(asymptoticalgorithmanalysis)，简称算法分析(algorithm•“规模”一般是指输入量的数目analysis)–比如，在排序问题中，问题的规模可以用被–可以估算出当问题规模变大时，一种算法及排序元素的个数来衡量实现它的程序的效率和开销–这是一种事前分析估算的方法1920“规模”与“基本操作”（续）运行时间和增长率•一个“基本操作”必须具有这样的性质：完•由于影响运行时间的最主要因素一成该操作所需时间与操作数的具体取值般是输入的规模，所以经常把执行无关算法所需要的时间T写成输入规模n–在大多数

8、高级语言中，下列操作是基本操作：的函数，记为T(n)•赋值运算–我们总是假设T(