算法设计与分析王红梅第二版第2章_算法分析基础

海南大学信息科学技术学院CollegeofInformationScienceandTechnology,HainanUniversity算法设计与分析—本科生课程DesignandAnalysisofAlgorithm2019/12/18AlgorithmIntroduction2算法分析（AlgorithmAnalysis）算法复杂性（AlgorithmComplexity）算法复杂性的高低体现在运行该算法所需计算机资源的多少.计算机中最重要的两种资源是时间和空间资源。更确切地说，算法的复杂性是算法运行所需要的计算机资源的量，需要的时间资源的量称为时间复杂性；需要的空间资源的量称为空间复杂性，如下：时间复杂性（TimeComplexity）空间复杂性（SpaceComplexity）2.1算法的时间复杂性分析2019/12/18AlgorithmIntroduction3算法时间复杂性分析这是一种事前分析估算的方法，对算法所消耗资源的一种渐进分析方法。渐进分析：忽略具体机器、编程语言和编译器的影响，只关注在输入规模增大时算法运行时间的增长趋势。这大大降低了算法分析的难度，从数量级的角度评价算法的效率。C=F（N,I,A）T＝T（N）N为问题规模，I为算法输入，A为算法本身2.1算法的时间复杂性分析2019/12/18AlgorithmIntroduction4输入规模与基础语句精确地表示算法的运行时间函数常常是很困难的，考虑到算法分析的主要目的在于比较求解同一个问题的不同算法效率，为精简客观地反映一个算法的运行时间，用算法中基本语句的执行次数来度量算法的工作量。基本语句：执行次数与整个算法的执行次数正比的语句，对算法运行时间贡献最大，是算法中最重要的操作。2.1算法的时间复杂性分析for(i=1;i=n;i++)for(j=1;j=n;j++)x++;问题规模：n基本语句：x++例2.1对如下顺序查找算法，请找出输入规模和基本语句intSeqSearch(intA[],intn,intk){for(inti=0;in;i++)if(A[i]==k)break;if(i==n)return0;elsereturn(i+1);}2019/12/18AlgorithmIntroduction52.1算法的时间复杂性分析例2.2对如下起泡排序算法，请找出输入规模和基本语句voidSubbleSort(intr[],intn){intbound,exchange=n-1;while(exchange!=0){//当上一趟排序有记录交换时bound=exchange;exchange=0;for(intj=0;jbound;j++)if(r[j]r[j+1]){inttemp=r[j];r[j]=r[j+1];r[j+1]=temp;exchange=j//记载每一次记录交换的位置}}}2019/12/18AlgorithmIntroduction62.1算法的时间复杂性分析例2.3下列算法实现将两个升序序列合并成一个升序序列，请找出输入规模和基本语句voidUnion(intA[],intn,intB[],intm,intC[]){inti=0,j=0,k=0;while(in&&jm){if(A[i]=B[j])C[k++]=A[i++];//A[i]和B[j]较小者存入C[k]elseC[k++]=B[j++];}while(in)C[k++]=A[i++];while(jm)C[k++]=B[j++];}2019/12/18AlgorithmIntroduction72.1算法的时间复杂性分析定义2.1若存在两个正常数c和n0，对于任意n≥n0，都有T(n)≤c×f(n)，就称函数T(n)＝O(f(n))。2019/12/18AlgorithmIntroduction82.1.2算法的渐进分析算法的渐进分析并不是度量算法的时间量，而是度量算法运行时间的增长趋势。只考察当输入规模充分大时，算法中基本语句的执行次数的渐近意义下的阶，常用大（读欧）O表示。上界（增长率的上限），用O表示大O符号描述增长率的上限，表示T(n)的增长最多像f(n)增长的那样快。c×f(n)T(n)nono之前的情况不重要执行次数问题规模例2.4.分析例2.3中合并算法的时间复杂性解：1、假设退出第1个循环后i＝n,j=m’，说明序列A处理完毕，第2个循环将不执行，第3个循环执行。算法的时间复杂性为：O(n+m’+m-m’)=O(n+m)2、假设退出第1个循环后i＝n’,j=m，说明序列B处理完毕，第2个循环将执行，第3个循环不执行。算法的时间复杂性为：O(n’+m+n-n’)=O(n+m)综上，算法的时间复杂性为O(n+m)2019/12/18AlgorithmIntroduction9渐进符号（13）有些算法的时间代价只依赖于问题的输入规模，而与输入的具体数据无关。如上例合并算法。但有些算法，即使输入规模相同，如果输入数据不同，其时间代价也不相同。2019/12/18AlgorithmIntroduction102.1.3最好、最坏和平均情况2019/12/18AlgorithmIntroduction11例2.5：在一维整型数组A[n]中顺序查找与给定值k相等的元素（假设该数组中有且仅有一个元素值为k）intFind(intA[],intn){for(i=0;in;i++)if(A[i]==k)break;returni;}最好、最坏和平均情况最好情况：数组中第一元素就是K最坏情况：数组中最后元素就是K平均情况：平均比较n/2个元素基本语句以上三种情况下的时间复杂性,各从某一个角度来反映算法的效率,各有各的用处,也各有各的局限性。但实践表明可操作性最好的,且最有实际价值的,是最坏情况下的时间复杂性Tmax。一般来说,最好情况和最坏情况的时间复杂性是很难计量的。有时也按平均情况计量时间复杂性，但要对输入不同数据的概率做人为的假设(一般是假设等概率)之后才能进行,所做的假设缺乏必要的根据。因此，在最好情况和平均情况下的时间复杂性分析还仅仅是停留在理论上。2019/12/18AlgorithmIntroduction12最好、最坏和平均情况2019/12/18AlgorithmIntroduction13最好情况：出现概率较大时应该分析最好情况最差情况：在实时系统中很重要平均情况：要求：已知输入数据是如何分布的，通常假设等概率分布结论：如果问题规模相同，时间代价与输入数据有关，则需要分析最好情况、最坏情况、平均情况。最好、最坏和平均情况2019/12/18AlgorithmIntroduction14例2.6分析例2.2中起泡排序算法的时间复杂性基本语句是比较操作r[j]r[j+1]最好情况：记录已经是升序排列，算法只执行一次，比较n-1次，时间复杂性为O(n)最坏情况：记录是降序排列，每趟只是无序序列中最大的记录交换到最终位置，所以算法执行n-1趟，第i趟比较n-i次比较，则记录的比较次数为，时间复杂性O(n2)平均情况：O(n2)，过程略2.1.4非递归算法的时间复杂性分析11(1)()2ninnni2019/12/18AlgorithmIntroduction15非递归算法分析的一般步骤1.决定用哪个（或哪些）参数作为算法问题规模的度量2.找出算法中的基本语句3.检查基本语句的执行次数是否只依赖于问题规模4.建立基本语句执行次数的求和表达式5.用渐进符号表示这个求和表达式关键：建立一个代表算法运行时间的求和表达式，然后用渐进符号表示这个求和表达式。2.1.4非递归算法的时间复杂性分析2.1.5递归算法的时间复杂性分析1.猜测技术:对递推关系式估计一个上限，然后（用数学归纳法）证明它正确。如果成功，试着收缩上限。如果失败，放松限制再试着证明。直到上限符合要求。递归算法是分而治之的方法。递归算法时间复杂性分析的关键：根据递归过程建立递推关系式，然后求解这个递推关系式。2.猜测技术+2)2(221)(nnnTnnT补例1使用猜测技术分析二路归并排序算法的时间复杂性。二路归并排序运行时间递推式：假定T(n)≤n2，需证明这个猜测是正确的。为方便假定n=2kT(2)=1≤22成立，对所有i≤n，假设T(i)≤i2，则：T(2n)＝2T(n)+2n≤2n2+2n≤4n2=(2n)2故得，T(n)=O(n2)成立2.猜测技术O(n2)是最小上限？如果猜测更小一些，如T(n)≤cn，证明失败。即说明上限应在n和n2之间。再试试T(n)≤nlognT(2)=1≤2log2成立，对所有i≤n，假设T(i)≤nlogn，则：T(2n)＝2T(n)+2n≤2nlogn+2n=2n(logn+1)=2nlog(2n)故得，T(n)=O(nlogn)成立2.扩展递归技术+15)2(217)(2nnnTnnT)(10310)212(57257)(22212102nOnnnnnnnnTkkii++222112222225)2(52)2(52)1(25))2(5))4(5)8(2(2(25))2(5)4(2(25)2(2)(nnnTnnnnTnnnTnnTnTkkk+×´+++++++++L例2.7使用扩展递归技术分析下面递推式的时间复杂性为方便假定n=2k。将递推式进行扩展3.通用分治递推式大小为n的原问题分成若干个大小为n/b的子问题，其中a个子问题需要求解，而cnk是合并各个子问题的解需要的工作量。+1)(1)(ncnbnaTncnTkkkkbkkabanObannObanOnTb)()log()()(log定理2.1设T(n)是一个非递减函数，且满足通用分治递推式，则有如下结果成立。3.通用分治递推式证明：用扩展递归技术对通用分治递推式进行推导，假定a=bm211000()()(()())(1)()...()()()ikkkmmkkkmkmmmmikmiikmmiiiinnnTnaTcnaaTccnbbbnnaTacaccnbbnbcacabcaab+++++++求和是个几何级数，比率r=bk/a，且,有以下三种情况：loglogbbnamaan3.通用分治递推式loglog0logk0101(1)1:,a,()()1(2)1:1logn1,an,()(logn)1(3)1:(r)T(n)O(a)()()1bbbmaaimimaimkbbimmimmmkmkirrnTnOnrrrmnTnOnrrrOrObOnr+++由于所以由于所以，所以，2.2算法的空间复杂性分析算法在运行过程中所需的存储空间包括：（1）输入输出数据占用的空间。取决于问题，与算法无关（2）算法本身占用的空间。大小固定（3）执行算法需要的辅助空间。空间复杂性所指S(n)=O(f(n))算法输入输出数据辅助空间2.2算法的空间复杂性分析例2.8分析例2.2中起泡排序算法的空间复杂性。解：输入输出都在r[n]中，声明了3个简单变量：exchange、bound和temp。所以空间复杂性为O(1)如果算法所需的辅助空间相对于问题的输入规模来说是一个常数，我们称此算法为原地（或就地）工作。起泡排序算法属于就地性质。例2.9分析例2.3中合并算法的空间复杂性。解：合并不能就地进行，需要将合并结果存入另外一个数组中。设序列A的长度为n，序列B的长度为m，则合并后的有序序列的长度为n+m，因此算法的空间复杂性为O(n+m)2.3最优算法同一个问题可能会存在多种算法，是否有求解该问题的最优算法？如果能够知道一个问题的计算复杂性下界，也就是求解该问题的任何算法（包括尚未发现的算法）所需的时间下界，就可以较准确