中科大计算机科学导论

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

2、、最好和平均三种情况的时间复杂性 复杂性的渐近行为及其阶 复杂性的渐近行为、渐近意义下的记号O、记号O的运算规则、复杂性渐近分析的重要性 算法复杂性渐近阶的分析 算法的复杂性渐近阶的分析、语句的规则例举,基 本 知 识,计算资源 在计算复杂性理论内，计算资源是指在某个计算模型之下，求解各种问题所要消耗的资源 时间资源：求解问题所需花费的时间，通常用计算步数来度量 空间资源：求解问题所需占用的空间，通常用存储器空间的大小来度量 计算所需资源的多少是衡量计算复杂性的依据 实际应用关心的资源与理论有区别：内存、通信 带宽、硬件等,基 本 知 识,计算复杂性理论 是理论计算机科学和数学的一个分支，它致

3、力于将可计算问题根据其本身固有的难度进行分类，以及把这些类别相互联系起来 若一个问题的求解需要很多的资源（无论用什么算法），则该问题被认为是难解的 通过引入计算模型来研究这些问题，并定量计算解决问题所需的资源（时间和空间），由此把确定资源的方法数学化 作用之一是确定计算机能解和不能解的实际界线,基 本 知 识,计算复杂性理论 相关领域有算法分析和可计算性理论 算法分析致力于分析用一个具体算法求解一个问题所需的资源量，而计算复杂性理论关注的是用所有可能算法解决相同问题层面上的一般性议题 计算复杂性理论尝试把问题分成两类：在适当的资源限制下能解和不能解的问题 资源受限和不受限是区分计算复杂性理论和

