中科大计算机科学导论 6

计算复杂性理论和算法分析计算机科学导论第六讲计算机科学技术学院陈意云[e-mail]课程内容•课程内容围绕学科理论体系中的模型理论,程序理论和计算理论1.模型理论关心的问题给定模型M，哪些问题可以由模型M解决；如何比较模型的表达能力2.程序理论关心的问题–给定模型M，如何用模型M解决问题–包括程序设计范型、程序设计语言、程序设计、形式语义、类型论、程序验证、程序分析等3.计算理论关心的问题给定模型M和一类问题,解决该类问题需多少资源讲座提纲•基本知识–计算资源、计算复杂性理论、算法分析•复杂性的计量–问题规模、复杂性函数、最坏、最好和平均三种情况的时间复杂性•复杂性的渐近行为及其阶–复杂性的渐近行为、渐近意义下的记号O、记号O的运算规则、复杂性渐近分析的重要性•算法复杂性渐近阶的分析–算法的复杂性渐近阶的分析、语句的规则例举基本知识•计算资源–在计算复杂性理论内，计算资源是指在某个计算模型之下，求解各种问题所要消耗的资源–时间资源：求解问题所需花费的时间，通常用计算步数来度量–空间资源：求解问题所需占用的空间，通常用存储器空间的大小来度量–计算所需资源的多少是衡量计算复杂性的依据实际应用关心的资源与理论有区别：内存、通信带宽、硬件等基本知识•计算复杂性理论–是理论计算机科学和数学的一个分支，它致力于将可计算问题根据其本身固有的难度进行分类，以及把这些类别相互联系起来–若一个问题的求解需要很多的资源（无论用什么算法），则该问题被认为是难解的–通过引入计算模型来研究这些问题，并定量计算解决问题所需的资源（时间和空间），由此把确定资源的方法数学化–作用之一是确定计算机能解和不能解的实际界线基本知识•计算复杂性理论–相关领域有算法分析和可计算性理论–算法分析致力于分析用一个具体算法求解一个问题所需的资源量，而计算复杂性理论关注的是用所有可能算法解决相同问题层面上的一般性议题–计算复杂性理论尝试把问题分成两类：在适当的资源限制下能解和不能解的问题–资源受限和不受限是区分计算复杂性理论和可计算性理论的一个重要标志：可计算性理论关注的是原则上可以用算法求解的问题基本知识•算法分析–确定执行一个算法需要消耗的计算资源数量的分析过程–算法的效率或复杂度表示为一个函数，其定义域是输入数据的长度（算法大都设计成允许任意长的输入），值域通常是执行步数（时间复杂度）或所需存储空间数量（空间复杂度）–在算法的理论分析中，通常是估计算法渐近意义上的复杂度–精确分析算法的效率有时也可行，但它通常基于一些与具体实现相关的假设复杂性的计量•两种查找算法的效率比较intsearch(intval){//顺序查找intj=0;//inta[m]无重复且已按从小到大排序while(a[j]val&&jm1){j=j+1;}if(a[j]==val){returnj;}else{return1;}//在最坏情况下，需要把val与a的所有m个}//分量比较复杂性的计量•两种查找算法的效率比较intsearch(intval){//二分查找inti,j,k;//inta[m]无重复且已按从小到大排序i=0;j=m1;while(i=j){k=i+(ji)/2;if(val=a[k])j=k1;if(val=a[k])i=k+1;}if(ji==1){return1;}else{returnk;}}//在最坏情况下，只需要把val与a的log2m个//分量比较，显然效率高于前一个算法复杂性的计量•两种求斐波那契数列前n+1项算法的效率比较voidFibonacci(intn){//假定n=0，递归算法inti;for(i=0;i=n;i++)printf(“%d\n”,fib(n));}intfib(intk){if(k==0)return0;elseif(k==1)return1;elsereturnfib(k1)+fib(k2);}对该数列a0,a1,…,an,ak(0kn)被重复计算多次复杂性的计量•两种求斐波那契数列前n+1项算法的效率比较voidFibonacci(intn){//假定n=0，循环算法intj0,j1,i,temp;j0=0;j1=1;for(i=0;i=n;i++){printf(“%d\n”,j0);temp=j1;j1=j0+j1;j0=temp;}}ak(0kn)都只计算1次,显然效率高于前一个算法复杂性的计量•两种求斐波那契数列前n+1项算法的效率比较voidFibonacci(intn){//假定n=0，循环算法intj0,j1,i,temp;j0=0;j1=1;for(i=0;i=n;i++){printf(“%d\n”,j0);temp=j1;j1=j0+j1;j0=temp;}}这个比较单纯反映作为算法精髓的计算方法本身的效率，不涉及运行这些算法的实际计算机的性能复杂性的计量•复杂性函数–时间和空间复杂性函数分别是：T(N,I)和S(N,I)N：问题规模，I：算法的输入问题问题的规模N在数组中查找值为val的分量数组中分量个数矩阵相乘矩阵的阶数表的排序数表中的项数遍历二叉树树中节点数求数列的前n项项数n解有关图的问题图中节点数或边数复杂性的计量•复杂性函数–时间和空间复杂性函数分别是：T(N,I)和S(N,I)N：问题规模，I：算法的输入–时间复杂性和空间复杂性的概念类同，计算方法相似，且空间复杂性分析相对简单，因此下面仅讨论时间复杂性–假定抽象计算机有k种运算，它们所需时间依次为t1,t2,…,tk。若某算法用到这k种运算的次数依次是e1,e2,…,ek,则ei(1ik)是N和I的函数,ei=ei(N,I),则T(N,I)=tiei(N,I)i=1k复杂性的计量•三种时间复杂性函数–最坏情况Tmax(N)=maxT(N,I)=tiei(N,I)=T(N,I)其中DN为规模为N的合法输入集,I是达max的输入–最好情况（其中I~是达min的输入）Tmin(N)=minT(N,I)=tiei(N,I~)=T(N,I~)–平均情况Tavg(N)=P(I)T(N,I)=P(I)tiei(N,I)其中P(I)是在算法的应用中出现输入I的概率i=1kIDNIDNi=1kIDNIDNi=1k=maxtiei(N,I)IDNi=1k复杂性的渐近行为及其阶•复杂性的渐近行为（asymptoticbehavior）–对于算法A的T(N)，一般来说，当N单调递增且趋于时，T(N)也单调递增且趋于–对于T(N)，若存在T(N)，使得当N时有(T(N)T(N))/T(N)0则称T(N)是T(N)当N时的渐近行为，或称T(N)为算法A的、当N时的渐近复杂性–直观上，T(N)是T(N)略去低项后的主项例：若T(N)是3N2+4Nlog2N+7时，T(N)可以是3N2,若N，(4Nlog2N+7)/(3N2+4Nlog2N+7)0～～～～～～N2称为阶复杂性的渐近行为及其阶•复杂性的渐近行为–对于T(N)，若存在T(N)，使得当N时有(T(N)T(N))/T(N)0则称T(N)为算法A的当N时的渐近复杂性–若用T(N)代替T(N)，作为算法A在N时的复杂性的度量，则复杂性分析明显简化–复杂性分析在于比较同一问题的不同算法的效率,若两个算法的阶可确定且不同，则可判断谁效率高–渐近性分析只要关心T(N)的阶，不必关心包含在T(N)中的常数因子。例如，在3N2中，不关心系数3～～～～～～复杂性的渐近行为及其阶•复杂性的渐近行为–对于T(N)，若存在T(N)，使得当N时有(T(N)T(N))/T(N)0则称T(N)为算法A的当N时的渐近复杂性–进一步简化T(N)分析：假设算法中用到的所有不同的元运算执行一次都只需一个时间单位•算法复杂性的渐近分析方法考察当问题规模充分大时，算法复杂性在渐近意义下的阶～～～～复杂性的渐近行为及其阶•渐近意义下的记号O（代表orderof…）若存在大于0的常数C和自然数N0,使得NN0时有f(N)Cg(N),则称函数f(N)在N充分大时有上界,且g(N)是它的一个上界,记为f(N)=O(g(N)).并称f(N)的阶不高于g(N)的阶(f和g是正整数集上的正函数)–N.N13N4N，故3N=O(N)–N.N1N+10241025N,故N+1024=O(N)–N.N102N2+11N103N2，故2N2+11N10=O(N2)–N.N1N2N3，故N2=O(N3)复杂性的渐近行为及其阶•渐近意义下的记号O（代表orderof…）若存在大于0的常数C和自然数N0,使得NN0时有f(N)Cg(N),则称函数f(N)在N充分大时有上界,且g(N)是它的一个上界,记为f(N)=O(g(N)).并称f(N)的阶不高于g(N)的阶(f和g是正整数集上的正函数)–N3O(N2)否则,存在大于0的常数C和自然数N0,使得NN0时有N3CN2，即NC。取N=max(N0,C+1)时该不等式不成立，故N3O(N2)复杂性的渐近行为及其阶•顺序查找算法回顾intsearch(intval){//顺序查找intj=0;//inta[m]不重复且已按从小到大排序while(a[j]val&&jm1){j=j+1;}//在最好情况下，val==a[0],if(a[j]==val){//把val与a第1个分量比较即可returnj;}else{return1;}}若赋值、比较和返回执行一次所需时间分别是a,t和r，若val等于a[0]，则Tmin(m)=a+2t+r，其中m是问题规模复杂性的渐近行为及其阶•渐近意义下的记号O（代表orderof…）若存在大于0的常数C和自然数N0,使得NN0时有f(N)Cg(N),则称函数f(N)在N充分大时有上界,且g(N)是它的一个上界,记为f(N)=O(g(N)).并称f(N)的阶不高于g(N)的阶(f和g是正整数集上的正函数)–对于顺序查找算法，在最好情况下，只要取C=a+2t+r，就有Tmin(m)C1，因此有Tmin(m)Cg(m)，其中g(m)=1，即Tmin(m)=O(1)复杂性的渐近行为及其阶•例：估计下面二重循环的最坏时间复杂性的阶for(i=1;iN;i++)for(j=1;ji;j++)s1;s2;s3;s4;其中sk(k=1,2,3,4)都是赋值语句–对内循环体，执行一次需要的时间是4a–加上循环控制条件，则是5a+t–内循环执行i次,需时间(5a+t)i,因此上界为O(i)–外循环执行N次，需时间(5a+t)(1+2+…+N)+(a+t)N因此上界为O(N2)，因为1+2+…+N=N(N+1)/2复杂性的渐近行为及其阶•例：估计下面二重循环的最坏时间复杂性的阶for(i=1;iN;i++)for(j=1;ji;j++)s1;s2;s3;s4;其中sk(k=1,2,3,4)都是赋值语句–外循环执行N次，需时间(5a+t)N(N+1)/2+(a+t)N因此上界为O(N2)–这是规模充分大时的上界–这个上界的阶越低，则评估就越精确，结果就越有价值复杂性的渐近行为及其阶•关于记号O(g(N))的讨论–当讨论复杂算法上界时，很希望上界记号O(g(N))能参与到复杂性计算中–例如，上例内循环的上界O(i)，则累加起来便是外循环的时间复杂性T(N)=O(i)=O(i)=O(N(N+1)/2)=O(N2)–若希望如此，则需要有一些演算规则，并证明其正确性i=1ni=1n复杂性的渐近行为及其阶•关于记号O(g(N))的讨论记号O的运算规则（某书给出）–O(f(N))+O(g(N))=O(max(f(N),g(N)))–O(f(N))+O(g(N))=O(f(N)+g(N))–O(f(N))O(g(N))=O(f(N)g(N))–……–