第2章 算法分析.ppt

Niklaus Wirth（N.沃思）教授提出：Programs=Algorithm+Data Structures 第第2章章 算法分析算法分析算法算法第第2章章 算法分析算法分析小结小结算法分析算法分析算法的定义算法的定义算法算法算法的特点算法的特点算法的设计原则算法的设计原则算法算法是为求解一个问题需要遵循的、被清楚指定的简单指令的集合。指令的集合。算法分析：算法分析：对算法的性能进行分析，便于算法的比较和选用。时间复杂性分析和空间复杂性分析算法的定义算法的定义n输入 n输出n有穷性n确定性n可行性算法的特点算法的特点输入输入:作为算法加工对象的量值，通常体现为算法中的一组变量。输出：输出：它是一组与“输入”有确定关系的量值，是算法进行信息加工后得到的结果，这种确定关系即为算法的功能。算法的特点算法的特点有穷性有穷性:对于任意一组合法输入值，在执行有穷步骤有穷步骤之后一定能结束。即：算法中的每个步骤都能在有限时间有限时间内完成。算法的特点算法的特点确定性确定性:对于每种情况每种情况下所应执行的操作，在算法中都有确切确切的规定，使算法的执行者或阅读者都能明确其含义及如何执行。并且在任何条件下，算法都只有一并且在任何条件下，算法都只有一条执行路径。条执行路径。算法的特点算法的特点可行性可行性:算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算有限次实现之。算法的特点算法的特点算法设计的原则算法设计的原则设计算法时，通常应考虑达到以下目标：1正确性2.可读性3健壮性4高效率与低存储量需求 首先，算法应当满足以特定的“规格说明”方式给出的需求。其次，对算法是否“正确”的理解可以有以下四个层次：a程序中不含语法错误b程序对于几组输入数据能够得出满足要求的结果算法设计的原则算法设计的原则 c程序对于精心选择的、典型的、苛刻的且带有刁难性的几组输入数据能够得出满足要求的结果；通常以第 c 层意义的正确性作为衡量一个算法是否合格的标准。d程序对于一切合法的输入数据都能得出满足要求的结果；算法设计的原则算法设计的原则 算法主要是为了人的阅读与交流阅读与交流，其次才是为计算机执行。因此算法应该易于易于人的理解。理解。另一方面，晦涩难读的程序易于隐藏较多错误而难以调试。算法设计的原则算法设计的原则 当输入的数据非法时，算法应当恰当地作出反映或进行相应处理，而不是产生莫名奇妙的输出结果。并且，处理出错的方法不应是中断程序的执行，而应是返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理。算法设计的原则算法设计的原则高效率与低存储量需求高效率与低存储量需求 通常，效率指的是算法执行时间。存储量指的是算法执行过程中所需的最大存储空间。两者都与问题的规模有关。算法设计的原则算法设计的原则算法分析：对算法的执行时间和需要的存储空间进行定性分析，以比较算法、改进算法。算法分析算法分析时间复杂度：算法的运行时间空间复杂度：算法运行所需的内存数量。空间复杂度分析空间复杂度分析算法的空间复杂度定义用S(N)表示。包含以下的部分：1输入数据所占空间2程序本身所占空间3辅助变量所占空间分析模型分析模型运行时间的计算运行时间的计算运行时间中的对数运行时间中的对数算法分析算法分析(教材教材2.3,2.4)分析模型-渐进表示法n任何一个算法都是由有限个基本运算（算术运算、逻辑运算和赋值操作）组成。n为了分析方便，将每种运算所需要的时间统一定义为1个时间单位。n算法需要的执行时间为所有运算个数之和n一般的讲，执行时间与问题规模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+1 3n+n 4nc=4，n0=1T1(n)=O(n),T1(n)=3n+1T(N)不快于f(N)的增长速度分析模型-渐进表示法T2(n)=O(log2(n)c=6,n0=28T2(n)=5log2(n)+7 5log2(n)+8 5log2(n)+log2(n)n28 6log2(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+1T2(n)=5log2(n)+7f(n)=(g(n)的表示意味着的表示意味着f(n)渐进渐进等于等于g(n)。表示法表示法分析模型-渐进表示法T(n)=(h(n)，如果存在正常数c1、c2和n0，nn0，c1h(n)T(n)c2h(n)T(n)=(h(n)T(n)=O(h(n)且 T(n)=(h(n)规则1：用函数乘以或除以一个正常量不会改变它的阶 3n2 和0.2n2 都在(n2)规则2：加上或减去较低阶的函数不会改变函数的阶2n n+log2 n 在(2n)分析模型-渐进表示法 例题1：T1(n)=3n+1与T2(n)=5log2n+7哪个快？n12345678910T1471013161922252831T27121517192222232425n11121314151617181920T134374043464952555861T225262727272728282929练习练习1 1练习练习1 1例题2：比较哪个速度快T1(n)=an2+blognT2(n)=cn+dT1(n)=O(n2)T2(n)=O(n)例题3：比较哪个速度快T1(n)=an3+bn2+cT2(n)=n(n+1)/2T1(n)=O(n3)T2(n)=0.5n2+0.5n=O(n2)练习练习1 1例题4：比较哪个速度快T1(n)=an3T2(n)=n!T1(n)=O(n3)T2(n)=n!=1*2*3*n 1*2*2*2=2n-1=0.5*2n=O(2n)练习练习1 1public int sum(int n)int partialSum;partialSum=0;for(int i=1;i=n;i+)partialSum+=i*i*i;return partialSum;运行时间计算运行时间计算占1个时间单元初始化占1个时间单元，测试为n+1个时间单元，自加占n个时间单元每执行一次占用4个时间单元，执行n次，共占用4n个时间单元占1个时间单元共占用共占用1+1+n+1+n+4n+1=6n+4，该方法的时间复，该方法的时间复杂度为杂度为O(n)。public int sum(int n)int partialSum;partialSum=0;for(int i=1;i=n;i+)partialSum+=i*i*i;return partialSum;运行时间计算运行时间计算一般法则一般法则法则法则1 for循环循环一个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;in;i+)for(j=0;jn;j+)ai+=aj+i+j;运行时间计算运行时间计算一般法则一般法则法则法则3 顺序语句顺序语句将各个语句的运行时间求和。O(n)O(n2)O(n2)运行时间计算运行时间计算一般法则一般法则法则法则4 if/else语句语句对于程序片段if(condition)S1else S2一个if/else语句的运行时间从不超过判断的运行时间加上S1和S2中运行时间长的总的运行时间。运行时间计算运行时间计算举例举例最大子序列问题最大子序列问题给定整数A1,A2，,AN，求 的最大值。例如：输入为-2，11，-4，13，-5，-2答案为20运行时间计算运行时间计算举例举例for(int i=0;ia.length;i+)for(int j=i;ja.length;j+)int thisSum=0;for(int k=i;kmaxSum)maxSum=thisSum;算法算法1：穷举法：穷举法第一个循环：N第二个循环：N-i第三个循环：j-i+1O(n3)运行时间计算运行时间计算举例举例for(int i=0;ia.length;i+)int thisSum=0;for(int j=i;jmaxSum)maxSum=thisSum;算法算法2：O(n2)运行时间计算运行时间计算举例举例算法算法3：分治策略：分治策略4 -3 5 -2 -1 2 6 -24 -3 5 -2 -1 2 6 -24 045 0515662+6=84+7=11运行时间计算运行时间计算举例举例if(left=right)if(aleft0)return aleft;else return 0;int center=(left+right)/2;int maxLeftSum=maxSumRec(a,left,center);int maxRightSum=maxSumRec(a,center+1,right);算法算法3：分治策略：分治策略运行时间计算运行时间计算举例举例int maxLeftBorderSum=0,leftBorderSum=0;for(int i=center;i=left;i-)leftBorderSum+=ai;if(leftBorderSummaxLeftBorderSum)maxLeftBorderSum=leftBorderSum;算法算法3：分治策略：分治策略运行时间计算运行时间计算举例举例int maxRightBorderSum=0,rightBorderSum=0;for(int i=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 1折半查找折半查找给定一个整数给定一个整数X和整数和整数A0，A1，AN-1，后，后者已经预先排序并在内存中，求下标者已经预先排序并在内存中，求下标i使得使得Ai=X，如果，如果X不在数据中，则返回不在数据中，则返回i=-1。运行时间中的对数运行时间中的对数-举例举例1 1折半查找折半查找int low=0,high=a.length-1;while(low=high)int mid=(low+high)/2;if(pareTo(x)0)high=mid-1;else return mid;循环开始：循环开始：high-low=n-1循环结束：循环结束：high-low=-1每次循环后每次循环后high-low的值的值至少将该次循环前的值折至少将该次循环前的值折半；循环的次数最多为半；循环的次数最多为运行时间中的对数运行时间中的对数-举例举例1 1折半查找折半查找int low=0,high=a.length-1;while(low=high)int mid=(low+high)/2;if(pareTo(x)0)high=mid-1;else return mid;high-low=128，则各次循，则各次循环后环后high-low的最大值为的最大值为64,32,16,8,4,2,1,0，-1。因此运行时间为因此运行时间为O(logn)运行时间中的对数运行时间中的对数-举例举例2 2欧几里得算法欧几里得算法计算最大公因数：计算最大公因数：gcd(m,n)。假设。假设mnwhile(n!=0)long rem=m%n;m=n;n=rem;m=1989,n=1590余数序列为余数序列为399,393,6,3,0可以证明运行时间为可以证明运行时间为O(logn)小小 结结算法分析算法的概念 算法设计原则特性问题的规模n执行时间和空间是n的函数。，O，的含义如何求出T(n)的阶