计算复杂性和算法分析计算机科学导论第六讲.ppt

《计算复杂性和算法分析计算机科学导论第六讲.ppt》由会员分享，可在线阅读，更多相关《计算复杂性和算法分析计算机科学导论第六讲.ppt（43页珍藏版）》请在三一办公上搜索。

1、计算复杂性和算法分析计算机科学导论第六讲,计算机科学技术学院陈意云0551-63607043http:/,课 程 内 容,课程内容围绕学科理论体系中的模型理论,程序理论和计算理论1.模型理论关心的问题 给定模型M，哪些问题可以由模型M解决；如何比较模型的表达能力2.程序理论关心的问题给定模型M，如何用模型M解决问题包括程序设计范型、程序设计语言、程序设计、形式语义、类型论、程序验证、程序分析等3.计算理论关心的问题给定模型M和一类问题,解决该类问题需多少资源,本讲座用简单的例子来扼要介绍计算复杂性和算法分析,2,讲 座 提 纲,基本知识可计算理论,计算资源,计算复杂性理论,算法分析复杂性的计量

2、问题规模、复杂性函数、最坏、最好和平均三种情况的时间复杂性复杂性的渐近行为及其阶复杂性的渐近行为、渐近意义下的记号O、记号O的运算规则、复杂性渐近阶分析的重要性算法复杂性渐近阶的分析算法的复杂性渐近阶的分析、语句规则的例举,3,基 本 知 识,可计算理论研究计算的一般性质的数学理论，也称算法理论通过建立计算的数学模型,区分可计算与不可计算可计算函数：能够在抽象计算机上编出程序计算其值的函数。这样的程序称为算法这样就可以讨论哪些函数是可计算的，哪些函数是不可计算的可计算性：指一个实际问题是否可以使用计算机来解决（能解决一定是指有限步内解决）上一讲介绍的就是计算模型和可计算函数,4,基 本 知 识

3、,计算资源在计算复杂性理论内，计算资源是指在某个计算模型之下，求解一个问题所要消耗的资源时间资源：求解问题所需花费的时间，通常用计算步数来度量空间资源：求解问题所需占用的空间，通常用存储器空间的大小来度量计算所需资源的多少是衡量计算复杂性的依据实际应用关心的资源与理论上的有区别：硬件资源（如计算机、存储器）、软件资源、网络资源（如通信带宽）等,5,基 本 知 识,计算复杂性理论是理论计算机科学和数学的一个分支，它致力于将可计算问题根据其本身固有的难度进行分类，以及把这些类别相互联系起来它尝试把问题分成两类：在适当的资源限制下能解(容易)和不能解(困难)的问题。一个问题，若求解需很多资源(无论什

4、么算法),则被认为是难解的通过引入计算模型来研究这些问题，并给出定量计算解决问题所需的资源(时间和空间)的方法，由此把确定资源的方法数学化作用之一是确定计算机能解和不能解的实际界线,6,基 本 知 识,计算复杂性理论研究问题之一：NP=?PP(Polynomial)：在确定型图灵机上有多项式时间算法的问题的集合NP(Nondeterministic Polynomial)：在非确定型图灵机上有多项式时间算法的问题的集合NP=?P：是计算机科学中非常重要而又经历了几十年始终未解决的一个问题它的解决可导致一系列理论问题的解决,7,基 本 知 识,算法分析确定执行一个算法需要消耗的计算资源的数量的分

5、析过程算法的效率或复杂度表示为一个函数，其定义域是输入数据的规模（长度，算法大都设计成允许任意长的输入），值域通常是执行步数（时间复杂度）或所需存储空间数量（空间复杂度）在算法的理论分析中，通常是估计算法渐近意义上的复杂度精确分析算法的复杂度有时也可行，但它通常基于一些与具体实现相关的假设,8,基 本 知 识,可计算性、计算复杂性和算法分析的区别算法分析致力于分析求解一个问题的某个具体算法所需的资源量计算复杂性理论关注的是用所有可能算法解决同一类问题层面上的一般性议题可计算性理论关注的是原则上可以用算法求解的问题（把问题区分为可计算和不可计算）资源受限和不受限是区分计算复杂性理论和可计算性理论

