计算复杂性和算法分析 计算机科学导论第六讲 计算机科学技术学院 陈意云 0551-63607043, yiyun@ustc.edu.cn http://staff.ustc.edu.cn/~yiyun/

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

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

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

基 本 知 识 计算资源 在计算复杂性理论内，计算资源是指在某个计算模型之下，求解一个问题所要消耗的资源 时间资源：求解问题所需花费的时间，通常用计算步数来度量 空间资源：求解问题所需占用的空间，通常用存储器空间的大小来度量 计算所需资源的多少是衡量计算复杂性的依据 实际应用关心的资源与理论上的有区别：硬件资 源（如计算机、存储器）、软件资源、网络资源 （如通信带宽）等 5

基 本 知 识 计算复杂性理论 是理论计算机科学和数学的一个分支，它致力于将可计算问题根据其本身固有的难度进行分类，以及把这些类别相互联系起来 它尝试把问题分成两类：在适当的资源限制下能解(容易)和不能解(困难)的问题。一个问题，若求解需很多资源(无论什么算法), 则被认为是难解的 通过引入计算模型来研究这些问题，并给出定量计算解决问题所需的资源 (时间和空间) 的方法，由此把确定资源的方法数学化 作用之一是确定计算机能解和不能解的实际界线 6

基 本 知 识 计算复杂性理论 研究问题之一：NP =? P P (Polynomial)：在确定型图灵机上有多项式时间算法的问题的集合 NP (Nondeterministic Polynomial)：在非确定型图灵机上有多项式时间算法的问题的集合 NP =? P：是计算机科学中非常重要而又经历了几十年始终未解决的一个问题 它的解决可导致一系列理论问题的解决 7

基 本 知 识 算法分析 确定执行一个算法需要消耗的计算资源的数量的分析过程 算法的效率或复杂度表示为一个函数，其定义域是输入数据的规模（长度，算法大都设计成允许任意长的输入），值域通常是执行步数（时间复杂度）或所需存储空间数量（空间复杂度） 在算法的理论分析中，通常是估计算法渐近意义上的复杂度 精确分析算法的复杂度有时也可行，但它通常基于一些与具体实现相关的假设 8

基 本 知 识 可计算性、计算复杂性和算法分析的区别 算法分析致力于分析求解一个问题的某个具体算法所需的资源量 计算复杂性理论关注的是用所有可能算法解决同一类问题层面上的一般性议题 可计算性理论关注的是原则上可以用算法求解的问题（把问题区分为可计算和不可计算） 资源受限和不受限是区分计算复杂性理论和可计算性理论的一个重要标志 9

复杂性的计量 两种查找算法的效率比较 int search(int val) { // 顺序查找 int j = 0; //int a[m]无重复且已按从小到大排序 while(a[j] < val && j < m 1) { j = j +1; } if (a[j] == val) { return j; } else { return 1; }// 在最坏情况下，需要把val与a的所有分量比较 10

复杂性的计量 两种查找算法的效率比较 int search(int val) { // 二分查找 int i, j, k; //int a[m]无重复且已按从小到大排序 i = 0; j = m 1; while(i <= j) { k = i + (j  i)/2; if (val <= a[k]) j = k  1; if (val >= a[k]) i = k + 1; } if (j  i ==  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(“%d\n”, 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)被重复计算多次

复杂性的计量 两种求斐波那契数列前n+1项算法的效率比较 void Fibonacci(int n) { // 假定n >= 0，循环算法 int j0, j1, i, temp; j0 = 0; j1 = 1; for(i = 0; i <= n; i ++) { printf(“%d\n”, j0); temp = j1; j1 = j0 + j1; j0 = temp; } ak(0  k  n)都只计算1次, 显然效率高于前一个算法

复杂性的计量 两种求斐波那契数列前n+1项算法的效率比较 void Fibonacci(int n) { // 假定n >= 0，循环算法 int j0, j1, i, temp; j0 = 0; j1 = 1; for(i = 0; i <= n; i ++) { printf(“%d\n”, j0); temp = j1; j1 = j0 + j1; j0 = temp; } 这种比较单纯反映作为算法精髓的计算方法本身 的效率，不涉及运行这些算法的实际计算机的性能

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

复杂性的计量 复杂性函数 时间和空间复杂性函数分别是：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) i=1 k

复杂性的计量 复杂性函数 有关算法的输入I 不可能为规模为N的每一种合法输入I 都去统计 ei (N, I) 简化办法：在规模为N的某些或某类有代表性的合法输入中统计相应的ei ，评价这些情况下的时间复杂性

复杂性的计量 三种时间复杂性函数 = max ti ei (N, I) 最坏情况 k 三种时间复杂性函数 最坏情况 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的概率 = max ti ei (N, I) IDN i=1 k IDN i=1 k IDN i=1 k IDN IDN

复杂性的渐近行为及其阶 如何简化算法分析 计算机解决的问题越来越复杂，规模越来越大 若按先前介绍的方法，把所有的元计算都考虑进去，并进行精确分析，则算法分析的步骤之多，工作量之大，令人难以承受 下面介绍复杂性渐近行为的概念，以简化算法分析

复杂性的渐近行为及其阶 复杂性的渐近行为（asymptotic behavior） 对于算法A的T(N)，一般来说，当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)略去低项后的主项 例：若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 时的复杂 性的度量，则复杂性分析明显简化 复杂性分析的目的：在于比较同一问题的不同算 法的效率，若两个算法的阶不同，则可知谁效率高 ～ ～ ～ ～

复杂性的渐近行为及其阶 复杂性的渐近行为 对于T(N)，若存在T(N)，使得当N 时有 (T(N)  T(N)) / T(N)  0 则称T(N)为算法A的当N 时的渐近复杂性 简化T(N)分析：只需关心T(N)的阶，把其常数因 子忽略。如在3N2中，不用关心系数 3 进一步简化T(N)分析：假设算法中用到的所有不 同的元运算执行一次都只需一个时间单位 ～ ～ ～ ～ ～ ～

复杂性的渐近行为及其阶 算法复杂性的渐近分析方法 只要考察当问题规模充分大时，算法复杂性在渐 近意义下的阶。算法分析通常都是这么做的 与此简化的复杂性分析相配套，需要引入一些渐 近意义下的记号

复杂性的渐近行为及其阶 渐近意义下的记号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))记号的含义是什么？