4、可计算性理论的一个重要标志：可计算性理论关注的是原则上可以用算法求解的问题,基 本 知 识,算法分析 确定执行一个算法需要消耗的计算资源数量的分析过程 算法的效率或复杂度表示为一个函数，其定义域是输入数据的长度（算法大都设计成允许任意长的输入），值域通常是执行步数（时间复杂度）或所需存储空间数量（空间复杂度） 在算法的理论分析中，通常是估计算法渐近意义上的复杂度 精确分析算法的效率有时也可行，但它通常基于一些与具体实现相关的假设,复杂性的计量,两种查找算法的效率比较 int search(int val) / 顺序查找 int j = 0; /int am无重复且已按从小到大排序 while(

5、aj = 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 = 1; for(i = 0; i = 0，循环算法 int j0, j1, i, temp; j0 = 0; j1 = 1; for(i = 0;

6、i = n; i +) printf(“%dn”, j0); temp = j1; j1 = j0 + j1; j0 = temp; 这个比较单纯反映作为算法精髓的计算方法本身 的效率，不涉及运行这些算法的实际计算机的性能,复杂性的计量,复杂性函数 时间和空间复杂性函数分别是：T(N, I)和S(N, I) N：问题规模， I：算法的输入 问题 问题的规模N 在数组中查找值为val的分量 数组中分量个数 矩阵相乘 矩阵的阶 数表的排序 数表中的项数 遍历二叉树 树中节点数 求数列的前n项 项数n 解有关图的问题 图中节点数或边数,复杂性的计量,复杂性函数 时间和空间复杂性函数分别是：T(N,

7、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),复杂性的计量,三种时间复杂性函数 最坏情况 Tmax(N) = max T(N, I) = ti ei (N, I) = T(N, I) 其中DN为规模为N的合法输入集, I是达max的输

8、入 最好情况（其中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的概率,IDN,IDN,IDN,IDN,= max ti ei (N, I),IDN,复杂性的渐近行为及其阶,复杂性的渐近行为（asymptotic behavior） 对于算法A的T(N)，一般来说，当N单调递增且趋 于时， T(N)也单调递增且趋于 对于T(N)，若存在T(N)，使得当N 时有 (T(N) T(N) / T(N

9、) 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 时的复杂 性的度量，则复杂性分析明显简化 复杂性分析在于比较同一问题的不同算法的效率, 若两

10、个算法的阶可确定且不同，则可判断谁效率高 渐近性分析只要关心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（代表order of ） 若存在大于0的常数C和自然数N0, 使得N N0

11、时有 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（代表order of ） 若存在大于0的常数C和自然数N0, 使得N N0时有 f(N)

12、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),复杂性的渐近行为及其阶,顺序查找算法回顾 int search(int val) / 顺序查找 int j = 0; / int am不重复且已按从小到大排序 while(aj val ,若赋值、比较和返回执行一次所需时间分别是a,

13、 t和r，若val 等于a0，则Tmin(m) = a + 2t + r，其中m是问题规模,复杂性的渐近行为及其阶,渐近意义下的记号O（代表order of ） 若存在大于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)

14、,复杂性的渐近行为及其阶,例：估计下面二重循环的最坏时间复杂性的阶 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) (1+2+ +N) + (a + t) N 因此上界为O(N2)，因为1+2+ +N = N(N+1)/2,复杂性的渐近行为及其阶,例：估计下面二重循环的最坏时间复杂性的阶 for(i

15、 = 1; i N; i+) for(j = 1; j 0.N N0. 0 f(N) Cg(N) 符号O(g(N) 在此给出了明确的数学表达 写f(N) O(g(N)容易理解 而各本书都用的f(N) = O(g(N)则难理解 对2N2+3N+1 = 2N2+O(N)即表示 2N2+3N+1 = 2N2+f(N), 其中f(N) = 3N+1O(N) 也不容易理解 在学习算法分析时，O是既可爱也可恨的记号,复杂性的渐近行为及其阶,其他渐近意义下的记号 下界记号 若存在大于0的常数C和自然数N0，使得N N0时 有f(N) Cg(N), 则称函数f(N)在N充分大时有下界, 且g(N)是它的一个下

16、界，记为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)同阶 还有其他记号,复杂性的渐近行为及其阶,算法与渐近时间复杂性的关系 算法 渐近复杂 在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

17、+ log10 A6 N! N16 N26 N26=N16+小的常数 同一问题六个算法, 在计算机C1和C2运行, C2比C1快 10倍. 从Ti(N2i)=10Ti(N1i)(i =1, , 6)解出关系式见上表,复杂性的渐近行为及其阶,复杂性渐近分析的重要性 对于低效算法，计算机速度数10甚至100倍的增长基本上不带来求解规模的增益 限制求解问题规模的关键因素是算法渐近复杂性的阶 前四个算法的渐近时间复杂性与规模N的一个确定的幂同阶，机器速度的乘法增长带来求解规模的乘法增长。这类算法称为多项式算法 后两个算法的渐近时间复杂性与规模N的一个函数同阶，只能带来求解规模的加法增长 这些结论在问题

18、规模充分大时才成立,算法复杂性渐近阶的分析,如何分析具体算法的复杂性渐近阶 算法是用程序来表达的，算法复杂性渐近阶分析就是对其程序的相应分析 针对所用编程语言，给出一套可操作的分析规则 分析程序的语句、程序块和函数时，可用程序的输入规模作为复杂性函数的自变量，也可用局部的规模参数作为自变量 对串行算法，其时间复杂性等于相应程序每个语句的时间复杂性之和。若对每种语句所需时间都有度量规则，则算法所需时间就是一个求和问题 运用O、 和 的运算规则就可进行所需分析,算法复杂性渐近阶的分析,基本运算和基本语句 赋值、比较、算术和逻辑运算等语句的规则例举需1个单位时间 下标变量和结构体的域的访问等需1个单位时间 if(C) S1 else S2只需TC + max(TS1, TS1)个单位时间 while(C) S所需单位时间数：(TC + TS) 循环次数 函数调用：控制转移的时间+执行被调函数的时间 递归函数：需要从所需时间的归纳定义中求解,小