6、的一个重要标志,9,复杂性的计量,两种查找算法的效率比较int search(int val)/顺序查找int j=0;/int am无重复且已按从小到大排序while(aj val/在最坏情况下，需要把val与a的所有分量比较,10,复杂性的计量,两种查找算法的效率比较int search(int val)/二分查找 int i,j,k;/int am无重复且已按从小到大排序 i=0;j=m 1;while(i=ak)i=k+1;if(j i=1)return 1;else return k;/在最坏情况下，只需要把val与a的log2 m个/分量比较，显然效率高于前一个算法,11,复杂性的

7、计量,两种求斐波那契数列前n+1项算法的效率比较void Fibonacci(int n)/假定n=0，递归算法 int i;for(i=0;i=n;i+)printf(“%dn”,fib(n);int fib(int k)if(k=0)return 0;else if(k=1)return 1;else return fib(k 1)+fib(k 2);对该数列a0,a1,an,ak(0 k n)被重复计算多次,12,复杂性的计量,两种求斐波那契数列前n+1项算法的效率比较void Fibonacci(int n)/假定n=0，循环算法 int j0,j1,i,temp;j0=0;j1=1;

8、for(i=0;i=n;i+)printf(“%dn”,j0);temp=j1;j1=j0+j1;j0=temp;ak(0 k n)都只计算1次,显然效率高于前一个算法,13,复杂性的计量,两种求斐波那契数列前n+1项算法的效率比较void Fibonacci(int n)/假定n=0，循环算法 int j0,j1,i,temp;j0=0;j1=1;for(i=0;i=n;i+)printf(“%dn”,j0);temp=j1;j1=j0+j1;j0=temp;这种比较单纯反映作为算法精髓的计算方法本身的效率，不涉及运行这些算法的实际计算机的性能,14,复杂性的计量,复杂性函数时间和空间复杂性

9、函数分别是：T(N,I)和S(N,I)N：问题规模，I：算法的输入问题问题的规模N在数组中查找值为val的分量数组中分量个数矩阵相乘矩阵的阶数表的排序数表中的项数遍历二叉树树中节点数求数列的前n项项数n解有关图的问题图中节点数或边数,15,复杂性的计量,复杂性函数时间和空间复杂性函数分别是：T(N,I)和S(N,I)N：问题规模，I：算法的输入时间复杂性和空间复杂性的概念类同，计算方法相似，且空间复杂性分析相对简单，因此下面仅讨论时间复杂性若抽象计算机有k种元运算，它们所需时间依次为t1,t2,tk。若某算法用到这k种运算的次数依次是e1,e2,ek，ei(1 i k)是N和I的函数,ei=e

10、i(N,I),则T(N,I)=ti ei(N,I),16,复杂性的计量,复杂性函数有关算法的输入I不可能为规模为N的每一种合法输入I 都去统计 ei(N,I)简化办法：在规模为N的某些或某类有代表性的合法输入中统计相应的ei，评价这些情况下的时间复杂性,17,复杂性的计量,三种时间复杂性函数最坏情况Tmax(N)=max T(N,I)=ti ei(N,I)=T(N,I)其中DN为规模为N的合法输入集,I是达max的输入最好情况（其中I是达min的输入）Tmin(N)=min T(N,I)=ti ei(N,I)=T(N,I)平均情况 Tavg(N)=P(I)T(N,I)=P(I)ti ei(N,

11、I)其中P(I)是在算法的应用中出现输入I的概率,IDN,IDN,IDN,IDN,=max ti ei(N,I),IDN,18,复杂性的渐近行为及其阶,如何简化算法分析计算机解决的问题越来越复杂，规模越来越大若按先前介绍的方法，把所有的元计算都考虑进去，并进行精确分析，则算法分析的步骤之多，工作量之大，令人难以承受下面介绍复杂性渐近行为的概念，以简化算法分析,19,复杂性的渐近行为及其阶,复杂性的渐近行为（asymptotic behavior）对于算法A的T(N)，一般来说，当N单调递增且趋于时，T(N)也单调递增且趋于对于T(N)，若存在T(N)，使得当N 时有(T(N)T(N)/T(N)

12、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称为阶,20,复杂性的渐近行为及其阶,复杂性的渐近行为对于T(N)，若存在T(N)，使得当N 时有(T(N)T(N)/T(N)0则称T(N)为算法A的当N 时的渐近复杂性若用T(N)代替T(N)，作为算法A在N 时的复杂性的度量，则复杂性分析明显简化复杂性分析的目的：在于比较同一问题的不同算法的效率，若两个算法的阶不同，则可知谁效

13、率高,21,复杂性的渐近行为及其阶,复杂性的渐近行为对于T(N)，若存在T(N)，使得当N 时有(T(N)T(N)/T(N)0则称T(N)为算法A的当N 时的渐近复杂性简化T(N)分析：只需关心T(N)的阶，把其常数因子忽略。如在3N2中，不用关心系数 3进一步简化T(N)分析：假设算法中用到的所有不同的元运算执行一次都只需一个时间单位,22,复杂性的渐近行为及其阶,算法复杂性的渐近分析方法只要考察当问题规模充分大时，算法复杂性在渐近意义下的阶。算法分析通常都是这么做的与此简化的复杂性分析相配套，需要引入一些渐近意义下的记号,23,复杂性的渐近行为及其阶,渐近意义下的记号O（代表order o

14、f）若f 和g是正整数集上的正函数，若存在大于0的常数C和自然数N0，使得N N0时有f(N)Cg(N),则称：在N充分大时，Cg(N)是函数f(N)的一个上界，记为f(N)=O(g(N)，并简称f(N)不大于g(N)的阶使用“=”是不妥的，这是一种对“=”的滥用f(N)=O(g(N)作为一个整体，表达函数f 和g的一种关系“=”在这里的含义是什么？单独的O(g(N)记号的含义是什么？,24,复杂性的渐近行为及其阶,渐近意义下的记号O（代表order of）若f 和g是正整数集上的正函数，若存在大于0的常数C和自然数N0，使得N N0时有f(N)Cg(N),则称：在N充分大时，Cg(N)是函数

15、f(N)的一个上界，记为f(N)=O(g(N)，并简称f(N)不大于g(N)的阶Intuitively this notation groups functions accordingto their growth respective to some parameter;as such,the notation is abusive in two respects:It abuses=,and it invokes terms that are real numbers instead of function terms.见Abuse_of_notation#Big_O_notation(网

16、页已被删去),25,复杂性的渐近行为及其阶,渐近意义下的记号O（代表order of）若f 和g是正整数集上的正函数，若存在大于0的常数C和自然数N0，使得N N0时有f(N)Cg(N),则称：在N充分大时，Cg(N)是函数f(N)的一个上界，记为f(N)=O(g(N)，并简称f(N)不大于g(N)的阶千万不要把这里的“=”理解成左右两边相等对于函数g(N)，尽可能使用简单的解析式。例如N,N2等N.N 1 3N 4N,故 f(N)=O(N)(f(N)=3N,g(N)=N,C=4,下面略去f和g的定义),26,复杂性的渐近行为及其阶,渐近意义下的记号O（代表order of）若f 和g是正整数

17、集上的正函数，若存在大于0的常数C和自然数N0，使得N N0时有f(N)Cg(N),则称：在N充分大时，Cg(N)是函数f(N)的一个上界，记为f(N)=O(g(N)，并简称f(N)不大于g(N)的阶N.N 10 2N2+11N 10 3N2，故 2N2+11N 10=O(N2)N.N 1 N+1024 1025N,故 N+1024=O(N)N.N 1 N2 N3，故N2=O(N3),27,复杂性的渐近行为及其阶,渐近意义下的记号O（代表order of）若f 和g是正整数集上的正函数，若存在大于0的常数C和自然数N0，使得N N0时有f(N)Cg(N),则称：在N充分大时，Cg(N)是函数f

18、(N)的一个上界，记为f(N)=O(g(N)，并简称f(N)不大于g(N)的阶N3 O(N2)（使用“”也是一种滥用）若不是这样，则存在大于0的常数C和自然数N0,使得N N0时有N3 CN2，即N C取N=max(N0,C+1)时，该不等式不成立，故N3 O(N2),28,复杂性的渐近行为及其阶,顺序查找算法回顾int search(int val)/顺序查找int j=0;/int am不重复且已按从小到大排序while(aj val,若赋值、比较和返回执行一次所需时间分别是a,t和r，若val 等于a0，则Tmin(m)=a+2t+r，其中m是问题规模,29,复杂性的渐近行为及其阶,渐近

19、意义下的记号O（代表order of）若f 和g是正整数集上的正函数，若存在大于0的常数C和自然数N0，使得N N0时有f(N)Cg(N),则称：在N充分大时，Cg(N)是函数f(N)的一个上界，记为f(N)=O(g(N)，并简称f(N)不大于g(N)的阶对于顺序查找算法，在最好情况下，只要取C=a+2t+r，就有Tmin(m)C 1，因此有Tmin(m)Cg(m)，其中g(m)=1，即Tmin(m)=O(1),30,复杂性的渐近行为及其阶,例：估计下面二重循环的最坏时间复杂性的阶for(i=1;i N;i+)for(j=1;j i;j+)s1;s2;s3;s4;其中sk(k=1,2,3,4)

20、都是赋值语句对内循环体，执行一次需要的时间是4a加上循环控制，则是5a+t内循环执行i 次,需时间(5a+t)i,因此上界为 O(i)外循环执行N次，需时间(5a+t)(1+2+N)+(a+t)N,31,复杂性的渐近行为及其阶,例：估计下面二重循环的最坏时间复杂性的阶for(i=1;i N;i+)for(j=1;j i;j+)s1;s2;s3;s4;其中sk(k=1,2,3,4)都是赋值语句外循环执行N次，需时间(5a+t)N(N+1)/2+(a+t)N因此上界为O(N2)这是规模充分大时的上界这个上界的阶越低，则评估就越精确，结果就越有价值,32,复杂性的渐近行为及其阶,关于记号O(g(N)

21、的讨论当讨论复杂算法上界时，很希望上界记号O(g(N)能参与到复杂性计算中例如，上例内循环的上界O(i)，则累加起来便是外循环的时间复杂性T(N)=O(i)=O(i)=O(N(N+1)/2)=O(N2)若希望如此，则需要有一些演算规则，并证明其正确性,33,复杂性的渐近行为及其阶,关于记号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)问题：在O()未定义时，等号左边+和的含义？,f(N),若f(N)g(N)其中max(f(N),g(N)=g(

22、N),若f(N)g(N),34,复杂性的渐近行为及其阶,关于记号O(g(N)的讨论一种解释（另一本书给出）：O(g(N)=f(N)|C 0.N0 0.N N0.0 f(N)Cg(N)符号O(g(N)在此给出了明确的数学意义写f(N)O(g(N)容易理解(而不是f(N)=O(g(N)但解释O(f(N)+O(g(N)和O(f(N)O(g(N)中的+和（尤其是）仍然有困难导致各书仍继续使用f(N)=O(g(N)记号，使得读者难理解,35,复杂性的渐近行为及其阶,其他渐近意义下的记号下界记号若f 和g是正整数集上的正函数，若存在大于0的常数C和自然数N0，使得N N0时有f(N)Cg(N),则称：在N

23、充分大时，Cg(N)是函数f(N)的一个下界，记为f(N)=(g(N)，并简称f(N)不小于g(N)的阶记号 f(N)=(g(N)f(N)=O(g(N)f(N)=(g(N)此时称f(N)和g(N)同阶还有其他记号,36,复杂性的渐近行为及其阶,算法与渐近时间复杂性的关系算法 渐近复杂 在C1上可 在C2上可 N1和N2的关系 性T(N)解规模N1 解规模N2 方程Ti(N2i)=10Ti(N1i)是求解N2i和N1i之间的关系 等式Ti(N2i)=10Ti(N1i)的含义是：第i个算法在C1上运行10倍于C2上运行的时间，则等号两边效果一样 同一问题六个算法,在C1和C2上运行,C2的速度是C

24、110倍.从Ti(N2i)=10Ti(N1i)(i=1,6)解出关系式,37,复杂性的渐近行为及其阶,算法与渐近时间复杂性的关系算法 渐近复杂 在C1上可 在C2上可 N1和N2的关系 性T(N)解规模N1 解规模N2 A1 N N11 N21 N21=10N11 A2 NlogN N12 N22 N22 10N12 A3 N2 N13 N23 N23=10N13 A4 N3 N14 N24 N24=10N14 A5 2N N15 N25 N25=N15+log10 A6 N!N16 N26 N26=N16+小的常数同一问题六个算法,在C1和C2上运行,C2的速度是C110倍.从Ti(N2i)

25、=10Ti(N1i)(i=1,6)解出关系式见上表,38,复杂性的渐近行为及其阶,复杂性渐近分析的重要性对于低效算法，计算机速度数10甚至100倍的增长基本上不带来求解规模的增益限制求解问题规模的主要根源是算法渐近复杂性的阶 前四个算法的渐近时间复杂性与规模N的一个确定的幂同阶，机器速度的乘法增长带来求解规模的乘法增长。这类算法称为多项式算法 后两个算法的渐近时间复杂性与规模N的一个指数函数同阶，只能带来求解规模的加法增长这些结论在问题规模充分大时才成立,39,算法复杂性渐近阶的分析,如何分析具体算法的复杂性渐近阶算法是用程序来表达的，算法复杂性渐近阶分析就是对其程序的相应分析针对所用编程语言

26、，给出一套可操作的分析规则分析程序的语句、程序块和函数时，可用局部的规模参数作为复杂性函数的自变量。整个程序的复杂性函数还是以整个程序的输入规模为自变量对串行算法，其时间复杂性等于相应程序每个语句的时间复杂性之和。若对每种语句所需时间都有度量规则，则算法所需时间就是一个求和问题运用O、和 的运算规则就可进行所需分析,40,算法复杂性渐近阶的分析,基本运算和基本语句赋值、比较运算、算术运算、逻辑运算和读写变量等需1个单位时间下标变量和结构体的域的访问等需1个单位时间if(C)S1 else S2只需TC+max(TS1,TS1)个单位时间while(C)S所需单位时间数：(TC+TS)循环次数函

27、数调用：控制转移的时间+执行被调函数的时间递归函数：需要从所需时间的归纳定义（递归方程）中求解基于这些规则可以计算整个程序的复杂性函数,41,小 结,本讲座小结概要介绍计算复杂性理论、计算所需资源的多少是衡量计算复杂性的依据概要介绍复杂性的渐近行为、渐近意义下的记号O及其运算规则、复杂性渐近分析的重要性、算法的复杂性渐近阶的分析参考书，2004帕帕李米特里乌，计算复杂性，清华大学出版社王晓东，计算机算法设计与分析,电子工业出版社本讲座的内容大部分取自该书,42,小 结,与算法分析相关课程数据结构、算法基础、并行计算研究方向挑战性的问题之一：证明诸如“NP=？P”这类问题的解是模型相关的各种新型计算模型下的核心算法,43,