复杂性的渐近行为及其阶 渐近意义下的记号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 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 function terms. 见https://en.wikipedia.org/wiki/ Abuse_of_notation#Big_O_notation(网页已被删去)

复杂性的渐近行为及其阶 渐近意义下的记号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的定义)

复杂性的渐近行为及其阶 渐近意义下的记号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  N2 N3，故N2 = O(N3)

复杂性的渐近行为及其阶 渐近意义下的记号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)

复杂性的渐近行为及其阶 顺序查找算法回顾 int search(int val) { // 顺序查找 int j = 0; // int a[m]不重复且已按从小到大排序 while(a[j] < val && j < m 1) { j = j +1; } // 在最好情况下，val == a[0], if (a[j] == val) { // 把val与a第1个分量比较即可 return j; } else { return 1; } 若赋值、比较和返回执行一次所需时间分别是a, t和r，若val 等于a[0]，则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)的阶 对于顺序查找算法，在最好情况下，只要取 C = a + 2t + r，就有Tmin(m)  C  1， 因此有Tmin(m)  Cg(m)，其中g(m) = 1， 即Tmin(m) = O(1)

复杂性的渐近行为及其阶 例：估计下面二重循环的最坏时间复杂性的阶 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

复杂性的渐近行为及其阶 例：估计下面二重循环的最坏时间复杂性的阶 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) 这是规模充分大时的上界 这个上界的阶越低，则评估就越精确，结果就越有价值

复杂性的渐近行为及其阶 关于记号O(g(N))的讨论 当讨论复杂算法上界时，很希望上界记号O(g(N)) 能参与到复杂性计算中 例如，上例内循环的上界O(i)，则累加起来便是外循环的时间复杂性 T(N) = O(i) = O(i) = O(N(N+1)/2) = O(N2) 若希望如此，则需要有一些演算规则，并证明其 正确性 i=1 n i=1 n

复杂性的渐近行为及其阶 关于记号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)< g(N)

复杂性的渐近行为及其阶 关于记号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))记号，使得读者难理解

复杂性的渐近行为及其阶 其他渐近意义下的记号 下界记号 若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)同阶 还有其他记号 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的速度是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)解出关系式见上表 3 38

复杂性的渐近行为及其阶 复杂性渐近分析的重要性 对于低效算法，计算机速度数10甚至100倍的增长基本上不带来求解规模的增益 限制求解问题规模的主要根源是算法渐近复杂性的阶  前四个算法的渐近时间复杂性与规模N的一个确定的幂同阶，机器速度的乘法增长带来求解规模的乘法增长。这类算法称为多项式算法  后两个算法的渐近时间复杂性与规模N的一个指数函数同阶，只能带来求解规模的加法增长 这些结论在问题规模充分大时才成立 39

算法复杂性渐近阶的分析 如何分析具体算法的复杂性渐近阶 算法是用程序来表达的，算法复杂性渐近阶分析就是对其程序的相应分析 针对所用编程语言，给出一套可操作的分析规则 分析程序的语句、程序块和函数时，可用局部的规模参数作为复杂性函数的自变量。整个程序的复杂性函数还是以整个程序的输入规模为自变量 对串行算法，其时间复杂性等于相应程序每个语句的时间复杂性之和。若对每种语句所需时间都有度量规则，则算法所需时间就是一个求和问题 运用O、 和 的运算规则就可进行所需分析 40

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

小 结 本讲座小结 参考书，2004 概要介绍计算复杂性理论、计算所需资源的多少是衡量计算复杂性的依据 小 结 本讲座小结 概要介绍计算复杂性理论、计算所需资源的多少是衡量计算复杂性的依据 概要介绍复杂性的渐近行为、渐近意义下的记号O及其运算规则、复杂性渐近分析的重要性、算法的复杂性渐近阶的分析 参考书，2004 帕帕李米特里乌，计算复杂性，清华大学出版社 王晓东，计算机算法设计与分析, 电子工业出版社 本讲座的内容大部分取自该书 42

小 结 与算法分析相关课程 研究方向 数据结构、算法基础、并行计算 挑战性的问题之一：证明诸如“NP =？P”这类问题的解是模型相关的 小 结 与算法分析相关课程 数据结构、算法基础、并行计算 研究方向 挑战性的问题之一：证明诸如“NP =？P”这类问题的解是模型相关的 各种新型计算模型下的核心算法 43