《计算复杂性优秀PPT.ppt》由会员分享，可在线阅读，更多相关《计算复杂性优秀PPT.ppt（43页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、计算困难性和算法分析计算困难性和算法分析计算机科学导论第六讲计算机科学导论第六讲计算机科学技术学院计算机科学技术学院陈意云陈意云0551-63607043,yiyunustc.edu :/staff.ustc.edu/yiyun/课课 程程 内内 容容课程内容课程内容围绕学科理论体系中的模型理论围绕学科理论体系中的模型理论,程序理论和程序理论和计算理论计算理论1.模型理论关切的问题模型理论关切的问题 给定模型给定模型M，哪些问题可以由模型，哪些问题可以由模型M解决；解决；如何比较模型的表达实力如何比较模型的表达实力2.程序理论关切的问题程序理论关切的问题给定模型给定模型M，如何用模型，如何用模
2、型M解决问题解决问题包括程序设计范型、程序设计语言、程序设包括程序设计范型、程序设计语言、程序设计、形式语义、类型论、程序验证、程序分计、形式语义、类型论、程序验证、程序分析等析等3.计算理论关切的问题计算理论关切的问题给定模型给定模型M和一类问题和一类问题,解决该类问题需解决该类问题需多少资源多少资源本讲座用简洁的例子来扼要本讲座用简洁的例子来扼要介绍计算困难性和算法分析介绍计算困难性和算法分析2讲讲 座座 提提 纲纲基本学问基本学问可计算理论可计算理论,计算资源计算资源,计算困难性理论计算困难性理论,算算法分析法分析困难性的计量困难性的计量问题规模、困难性函数、最坏、最好和平均问题规模、困
3、难性函数、最坏、最好和平均三种状况的时间困难性三种状况的时间困难性困难性的渐近行为及其阶困难性的渐近行为及其阶困难性的渐近行为、渐近意义下的记号困难性的渐近行为、渐近意义下的记号O、记、记号号O的运算规则、困难性渐近阶分析的重要性的运算规则、困难性渐近阶分析的重要性算法困难性渐近阶的分析算法困难性渐近阶的分析算法的困难性渐近阶的分析、语句规则的例算法的困难性渐近阶的分析、语句规则的例举举3基基 本本 知知 识识可可计计算理算理论论探探讨计讨计算的一般性算的一般性质质的数学理的数学理论论，也称算法，也称算法理理论论通通过过建立建立计计算的数学模型算的数学模型,区分可区分可计计算与不行算与不行计计
4、算算可可计计算函数：能算函数：能够够在抽象在抽象计计算机上算机上编编出程序出程序计计算其算其值值的函数。的函数。这样这样的程序称的程序称为为算法算法这样这样就可以探就可以探讨讨哪些函数是可哪些函数是可计计算的，哪些算的，哪些函数是不行函数是不行计计算的算的可可计计算性：指一个算性：指一个实际问题实际问题是否可以运用是否可以运用计计算机来解决（能解决确定是指有限步内解决）算机来解决（能解决确定是指有限步内解决）上一上一讲讲介介绍绍的就是的就是计计算模型和可算模型和可计计算函数算函数4基基 本本 知知 识识计计算算资资源源在在计计算困算困难难性理性理论论内，内，计计算算资资源是指在某个源是指在某个
5、计计算模型之下，求解一个算模型之下，求解一个问题问题所要消耗的所要消耗的资资源源时间资时间资源：求解源：求解问题问题所需花所需花费费的的时间时间，通常，通常用用计计算步数来度量算步数来度量空空间资间资源：求解源：求解问题问题所需占用的空所需占用的空间间，通常，通常用存用存储储器空器空间间的大小来度量的大小来度量计计算所需算所需资资源的多少是衡量源的多少是衡量计计算困算困难难性的依性的依据据实际应实际应用关切的用关切的资资源与理源与理论论上的有区分：上的有区分：硬件硬件资资源（如源（如计计算机、存算机、存储储器）、器）、软软件件资资源、源、网网络资络资源（如通信源（如通信带宽带宽）等）等 5基基
6、 本本 知知 识识计计算困算困难难性理性理论论是理是理论计论计算机科学和数学的一个分支，它致算机科学和数学的一个分支，它致力于将可力于将可计计算算问题问题依据其本身固有的依据其本身固有的难难度度进进行分行分类类，以及把，以及把这这些些类别类别相互相互联联系起来系起来它它尝试尝试把把问题问题分成两分成两类类：在适当的：在适当的资资源限制源限制下能解下能解(简洁简洁)和不能解和不能解(困困难难)的的问题问题。一个。一个问问题题，若求解需很多，若求解需很多资资源源(无无论论什么算法什么算法),则则被被认为认为是是难难解的解的通通过过引入引入计计算模型来探算模型来探讨这讨这些些问题问题，并，并给给出出
7、定量定量计计算解决算解决问题问题所需的所需的资资源源(时间时间和空和空间间)的方法，由此把确定的方法，由此把确定资资源的方法数学化源的方法数学化作用之一是确定作用之一是确定计计算机能解和不能解的算机能解和不能解的实际实际界界线线6基基 本本 知知 识识计计算困算困难难性理性理论论探探讨问题讨问题之一：之一：NP=?PP(Polynomial)：在确定型：在确定型图图灵机上有多灵机上有多项项式式时间时间算法的算法的问题问题的集合的集合NP(Nondeterministic Polynomial)：在非确定：在非确定型型图图灵机上有多灵机上有多项项式式时间时间算法的算法的问题问题的集合的集合NP=
8、?P：是：是计计算机科学中特算机科学中特别别重要而又重要而又经验经验了几十年始了几十年始终终未解决的一个未解决的一个问题问题它的解决可它的解决可导导致一系列理致一系列理论问题论问题的解决的解决7基基 本本 知知 识识算法分析算法分析确定执行一个算法须要消耗的计算资源的数确定执行一个算法须要消耗的计算资源的数量的分析过程量的分析过程算法的效率或困难度表示为一个函数，其定算法的效率或困难度表示为一个函数，其定义域是输入数据的规模（长度，算法大都设义域是输入数据的规模（长度，算法大都设计成允许随意长的输入），值域通常是执行计成允许随意长的输入），值域通常是执行步数（时间困难度）或所需存储空间数量步数
9、（时间困难度）或所需存储空间数量（空间困难度）（空间困难度）在算法的理论分析中，通常是估计算法渐近在算法的理论分析中，通常是估计算法渐近意义上的困难度意义上的困难度精确分析算法的困难度有时也可行，但它通精确分析算法的困难度有时也可行，但它通常基于一些与具体实现相关的假设常基于一些与具体实现相关的假设8基基 本本 知知 识识可可计计算性、算性、计计算困算困难难性和算法分析的区分性和算法分析的区分算法分析致力于分析求解一个算法分析致力于分析求解一个问题问题的某个具的某个具体算法所需的体算法所需的资资源量源量计计算困算困难难性理性理论论关注的是用全部可能算法解关注的是用全部可能算法解决同一决同一类问
10、题层类问题层面上的一般性面上的一般性议题议题可可计计算性理算性理论论关注的是原关注的是原则则上可以用算法求上可以用算法求解的解的问题问题（把（把问题问题区分区分为为可可计计算和不行算和不行计计算）算）资资源受限和不受限是区分源受限和不受限是区分计计算困算困难难性理性理论论和和可可计计算性理算性理论论的一个重要的一个重要标记标记9困难性的计量困难性的计量两种两种查查找算法的效率比找算法的效率比较较int search(int val)/依次依次查查找找int j=0;/int am无重复且已按从小到大无重复且已按从小到大排序排序while(aj val&j m 1)j=j+1;if(aj=val
11、)return j;else return 1;/在最坏状况下，在最坏状况下，须须要把要把val与与a的全部重的全部重量比量比较较10困难性的计量困难性的计量两种两种查查找算法的效率比找算法的效率比较较int search(int val)/二分二分查查找找 int i,j,k;/int am无重复且已按从小到大无重复且已按从小到大排序排序 i=0;j=m 1;while(i=j)k=i+(j i)/2;if(val=ak)i=k+1;if(j i=1)return 1;else return k;/在最坏状况下，只在最坏状况下，只须须要把要把val与与a的的log2 m个个 /重量比重量比较
12、较，明，明显显效率高于前一个算法效率高于前一个算法11困难性的计量困难性的计量两种求斐波那契数列前两种求斐波那契数列前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=0，循，循环环算算法法 int j0,j1,i,temp;j0=0;j1=
13、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;这这种比种比较单纯较单纯反映作反映作为为算法精髓的算法精髓的计计算方法本身算方法本身的效率，不涉及运行的效率，不涉及运行这这些算法的些算法的实际计实际计算机的性能算机的性能14困难性的计量困难性的计量困难性函数困难性函数时间和空间困难性函数分别是：时间和空间困难性函数分别是：T(N,I)和和S(N,I)N：问题规模，：问题规模，I：算法的输入：算法的输入问题问题问题的规模问题的规模N
14、在数组中查找值为在数组中查找值为val的重量的重量 数组中重量个数数组中重量个数矩阵相乘矩阵相乘矩阵的阶矩阵的阶数表的排序数表的排序数表中的项数数表中的项数遍历二叉树遍历二叉树树中节点数树中节点数求数列的前求数列的前n项项项数项数n解有关图的问题解有关图的问题图中节点数或边图中节点数或边数数15困难性的计量困难性的计量困难性函数困难性函数时间和空间困难性函数分别是：时间和空间困难性函数分别是：T(N,I)和和S(N,I)N：问题规模，：问题规模，I：算法的输入：算法的输入时间困难性和空间困难性的概念类同，计算时间困难性和空间困难性的概念类同，计算方法方法相像，且空间困难性分析相对简洁，因此下相
15、像，且空间困难性分析相对简洁，因此下面仅讨面仅讨论时间困难性论时间困难性若抽象计算机有若抽象计算机有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=1k16困难性的计量困难性的计量困难性函数困难性函数有关算法的输入有关算法的输入I不行能为规模为不行能为规模为N的每一种合法输入的每一种合法输入I 都去统都去统计计 ei(N,I)简化方法：在规模为简化方法：在规模为N的某些或某类
16、有代表性的某些或某类有代表性的合法输入中统计相应的的合法输入中统计相应的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,I)其中其中P(I
17、)是在算法的应用中出现输入是在算法的应用中出现输入I的概率的概率i=1kI D DNI D DNi=1kI D DNI D DNi=1k=max ti ei(N,I)I D DNi=1k18困难性的渐近行为及其阶困难性的渐近行为及其阶如何简化算法分析如何简化算法分析计算机解决的问题越来越困难，规模越来越计算机解决的问题越来越困难，规模越来越大大若按从前介绍的方法，把全部的元计算都考若按从前介绍的方法，把全部的元计算都考虑进去，并进行精确分析，则算法分析的步虑进去，并进行精确分析，则算法分析的步骤之多，工作量之大，令人难以承受骤之多，工作量之大，令人难以承受下面介绍困难性渐近行为的概念，以简化算
18、下面介绍困难性渐近行为的概念，以简化算法分析法分析19困难性的渐近行为及其阶困难性的渐近行为及其阶困难性的渐近行为（困难性的渐近行为（asymptotic behavior）对于算法对于算法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)略去低项后的
19、主项略去低项后的主项 例：若例：若T(N)是是3N2+4Nlog2N+7时，时，T(N)可以可以是是3N2,若若N ，(4Nlog2N+7)/(3N2+4Nlog2N+7)0N2称为阶称为阶20困难性的渐近行为及其阶困难性的渐近行为及其阶困难性的渐近行为困难性的渐近行为对于对于T(N)，若存在，若存在T(N)，使得当，使得当N 时有时有 (T(N)T(N)/T(N)0则称则称T(N)为算法为算法A的当的当N 时的渐近困难性时的渐近困难性若用若用T(N)代替代替T(N)，作为算法，作为算法A在在N 时的时的困难困难性的度量，则困难性分析明显简化性的度量，则困难性分析明显简化困难性分析的目的：在于
20、比较同一问题的不困难性分析的目的：在于比较同一问题的不同算同算法的效率，若两个算法的阶不同，则可知谁法的效率，若两个算法的阶不同，则可知谁效率高效率高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)分析：假设算法中用到的
21、全分析：假设算法中用到的全部不部不同的元运算执行一次都只需一个时间单位同的元运算执行一次都只需一个时间单位22困难性的渐近行为及其阶困难性的渐近行为及其阶算法困难性的渐近分析方法算法困难性的渐近分析方法只要考察当问题规模充分大时，算法困难性只要考察当问题规模充分大时，算法困难性在渐近意义下的阶。算法分析通常都是这么在渐近意义下的阶。算法分析通常都是这么做的做的与此简化的困难性分析相配套，须要引入一与此简化的困难性分析相配套，须要引入一些渐近意义下的记号些渐近意义下的记号23困难性的渐近行为及其阶困难性的渐近行为及其阶渐近意义下的记号渐近意义下的记号O（代表（代表order of）若若f 和和g
22、是正整数集上的正函数，若存在大于是正整数集上的正函数，若存在大于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
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)，并简称，并简称f(N)不大于不大于g(N)的的阶阶Intuitively this notation groups functions accordingto their growth respective
24、 to some parameter;as such,the notation is abusive in two respects:It abuses=,and it invokes terms that are real numbers instead ofAbuse_of_notation#Big_O_notation(网页已被网页已被删去删去)25困难性的渐近行为及其阶困难性的渐近行为及其阶渐近意义下的记号渐近意义下的记号O（代表（代表order of）若若f 和和g是正整数集上的正函数，若存在大于是正整数集上的正函数，若存在大于0的常的常数数C和自然数和自然数N0，使得，使得N N0
25、时有时有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（代表（代表orde
26、r 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)的阶的阶 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困难性的渐近行为及其阶困难性的渐近行为及其阶渐近意义下
27、的记号渐近意义下的记号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)的的阶阶N3 O(N2)（运用（运用“”也是一种滥用）也是一种滥用）若不是这样，则存在大于若不是这样，则存在大于0的常数的常数C和自然和自然数数N0,使得使得N N0时有时有N3 CN2，即，即N C取取N=max(N
28、0,C +1)时，该不等时，该不等式不成立，故式不成立，故N3 O(N2)28困难性的渐近行为及其阶困难性的渐近行为及其阶依次依次查查找算法回找算法回顾顾int search(int val)/依次依次查查找找int j=0;/int am不重复且已按从小不重复且已按从小到大排序到大排序while(aj val&j m 1)j=j+1;/在最好状况下，在最好状况下，val=a0,if(aj=val)/把把val与与a第第1个重量比个重量比较较即可即可 return j;else return 1;若赋值、比较和返回执行一次所需若赋值、比较和返回执行一次所需时间分别是时间分别是a,t和和r，若，
29、若val 等于等于a0，则则Tmin(m)=a+2t+r，其中，其中m是是问题问题规规模模29困难性的渐近行为及其阶困难性的渐近行为及其阶渐近意义下的记号渐近意义下的记号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)的的阶阶对于依次查找算法，在最好状况下，只要取对于依次查找算法，在最好
30、状况下，只要取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)都是赋值语句都是赋值语句对内循环体，执行一次须要的时间是对内循环体，执行一次须要的时间是4a加上循环限制，则是加上循环限制，则是5a+t内循环执行内循环执行i 次次,需时间需时间(5a+t)i,因此上
31、界为因此上界为 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、就越精确，结果就越有价值越有价值32困难性的渐近行为及其阶困难性的渐近行为及其阶关于记号关于记号O(g(N)的探讨的探讨当探讨困难算法上界时，很希望上界记号当探讨困难算法上界时，很希望上界记号O(g(N)能参与到困难性计算中能参与到困难性计算中例如，上例内循环的上界例如，上例内循环的上界O(i)，则累加起来便，则累加起来便是外循环的时间困难性是外循环的时间困难性T(N)=O(i)=O(i)=O(N(N+1)/2)=O(N2)若希望如此，则须要有一些演算规则，并证若希望如此，则须要有一些演算规则，并证明其正确性明其正确性i=1ni=1n33困难性的渐近行为及其阶困难性的渐近行为及其阶关于记号关于
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(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)但说
34、明但说明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充分大时，充分大时，Cg(N)是函数是函数f(N)的一个的一个下下界，界，记为记为f(N)=(g(
35、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个个算算法法在
36、在C1上上运运行行10倍倍于于C2上上运运行行的的时时间间，则等号两边效果一样则等号两边效果一样 同同一一问问题题六六个个算算法法,在在C1和和C2上上运运行行,C2的速度是的速度是C110倍倍.从从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 10N
37、12 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)=10Ti(N1i)(i=1,6)解解出出关关系式见上表系式见上表 338困难性的渐近行为及其阶困难性的渐近行为及其阶困难性渐近分析的重要性困难性渐近分析的重要性对对于于低低效效算算法法，计计算算机机速速度度数数10甚甚至至100倍倍的的增长基本上不带来求解规模的增益
38、增长基本上不带来求解规模的增益限限制制求求解解问问题题规规模模的的主主要要根根源源是是算算法法渐渐近近困困难性的阶难性的阶 前前四四个个算算法法的的渐渐近近时时间间困困难难性性与与规规模模N的的一一个个确确定定的的幂幂同同阶阶，机机器器速速度度的的乘乘法法增增长长带带来来求求解解规规模模的的乘乘法法增增长长。这这类类算算法法称称为为多多项式算法项式算法 后后两两个个算算法法的的渐渐近近时时间间困困难难性性与与规规模模N的的一一个个指指数数函函数数同同阶阶，只只能能带带来来求求解解规规模模的的加法增长加法增长这些结论在问题规模充分大时才成立这些结论在问题规模充分大时才成立39算法困难性渐近阶的分
39、析算法困难性渐近阶的分析如何分析具体算法的困难性渐近阶如何分析具体算法的困难性渐近阶算算法法是是用用程程序序来来表表达达的的，算算法法困困难难性性渐渐近近阶阶分析就是对其程序的相应分析分析就是对其程序的相应分析针针对对所所用用编编程程语语言言，给给出出一一套套可可操操作作的的分分析析规则规则分分析析程程序序的的语语句句、程程序序块块和和函函数数时时，可可用用局局部部的的规规模模参参数数作作为为困困难难性性函函数数的的自自变变量量。整整个个程程序序的的困困难难性性函函数数还还是是以以整整个个程程序序的的输输入入规模为自变量规模为自变量对对串串行行算算法法，其其时时间间困困难难性性等等于于相相应应
40、程程序序每每个个语语句句的的时时间间困困难难性性之之和和。若若对对每每种种语语句句所所需需时时间间都都有有度度量量规规则则，则则算算法法所所需需时时间间就就是是一个求和问题一个求和问题运用运用O、和和 的运算规则就可进行所需分析的运算规则就可进行所需分析40算法困难性渐近阶的分析算法困难性渐近阶的分析基本运算和基本语句基本运算和基本语句赋赋值值、比比较较运运算算、算算术术运运算算、逻逻辑辑运运算算和和读读写变量等需写变量等需1个单位时间个单位时间下下标标变变量量和和结结构构体体的的域域的的访访问问等等需需1个个单单位位时时间间if(C)S1 else S2只只需需TC+max(TS1,TS1)
41、个个单单位时间位时间while(C)S所所需需单单位位时时间间数数：(TC+TS)循循环环次数次数函函数数调调用用：限限制制转转移移的的时时间间+执执行行被被调调函函数数的的时间时间递递归归函函数数：须须要要从从所所需需时时间间的的归归纳纳定定义义（递递归方程）中求解归方程）中求解基基于于这这些些规规则则可可以以计计算算整整个个程程序序的的困困难难性性函函数数41小小 结结本讲座小结本讲座小结概概要要介介绍绍计计算算困困难难性性理理论论、计计算算所所需需资资源源的的多少是衡量计算困难性的依据多少是衡量计算困难性的依据概概要要介介绍绍困困难难性性的的渐渐近近行行为为、渐渐近近意意义义下下的的记记
42、号号O及及其其运运算算规规则则、困困难难性性渐渐近近分分析析的的重重要要性、算法的困难性渐近阶的分析性、算法的困难性渐近阶的分析参考书，参考书，2004帕帕帕帕李李米米特特里里乌乌，计计算算困困难难性性，清清华华高高校校出出版社版社王王晓晓东东，计计算算机机算算法法设设计计与与分分析析,电电子子工工业业出出版社版社本讲座的内容大部分取自该书本讲座的内容大部分取自该书42小小 结结与算法分析相关课程与算法分析相关课程数据结构、算法基础、并行计算数据结构、算法基础、并行计算探讨方向探讨方向挑战性的问题之一：证明诸如挑战性的问题之一：证明诸如“NP=？P”这类这类问题的解是模型相关的问题的解是模型相关的各种新型计算模型下的核心算法各种新型计算模型下的核心算法43