计算复杂性和算法分析计算机科学导论第六讲（陈意云）.ppt

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

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

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

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

7、1) return 1; else return k; / 在最坏情况下，只需要把val与a的log2 m个 / 分量比较，显然效率高于前一个算法,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

8、, , an, ak(0 k n)被重复计算多次,12,复杂性的计量,两种求斐波那契数列前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; ak(0 k n)都只计算1次, 显然效率高于前一个算法,13,复杂性的计量,两种求斐波那契数列前n+1项算法的效率比较 void Fibonacci(int n) / 假定n =

9、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 在数组中查找值为val的分量数组中分量个数 矩阵相乘矩阵的阶 数表的排序数表中的项数 遍历二叉树树中节点数 求数列的前n项项

10、数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 =ei (N, I), 则T(N, I) = ti ei (N, I,16,复杂性的计量,复杂性函数 有关算法的输入I 不可能为规模为N的每一种合法输入I 都

11、去统计 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, I) 其中P(I)是在算法的应用中出现输入I的概率,ID

12、N,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) 0 则称T(N)是T(N)当N

13、 时的渐近行为，或称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 时的复杂 性的度量，则复杂性分析明显简化 复杂性分析的目的：在于比较同一问题的不同算 法的效率，若两个算法的阶不同，则可

14、知谁效率高,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,复杂性的渐近行为及其阶,渐近意

15、义下的记号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(g(N)作为一个整体，表达函数f 和g的一种关系 “=”在这里的含义是什么？ 单独的O(g(N)记号的含义是什么,24,复杂性的渐近行为及其阶,渐近意义下的记号O（代表order of ） 若f 和g是正整数集上的正函数，若存在大于0的常 数C和自然数N0，使得N

16、 N0时有f(N) Cg(N), 则 称：在N充分大时，Cg(N)是函数f(N)的一个上界， 记为f(N) = O(g(N)，并简称f(N)不大于g(N)的阶 Intuitively this notation groups functions according to 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 func

17、tion terms. 见/wiki/ Abuse_of_notation#Big_O_notation(网页已被删去,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

18、4N, 故 f(N) = O(N) (f(N) = 3N, g(N) = N, C =4, 下面略去f和g的定义,26,复杂性的渐近行为及其阶,渐近意义下的记号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)的阶 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

19、 N2 N3，故N2 = O(N3,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(N0 , C +1)时，该不等式不成立，故 N3 O(N2,28,复杂性的渐近行为及其阶,顺序查找算法回

20、顾 int search(int val) / 顺序查找 int j = 0; / int am不重复且已按从小到大排序 while(aj val,若赋值、比较和返回执行一次所需时间分别是a, t和r，若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)的阶 对于顺

21、序查找算法，在最好情况下，只要取 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, 因此上界为 O(i) 外循环执行N次，需时间 (5a +t) (

22、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)的讨论 当讨论复杂算法上界时，很希望上界记号O(g(N) 能参与到复杂性计算中 例如，上例内循环

23、的上界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(N), 若f(N)

24、 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

25、 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)同阶 还有其他记号,36,复杂性的渐近行为及其阶,算法与渐近时间复杂性的关系 算法 渐近复杂 在C1上可 在C2上可 N1和N2的关系 性T(N) 解规模N1 解规模N2 方程Ti(N2i)=10Ti(N1i)是求解N2i和N1i之间的关系 等式Ti(N2i)=10Ti(N1i)的含义是：第i个算法在C1上运行10倍于C2上运行的时间，

26、则等号两边效果一样 同一问题六个算法, 在C1和C2上运行, C2的速度是C1 10倍. 从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的速度是C1 10倍. 从Ti(N2i)=10Ti(N1i)(i =1, , 6)解出关系式见上表,38,复杂性的渐近行为及其阶,复杂性渐近分析的重要性 对于低效算法，计算机速度数10