第2章 算法分析

NiklausWirth（N.沃思）教授提出：Programs=Algorithm+DataStructures,第2章算法分析,算法,第2章算法分析,小结,算法分析,算法的定义,算法,算法的特点,算法的设计原则,算法是为求解一个问题需要遵循的、被清楚指定的简单指令的集合。,算法分析：对算法的性能进行分析，便于算法的比较和选用。时间复杂性分析和空间复杂性分析,算法的定义,输入输出有穷性确定性可行性,算法的特点,输入:作为算法加工对象的量值，通常体现为算法中的一组变量。,输出：它是一组与“输入”有确定关系的量值，是算法进行信息加工后得到的结果，这种确定关系即为算法的功能。,算法的特点,有穷性:对于任意一组合法输入值，在执行有穷步骤之后一定能结束。即：算法中的每个步骤都能在有限时间内完成。,算法的特点,确定性:对于每种情况下所应执行的操作，在算法中都有确切的规定，使算法的执行者或阅读者都能明确其含义及如何执行。并且在任何条件下，算法都只有一条执行路径。,算法的特点,可行性:算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算有限次实现之。,算法的特点,算法设计的原则,设计算法时，通常应考虑达到以下目标：,1正确性,2.可读性,3健壮性,4高效率与低存储量需求,首先，算法应当满足以特定的“规格说明”方式给出的需求。,其次，对算法是否“正确”的理解可以有以下四个层次：,a程序中不含语法错误,b程序对于几组输入数据能够得出满足要求的结果,算法设计的原则,c程序对于精心选择的、典型的、苛刻的且带有刁难性的几组输入数据能够得出满足要求的结果；,通常以第c层意义的正确性作为衡量一个算法是否合格的标准。,d程序对于一切合法的输入数据都能得出满足要求的结果；,算法设计的原则,算法主要是为了人的阅读与交流，其次才是为计算机执行。因此算法应该易于人的理解。另一方面，晦涩难读的程序易于隐藏较多错误而难以调试。,算法设计的原则,当输入的数据非法时，算法应当恰当地作出反映或进行相应处理，而不是产生莫名奇妙的输出结果。并且，处理出错的方法不应是中断程序的执行，而应是返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理。,算法设计的原则,高效率与低存储量需求,通常，效率指的是算法执行时间。存储量指的是算法执行过程中所需的最大存储空间。两者都与问题的规模有关。,算法设计的原则,算法分析：对算法的执行时间和需要的存储空间进行定性分析，以比较算法、改进算法。,算法分析,时间复杂度：算法的运行时间空间复杂度：算法运行所需的内存数量。,空间复杂度分析,算法的空间复杂度定义用S(N)表示。包含以下的部分：,1输入数据所占空间,2程序本身所占空间,3辅助变量所占空间,分析模型运行时间的计算运行时间中的对数,算法分析(教材2.3,2.4),分析模型-渐进表示法,任何一个算法都是由有限个基本运算（算术运算、逻辑运算和赋值操作）组成。,为了分析方便，将每种运算所需要的时间统一定义为1个时间单位。,算法需要的执行时间为所有运算个数之和,一般的讲，执行时间与问题规模n有关，是n的函数，记作T(n)，T(n)是非负递增函数,要分析的问题：,输入的大小,最好情形、平均情形、最坏情形。,Tbest(n)，Tworst(n)，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),分析模型-渐进表示法,使用函数描述渐进行为的通常方式为：10n+7=O(n)，100n3+3=O(n3)，8n3+4n2=O(n3),在渐进表示法中，复杂度中的最大项系数改为1，所以，当一次算法的步骤计数为5n2+n+4时，我们称其渐进复杂度为O(n2)。,如果存在正常数c和n0，当Nn0，T(N)cf(N)，则记为T(N)=O(f(N)。,O表示法的定义：,分析模型-渐进表示法,T1(n)=3n+13n+n4n,c=4，n0=1,T1(n)=O(n),T1(n)=3n+1,T(N)不快于f(N)的增长速度,分析模型-渐进表示法,T2(n)=O(log2(n)c=6,n0=28,T2(n)=5log2(n)+75log2(n)+85log2(n)+log2(n)n286log2(n),如果存在正常数c和n0，当Nn0，T(N)cf(N)，则记为T(N)=O(f(N)。,O表示法的定义：,T(N)不快于f(N)的增长速度,f(n)=(g(n)的表示意味着f(n)渐进大于或等于g(n)，因此从渐进的意义上来说，g(n)是f(n)的下界。,表示法,分析模型-渐进表示法,T1(n)=(n)T2(n)=(log2n),分析模型-渐进表示法,如果存在正常数c和n0，当Nn0，T(N)cg(N)，则记为T(N)=(g(N)。,表示法的定义：,T(N)不慢于g(N)的增长速度,T1(n)=3n+1,T2(n)=5log2(n)+7,f(n)=(g(n)的表示意味着f(n)渐进等于g(n)。,表示法,分析模型-渐进表示法,T(n)=(h(n)，如果存在正常数c1、c2和n0，nn0，c1h(n)T(n)c2h(n),规则1：用函数乘以或除以一个正常量不会改变它的阶3n2和0.2n2都在(n2),规则2：加上或减去较低阶的函数不会改变函数的阶2nn+log2n在(2n),分析模型-渐进表示法,例题1：T1(n)=3n+1与T2(n)=5log2n+7哪个快？,练习1,练习1,例题2：比较哪个速度快T1(n)=an2+blognT2(n)=cn+d,T1(n)=O(n2)T2(n)=O(n),例题3：比较哪个速度快T1(n)=an3+bn2+cT2(n)=n(n+1)/2,T1(n)=O(n3)T2(n)=0.5n2+0.5n=O(n2),练习1,例题4：比较哪个速度快T1(n)=an3T2(n)=n!,T1(n)=O(n3)T2(n)=n!=1*2*3*n1*2*2*2=2n-1=0.5*2n=O(2n),练习1,publicintsum(intn)intpartialSum;partialSum=0;for(inti=1;i=n;i+)partialSum+=i*i*i;returnpartialSum;,运行时间计算,共占用1+1+n+1+n+4n+1=6n+4，该方法的时间复杂度为O(n)。,publicintsum(intn)intpartialSum;partialSum=0;for(inti=1;i=n;i+)partialSum+=i*i*i;returnpartialSum;,运行时间计算一般法则,法则1for循环,一个for循环的运行时间最多是该for循环内部语句(包括测试)的运行时间乘以迭代的次数。,O(n),for(i=1;in;i+)for(j=0;jn;j+)k+;,运行时间计算一般法则,法则2嵌套的for循环,从里向外分析。在一组嵌套循环内部的一条语句总的运行时间为该语句的运行时间乘以该组所有的for循环的大小。,O(n2),for(i=0;in;i+)ai=0;for(i=1;i=left;i-)leftBorderSum+=ai;if(leftBorderSummaxLeftBorderSum)maxLeftBorderSum=leftBorderSum;,算法3：分治策略,运行时间计算举例,intmaxRightBorderSum=0,rightBorderSum=0;for(inti=center+1;imaxRightBorderSum)maxRightBorderSum=rightBorderSum;,算法3：分治策略,运行时间计算举例,算法3：分治策略,O(nlogn),分析程序：n=1,T(n)=1T(n)=O(n)+2T(n/2)=n+2T(n/2),n=1,T(1)=1T(2)=2+2T(1)=4=2*2T(3)=3+2T(1)=5T(4)=4+2T(2)=12=4*3T(8)=8+2T(4)=32=8*4,当n=2k时，T(n)=n*(k+1)=n*(logn+1)=O(nlogn),运行时间中的对数,某些分治算法将以O(nlogn)时间运行。此外，对数最常出现的规律法则可概括为：,如果一个算法用常数时间将问题的大小削减为其一部分（通常是1/2），那么该算法就是O(logn)。另一方面，如果使用常数时间只是把问题减少一个常数的数量(如将问题减1)，那么这种算法就是O(n)的。,运行时间中的对数-举例1,折半查找,给定一个整数X和整数A0，A1，AN-1，后者已经预先排序并在内存中，求下标i使得Ai=X，如果X不在数据中，则返回i=-1。,运行时间中的对数-举例1,折半查找,intlow=0,high=a.length-1;while(low0)high=m