计算复杂性说课讲解.ppt

《计算复杂性说课讲解.ppt》由会员分享，可在线阅读，更多相关《计算复杂性说课讲解.ppt（43页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、计算复杂性讲讲 座座 提提 纲纲基本知识基本知识可计算理论可计算理论,计算资源计算资源,计算复杂性理论计算复杂性理论,算法分析算法分析复杂性的计量复杂性的计量问题规模、复杂性函数、最坏、最好和平均三种问题规模、复杂性函数、最坏、最好和平均三种情况的时间复杂性情况的时间复杂性复杂性的渐近复杂性的渐近行为及其阶行为及其阶复杂性的渐近复杂性的渐近行为、行为、渐近意义下的记号渐近意义下的记号O、记号记号O的运算规则、的运算规则、复杂性渐近阶分析的重要性复杂性渐近阶分析的重要性算法复杂性渐近阶的分析算法复杂性渐近阶的分析算法的复杂性渐近阶的分析、语句规则的例举算法的复杂性渐近阶的分析、语句规则的例举2基

2、基 本本 知知 识识可可计计算理算理论论研究计算的一般性质的数学理论，也称算法理论研究计算的一般性质的数学理论，也称算法理论通过建立计算的数学模型通过建立计算的数学模型,区分可计算与不可计算区分可计算与不可计算可计算函数：能够在抽象计算机上编出程序计算可计算函数：能够在抽象计算机上编出程序计算其值的函数。这样的程序称为算法其值的函数。这样的程序称为算法这样就可以讨论哪些函数是可计算的，哪些函数这样就可以讨论哪些函数是可计算的，哪些函数是不可计算的是不可计算的可计算性：指一个实际问题是否可以使用计算机可计算性：指一个实际问题是否可以使用计算机来解决（能解决一定是指有限步内解决）来解决（能解决一定

3、是指有限步内解决）上一讲介绍的就是计算模型和可计算函数上一讲介绍的就是计算模型和可计算函数3基基 本本 知知 识识计计算算资资源源在计算复杂性理论内，计算资源是指在某个计算在计算复杂性理论内，计算资源是指在某个计算模型之下，求解一个问题所要消耗的资源模型之下，求解一个问题所要消耗的资源时间资源：求解问题所需花费的时间，通常用计时间资源：求解问题所需花费的时间，通常用计算步数来度量算步数来度量空间资源：求解问题所需占用的空间，通常用存空间资源：求解问题所需占用的空间，通常用存储器空间的大小来度量储器空间的大小来度量计算所需资源的多少是衡量计算复杂性的依据计算所需资源的多少是衡量计算复杂性的依据实

4、际应用关心的资源与理论上的有区别：硬件资实际应用关心的资源与理论上的有区别：硬件资源（如计算机、存储器）、软件资源、网络资源源（如计算机、存储器）、软件资源、网络资源（如通信带宽）等（如通信带宽）等 4基基 本本 知知 识识计计算复算复杂杂性理性理论论是理论计算机科学和数学的一个分支，它致力于是理论计算机科学和数学的一个分支，它致力于将可计算问题根据将可计算问题根据其其本身本身固有的难度进行固有的难度进行分类，分类，以及以及把把这些类别这些类别相互相互联系起来联系起来它它尝试尝试把把问题分成两类问题分成两类：在：在适当适当的的资源资源限制下能限制下能解解(容易容易)和不能解和不能解(困难困难)

5、的问题。一个问题，若的问题。一个问题，若求求解需解需很很多资源多资源(无论什么算法无论什么算法),则被认为是难解的则被认为是难解的通过引入计算模型来研究这些问题通过引入计算模型来研究这些问题，并给出，并给出定量定量计算解决问题所需的资源计算解决问题所需的资源(时间和空间时间和空间)的方法的方法，由此把由此把确定资源确定资源的的方法方法数学化数学化作用之一作用之一是确定计算机是确定计算机能解和不能能解和不能解的实际解的实际界线界线5基基 本本 知知 识识计计算复算复杂杂性理性理论论研究问题之一：研究问题之一：NP=?PP(Polynomial)：在确定型图灵机上有多项式时间：在确定型图灵机上有多

