第2章 算法分析ppt课件.ppt

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

1、NiklausWirth（N.沃思）教授提出：Programs=Algorithm+DataStructures第2章算法分析算法第2章算法分析小结算法分析算法的定义算法算法的特点算法的设计原则算法是为求解一个问题需要遵循的、被清楚指定的简单指令的集合。算法分析：对算法的性能进行分析，便于算法的比较和选用。时间复杂性分析和空间复杂性分析算法的定义输入输出有穷性确定性可行性算法的特点输入:作为算法加工对象的量值，通常体现为算法中的一组变量。输出：它是一组与“输入”有确定关系的量值，是算法进行信息加工后得到的结果，这种确定

2、关系即为算法的功能。算法的特点有穷性:对于任意一组合法输入值，在执行有穷步骤之后一定能结束。即：算法中的每个步骤都能在有限时间内完成。算法的特点确定性:对于每种情况下所应执行的操作，在算法中都有确切的规定，使算法的执行者或阅读者都能明确其含义及如何执行。并且在任何条件下，算法都只有一条执行路径。算法的特点可行性:算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算有限次实现之。算法的特点算法设计的原则设计算法时，通常应考虑达到以下目标：1．正确性2.可读性3．健壮性4．高效率与低存储量需求首先，算法应当满足

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

4、当输入的数据非法时，算法应当恰当地作出反映或进行相应处理，而不是产生莫名奇妙的输出结果。并且，处理出错的方法不应是中断程序的执行，而应是返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理。算法设计的原则高效率与低存储量需求通常，效率指的是算法执行时间。存储量指的是算法执行过程中所需的最大存储空间。两者都与问题的规模有关。算法设计的原则算法分析：对算法的执行时间和需要的存储空间进行定性分析，以比较算法、改进算法。算法分析时间复杂度：算法的运行时间空间复杂度：算法运行所需的内存数量。空间复杂度分析算法的空间复杂

5、度定义用S(N)表示。包含以下的部分：1．输入数据所占空间2．程序本身所占空间3．辅助变量所占空间分析模型运行时间的计算运行时间中的对数算法分析(教材2.3,2.4)分析模型-渐进表示法任何一个算法都是由有限个基本运算（算术运算、逻辑运算和赋值操作）组成。为了分析方便，将每种运算所需要的时间统一定义为1个时间单位。算法需要的执行时间为所有运算个数之和一般的讲，执行时间与问题规模n有关，是n的函数，记作T(n)，T(n)是非负递增函数要分析的问题：输入的大小最好情形、平均情形、最坏情形。Tbest(n)，Tworst(n

6、)，Taverage(n)Tbest(n)≤Taverage(n)≤Tworst(n)分析模型-渐进表示法渐进时间复杂性分析方法：1、确定算法的主要操作2、计算主要操作执行的次数3、一般的讲，执行次数是输入的函数4、根据函数的特点，得到函数所属的阶（order）分析模型-渐进表示法函数的分类：常数阶O(1)对数阶O(logn)线性阶O(n)线性对数阶O(nlogn)平方阶O(n2)指数阶O(2n)f(n)=O(g(n))的表示意味着f(n)渐进小于或等于g(n)，因此从渐进的意义上来说，g(n)是f(n)的上界。O表示

7、法分析模型-渐进表示法使用函数描述渐进行为的通常方式为：10n+7=O(n)，100n3+3=O(n3)，8n3+4n2=O(n3)在渐进表示法中，复杂度中的最大项系数改为1，所以，当一次算法的步骤计数为5n2+n+4时，我们称其渐进复杂度为O(n2)。T(n)=O(T(n))，如果存在正常数c和n0，当n>n0，T(n)≤cT(n)O表示法的定义：分析模型-渐进表示法T1(n)=3n+1≤3n+n≤4nc=4，n0=1T1(n)=O(n),T1(n)=3n+1T(n)=O(T(n))，如果存在正常数c和n0，当n>n

8、0，T(n)≤cT(n)O表示法的定义：分析模型-渐进表示法T2(n)=O(log2(n))c=6,n0=28T2(n)=5log2(n)+7≤5log2(n)+8≤5log2(n)+log2(n)n≥28≤6log2(n)f(n)=Ω(g(n))的表示意味着f(n)渐进大于或等于g(n)，因此从渐进的意义上来说，g(n)是f(n