6、项式时间算法的问题的集合算法的问题的集合NP(Nondeterministic Polynomial)：在非确定型图：在非确定型图灵机上有多项式时间算法的问题的集合灵机上有多项式时间算法的问题的集合NP=?P：是计算机科学中非常重要而又经历了几：是计算机科学中非常重要而又经历了几十年始终未解决的一个问题十年始终未解决的一个问题它的解决可导致一系列理论问题的解决它的解决可导致一系列理论问题的解决6基基 本本 知知 识识算法分析算法分析确定确定执行一个算法需要消耗的计算资源执行一个算法需要消耗的计算资源的的数量数量的的分析过程分析过程算法的效率或复杂度表示为一个函数算法的效率或复杂度表示为一个函数

7、，其定义域其定义域是输入数据的是输入数据的规模规模（长度，算法大都设计成允许长度，算法大都设计成允许任意任意长长的输入），值域通常是执行步数（时间复的输入），值域通常是执行步数（时间复杂度）或杂度）或所需所需存储存储空间空间数量（空间复杂度）数量（空间复杂度）在算法的在算法的理论分析理论分析中，通常是中，通常是估计算法估计算法渐近意义渐近意义上上的复杂度的复杂度精确分析算法的精确分析算法的复杂度复杂度有时也可行，但有时也可行，但它它通常通常基基于于一些与具体实现相关的假设一些与具体实现相关的假设7基基 本本 知知 识识可可计计算性、算性、计计算复算复杂杂性和算法分析的区性和算法分析的区别别算法

8、分析算法分析致力于分析求解一个问题致力于分析求解一个问题的某个具体算的某个具体算法法所需的资源量所需的资源量计算复杂性理论计算复杂性理论关注的是用所有可能算法解决同关注的是用所有可能算法解决同一类问题层面上的一般性议题一类问题层面上的一般性议题可计算性理论可计算性理论关注关注的是原则上可以的是原则上可以用算法求解的用算法求解的问题（把问题区分为可计算和不可计算）问题（把问题区分为可计算和不可计算）资源受限和不受限资源受限和不受限是区分计算复杂性理论和可计是区分计算复杂性理论和可计算性理论的一个重要算性理论的一个重要标志标志8复杂性的计量复杂性的计量两种两种查查找算法的效率比找算法的效率比较较i

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

10、/2;if(val=ak)i=k+1;if(j i=1)return 1;else return k;/在最坏情况下，只需要把在最坏情况下，只需要把val与与a的的log2 m个个 /分量比分量比较较，显显然效率高于前一个算法然效率高于前一个算法10复杂性的计量复杂性的计量两种求斐波那契数列前两种求斐波那契数列前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)re

11、turn 1;else return fib(k 1)+fib(k 2);对该对该数列数列a0,a1,an,ak(0 k=0，循环算法循环算法 int j0,j1,i,temp;j0=0;j1=1;for(i=0;i=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;这这种比种比较单纯较单纯反映作反映作为为算法精髓的算法精髓的计计算方法本身算方法本身的效率，不涉及运行的效率，不涉及运行这这些算法的些算法的实际计实际计算机的性能算机的性能13复杂性的计量复杂

12、性的计量复杂性函数复杂性函数时间和空间复杂性函数分别是：时间和空间复杂性函数分别是：T(N,I)和和S(N,I)N：问题规模，：问题规模，I：算法的输入：算法的输入问题问题问题的规模问题的规模N在数组中查找值为在数组中查找值为val的分量的分量数组中分量个数数组中分量个数矩阵相乘矩阵相乘矩阵的阶矩阵的阶数表的排序数表的排序数表中的项数数表中的项数遍历二叉树遍历二叉树树中节点数树中节点数求数列的前求数列的前n项项项数项数n解有关图的问题解有关图的问题图中节点数或边数图中节点数或边数14复杂性的计量复杂性的计量复杂性函数复杂性函数时间和空间复杂性函数分别是：时间和空间复杂性函数分别是：T(N,I)

13、和和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)=ti ei(N,I)i=1k15复杂性的计量复杂性的计量复杂性

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

15、是达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,I)其中其中P(I)是在算法的应用中出现输入是在算法的应用中出现输入I的概率的概率i=1kI D DNI D DNi=1kI D DNI D DNi=1k=max ti ei(N,I)I D DNi=1k17复杂性的渐近行为及其阶复杂性的渐近行为及其阶如何简化算法分析如何简化算法分析计算机解决的问题越来越复杂，规模越来越大计算机解决的问题越来越复杂，规模越来越大若按先前介绍的方法，把所有的元计算都考虑进若按先前介绍的方

16、法，把所有的元计算都考虑进去，并进行精确分析，则算法分析的步骤之多，去，并进行精确分析，则算法分析的步骤之多，工作量之大，令人难以承受工作量之大，令人难以承受下面介绍复杂性渐近行为的概念，以简化算法分下面介绍复杂性渐近行为的概念，以简化算法分析析18复杂性的渐近行为及其阶复杂性的渐近行为及其阶复杂性的渐近行为（复杂性的渐近行为（asymptotic behavior）对于算法对于算法A的的T(N)，一般来说，一般来说，当当N单调递增且趋单调递增且趋于于 时，时，T(N)也也单调递增且趋于单调递增且趋于 对于对于T(N)，若存在，若存在T(N)，使得当，使得当N 时有时有 (T(N)T(N)/T

17、(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)0N2称为阶称为阶19复杂性的渐近行为及其阶复杂性的渐近行为及其阶复杂性的渐近行为复杂性的渐近行为对于对于T(N)，若存在，若存在T(N)，使得当，使得当N 时有时有 (T(N)T(N)/T(N)0则称则称T(N)为算法为算法A的当的

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

19、化T(N)分析：分析：只需关心只需关心T(N)的阶，把其常数因的阶，把其常数因子忽略。如在子忽略。如在3N2中，不用关心系数中，不用关心系数 3进一步简化进一步简化T(N)分析：假设算法中用到的所有不分析：假设算法中用到的所有不同的元运算执行一次都只需一个时间单位同的元运算执行一次都只需一个时间单位21复杂性的渐近行为及其阶复杂性的渐近行为及其阶算法复杂性的渐近分析方法算法复杂性的渐近分析方法只要考察当问题规模充分大时，算法复杂性在渐只要考察当问题规模充分大时，算法复杂性在渐近意义下的阶。算法分析通常都是这么做的近意义下的阶。算法分析通常都是这么做的与此简化的复杂性分析相配套，需要引入一些渐与

20、此简化的复杂性分析相配套，需要引入一些渐近意义下的记号近意义下的记号22复杂性的渐近行为及其阶复杂性的渐近行为及其阶渐近意义下的渐近意义下的记号记号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)的阶的阶使用使用“=”是不妥的，这是一种对是不妥的，这是一种对“=”的滥用的滥用f(N)=O

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

22、称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.见见https:/en.wikipedia.org/wiki/Abuse_of_notation#Big_O_n

23、otation(网页已被删去网页已被删去)24复杂性的渐近行为及其阶复杂性的渐近行为及其阶渐近意义下的渐近意义下的记号记号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)，尽可能使用

24、简单的解析式。例如，尽可能使用简单的解析式。例如N,N2等等 N.N 1 3N 4N,故故 f(N)=O(N)(f(N)=3N,g(N)=N,C=4,下面略去下面略去f和和g的定义的定义)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)，并简称，并简称

25、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)26复杂性的渐近行为及其阶复杂性的渐近行为及其阶渐近意义下的渐近意义下的记号记号O（代表（代表order of）若若f 和和g是正整数集上的正函数，若存在大于是正整数集上的正函数，若存在大于0的常的常数数C和自然数和自然数N0，使得，使得N N0时有时有f(N)Cg(N),则则称：在称：在N充分大时，充分大时，Cg(N)是函数是函数f(N)的一个上界，的一个上界，记

26、为记为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)27复杂性的渐近行为及其阶复杂性的渐近行为及其阶顺顺序序查查找算法回找算法回顾顾int search(int val)/顺顺序序查查找找int j=0;/int am不重复且已按从小到大排序不重复且已按从小到大排序while(aj va

27、l&j m 1)j=j+1;/在最好情况下，在最好情况下，val=a0,if(aj=val)/把把val与与a第第1个分量比个分量比较较即可即可 return j;else return 1;若赋值、比较和返回执行一次所需若赋值、比较和返回执行一次所需时间分别是时间分别是a,t和和r，若，若val 等于等于a0，则则Tmin(m)=a+2t+r，其中，其中m是是问题问题规规模模28复杂性的渐近行为及其阶复杂性的渐近行为及其阶渐近意义下的记号渐近意义下的记号O（代表（代表order of）若若f 和和g是正整数集上的正函数，若存在大于是正整数集上的正函数，若存在大于0的常的常数数C和自然数和自然

28、数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)29复杂性的渐近行为及其阶复杂性的渐近行为及其阶例：估计下面二重循环的最坏时间复杂性的阶例：估计下面二重循环的最坏时间复杂性的阶for(i=1;i N;i+

29、)for(j=1;j i;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 30复杂性的渐近行为及其阶复杂性的渐近行为及其阶例：估计下面二重循环的最坏时间复杂性的阶例：估计下面二重循环的最坏时间复杂性的阶for(i=1;i N;i+)for(j=1;j i;j+)s1;s2;s

30、3;s4;其中其中sk(k=1,2,3,4)都是赋值语句都是赋值语句外循环执行外循环执行N次，需时间次，需时间(5a+t)N(N+1)/2+(a+t)N因此上界为因此上界为O(N2)这是规模充分大时的上界这是规模充分大时的上界这个上界的阶越低，则评估就越精确，结果就越有这个上界的阶越低，则评估就越精确，结果就越有价值价值31复杂性的渐近行为及其阶复杂性的渐近行为及其阶关于记号关于记号O(g(N)的讨论的讨论当讨论复杂算法上界时，很希望上界记号当讨论复杂算法上界时，很希望上界记号O(g(N)能参与到复杂性计算中能参与到复杂性计算中例如，上例内循环的上界例如，上例内循环的上界O(i)，则累加起来便

31、是外，则累加起来便是外循环的时间复杂性循环的时间复杂性T(N)=O(i)=O(i)=O(N(N+1)/2)=O(N2)若希望如此，则需要有一些演算规则，并证明其若希望如此，则需要有一些演算规则，并证明其正确性正确性i=1ni=1n32复杂性的渐近行为及其阶复杂性的渐近行为及其阶关于记号关于记号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()未定义时，等号左边未定义时，等号左边+和和 的含义？

32、的含义？f(N),若若f(N)g(N)其中其中max(f(N),g(N)=g(N),若若f(N)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)记号，使得读记号，使得读者难理解者难理解34复杂性的渐近行为及其阶复杂性的渐近行为及其阶其他渐近意义下的记号其他渐近意义下的记号下界记

33、号下界记号 若若f 和和g是正整数集上的正函数，若是正整数集上的正函数，若存在大于存在大于0的常的常数数C和自然数和自然数N0，使得，使得N N0时有时有f(N)Cg(N),则则称：称：在在N充分大时，充分大时，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)同阶同阶还有其他记号还有其他记号35复杂性的渐近行为及其阶复杂性的渐近行为及其阶算法与渐近时间复杂性的关系算法与渐近时间复杂性的关系算法算法 渐近复杂渐

34、近复杂 在在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的速度是的速度是C110倍倍.从从Ti(N2i)=10Ti(N1i)(i=1,6)解出关系式解出关系式36复杂性的渐近行为及其阶复杂性的渐近行

35、为及其阶算法与渐近时间复杂性的关系算法与渐近时间复杂性的关系算法算法 渐近复杂渐近复杂 在在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

36、倍倍.从从Ti(N2i)=10Ti(N1i)(i=1,6)解出关系式见上表解出关系式见上表 337复杂性的渐近行为及其阶复杂性的渐近行为及其阶复杂性渐近分析的重要性复杂性渐近分析的重要性对对于于低低效效算算法法，计计算算机机速速度度数数10甚甚至至100倍倍的的增增长长基本上不带来求解规模的增益基本上不带来求解规模的增益限限制制求求解解问问题题规规模模的的主主要要根根源源是是算算法法渐渐近近复复杂杂性性的阶的阶 前前四四个个算算法法的的渐渐近近时时间间复复杂杂性性与与规规模模N的的一一个个确确定定的的幂幂同同阶阶，机机器器速速度度的的乘乘法法增增长长带带来来求求解解规规模模的乘法增长。这类算法

37、称为多项式算法的乘法增长。这类算法称为多项式算法 后后两两个个算算法法的的渐渐近近时时间间复复杂杂性性与与规规模模N的的一一个个指指数函数同阶，只能带来求解规模的加法增长数函数同阶，只能带来求解规模的加法增长这些结论在问题规模充分大时才成立这些结论在问题规模充分大时才成立38算法复杂性渐近阶的分析算法复杂性渐近阶的分析如何分析具体算法的复杂性渐近阶如何分析具体算法的复杂性渐近阶算算法法是是用用程程序序来来表表达达的的，算算法法复复杂杂性性渐渐近近阶阶分分析析就是对其程序的相应分析就是对其程序的相应分析针对所用编程语言，给出一套可操作的分析规则针对所用编程语言，给出一套可操作的分析规则分分析析程

38、程序序的的语语句句、程程序序块块和和函函数数时时，可可用用局局部部的的规规模模参参数数作作为为复复杂杂性性函函数数的的自自变变量量。整整个个程程序序的的复杂性函数还是以整个程序的输入规模为自变量复杂性函数还是以整个程序的输入规模为自变量对对串串行行算算法法，其其时时间间复复杂杂性性等等于于相相应应程程序序每每个个语语句句的的时时间间复复杂杂性性之之和和。若若对对每每种种语语句句所所需需时时间间都都有度量规则，则算法所需时间就是一个求和问题有度量规则，则算法所需时间就是一个求和问题运用运用O、和和 的运算规则就可进行所需分析的运算规则就可进行所需分析39算法复杂性渐近阶的分析算法复杂性渐近阶的分

39、析基本运算和基本语句基本运算和基本语句赋赋值值、比比较较运运算算、算算术术运运算算、逻逻辑辑运运算算和和读读写写变变量等需量等需1个单位时间个单位时间下标变量和结构体的域的访问等需下标变量和结构体的域的访问等需1个单位时间个单位时间if(C)S1 else S2只需只需TC+max(TS1,TS1)个单位时间个单位时间while(C)S所需单位时间数：所需单位时间数：(TC+TS)循环次数循环次数函数调用：控制转移的时间函数调用：控制转移的时间+执行被调函数的时间执行被调函数的时间递递归归函函数数：需需要要从从所所需需时时间间的的归归纳纳定定义义（递递归归方方程）中求解程）中求解基于这些规则可

40、以计算整个程序的复杂性函数基于这些规则可以计算整个程序的复杂性函数40小小 结结本讲座小结本讲座小结概概要要介介绍绍计计算算复复杂杂性性理理论论、计计算算所所需需资资源源的的多多少少是衡量计算复杂性的依据是衡量计算复杂性的依据概要介绍概要介绍复杂性的渐近复杂性的渐近行为、行为、渐近意义下的记号渐近意义下的记号O及其及其运算规则、运算规则、复杂性渐近分析的重要性、算复杂性渐近分析的重要性、算法的复杂性渐近阶的分析法的复杂性渐近阶的分析参考书，参考书，2004帕帕李米特里乌，计算复杂性，清华大学出版社帕帕李米特里乌，计算复杂性，清华大学出版社王晓东，计算机算法设计与分析王晓东，计算机算法设计与分析,电子工业出版社电子工业出版社本讲座的内容大部分取自该书本讲座的内容大部分取自该书41小小 结结与算法分析相关课程与算法分析相关课程数据结构、算法基础、并行计算数据结构、算法基础、并行计算研究方向研究方向挑挑战战性性的的问问题题之之一一：证证明明诸诸如如“NP=？P”这这类类问问题的解是模型相关的题的解是模型相关的各种新型计算模型下的核心算法各种新型计算模型下的核心算法42此课件下载可自行编辑修改，仅供参考！此课件下载可自行编辑修改，仅供参考！感谢您的支持，我们努力做得更好！谢谢感谢您的支持，我们努力做得更好！谢谢