《函数的渐进复杂性》PPT课件.ppt

1 2.2. 函数的渐近复杂性函数的渐近复杂性 第一章第一章 2 问题的模数（size）用一个整数n表示，它是 输入数据的一个量度。 例如，集合的运算，可以是集合的基数； 图的运算，可以是V或e。 算法的计算复杂性（complexity of computation）- 是问题的模数的一个函数 。 3 一个算法所需的机时，表示为n的函数，称该算 法的时间复杂性（time complexity）。 算法是程序的灵魂，程序的性能一般指程序的 空间复杂性和时间复杂性。 算法的好坏，关系到我们所求的问题是否有解算法的好坏，关系到我们所求的问题是否有解 ！ 一个算法所需的存储量，表示为n的函数，称该 算法的空间复杂性（space complexity）。 4 2.12.1 一个实例一个实例 5 6 货郎担问题 - 货郎担问题 （公路调度） 货郎担问题 7 货郎担问题 货郎担问题一般提法为：一个货郎从 某城镇出发，经过若干个城镇一次，且仅 经过一次，最后仍回到原出发的城镇，问 应如何选择行走路线可使总行程最短，这 是运筹学的一个著名的问题。 实际中有很多问题可以归结为这类问题。 8 实际中很多问题都可以归结为货郎担这 类问题。 如： 1) 物资运输路线中，汽车应该走怎样的路线 使路程最短； 2) 工厂里在钢板上要挖一些小圆孔，自动焊 接机的割咀应走怎样的路线使路程最短； 3) 城市里有一些地方铺设管道时，管子应走 怎样的路线才能使管子耗费最少，等等。 9 我们学的数据结构里面也有很多 内容和货郎担问题的思想相似! 10 最小生成树的普里姆算法 11 最短路径问题 DijkstraDijkstra提出了一个按路径长度递增的顺序逐提出了一个按路径长度递增的顺序逐 步产生最短路径的方法，称为步产生最短路径的方法，称为DijkstraDijkstra算法。算法。 12 三个城市，有2!个“遍历”路径，每个路径需 做2次加法，一次比较运算。共有32！运算。 - 有2!个“遍历”路径 货郎担问题 13 四个城市，有3!个“遍历”路径，每个路径需 做3次加法,一次比较运算。共有43！运算。 - 有3!个“遍历”路径 14 n个城市，有（n-1）!个“遍历”路径，每个路径 需做(n-1)次加法,一次比较运算。 共有n(n-1)！=n!运算。 按上述算法，搜索最短路径需要的 时间复杂性为：f(n)=c*n! 空间复杂性为n2（n个边的相邻矩阵）。 显然，时间复杂性 n! 是个explosive问题。 15 例如，若有56个点： 有56个点需做加法： 56！7.11074次 一年秒数： 60秒60分24小时365天3.15107秒 每秒10亿次计算机109次/秒 56！7.11074次加法所需时间： 21063 小时 8.21061 天 2.251059 年 16 由此可见，货郎担问题的时间复杂性是： f(n)=cn! 由以上的条件可知： n的函数是N R+（正实数）的一个映射。 即， 当n是N中的元时（nN），f(n)=cn!R+ 课后思考题？ 中国有34个一级城市，采用穷举法求 连通各个一级城市的最短路径长度， 能计算出来吗？理论上计算需要多少 年？ 请思考：采用哪些近似算法可以得到 满意解？ 17 18 2.22.2 函数的渐进控制函数的渐进控制 19 确定程序的操作计数和执行步数的目的：为了比较 两个完成同一功能的程序的时间复杂性，预测程序 的运行时间随着实例特征变化的变化量。 设 是算法A的复杂性函数。一般说来，当n单调 增加趋于时， 也将单调增加趋于。 如果存在函数 ，使得当 时有 ，则称 是 当 时 的渐近性态，或称 是算法A当 的渐近复 杂性。 20 定义1.2.1：渐进控制 设有 N 到 R+(正实数）的映射f和g， 那么g渐进控制f, 若存在常数m，使 f(n)mg(n), for all nk, k0 即从某一个值k开始，g乘以一固定常数m 之后，总大于f。 21 例1. 设f=3n-1, g=n2, nN 当m=1,k=3时， fmg (在n=3之后，总是gf) g渐进控制f。 22 例2: 设f=cn, g=n fcg, 而g( )*f, for all nN f与g是相互渐进的控制。 23 定理1.2.1: 设F是N到R+（正实数）函数的集合，那么， F的二元关系“渐进控制”自反和可迁。 F的二元关系“相互渐进控制”是F的一个等价关 系（自反、可迁、对称）。 注：.自反：- 若对每个xA，xRx，那么R自反。 .可迁：- xRyyRz xRz，那么，R可迁。 .对称：- 若对每个x,yA，xRy yRx，那么R对称。 注：A为某种关系的集合。 24 定义1.2.2： g渐进控制的所有函数集合，用O(g)表示，称 Order g 或 O(g)。 若fO(g)， 那么称f是O(g)。 25 定理1.2.2： g是O(g) 若f是O(g)，那么cf也是O(g) 若f和h是O(g)，那么f+h也是O(g) 证： 设 fm1g for nk1 hm2g for nk2 那么，f+h(m1+m2)g for nmax(k1,k2) 推理： 多项式a0 + a1n + a2n2+ + arnr 是 O(nr). 26 例3， 2n2+3n+4 n2渐进控制4、3n和2n2， 按定理1.2.2 , 2n2+3n+4 是 O(n2). 27 定理定理1.2.31.2.3： f是O(g),iff（如果且只要是）O(f)O(g). 推理： f是O(g)，g是O(f)，iff O(f)=O(g) 这个推理和定理一样重要，举一简单例子， cn2是O(n2), n2是O(cn2), O(cn2)=O(n2) f=an2+bn+c 是O(n2), n2是O(f), O(f)=O(n2) 28 定义1.2.3： 渐进复杂性 asymptotic complexity 设算法的复杂性函数是f，那么O(f)叫做该算法 的渐进复杂性。 例4, f=an2+bn+c, 那么该算法渐进复杂性是O(f),即O(n2)。 g=bn+c的渐进复杂性是O(g),即O(n)。 29 渐进复杂性的几个重要的类： O(1) f=c 是 O(c)=O(1) 常数复杂性 O(logn) f=logn,log10n=lognlg10 对数复杂性 O(n) 线性复杂性 O(nlogn) 线性对数乘积复杂性 O(n2) 平方复杂性 O(n3) 立方复杂性 O(cn) 指数复杂性 O(n!) 阶乘复杂性 后面一个包含前面一个（一个比一个高阶）： O(1)O(logn)O(n)O(nlogn)O(n2)O(n3)O(cn)O(n!) 30 证: O(nr)O(cn) nrcn 如果 rlognnlogc 但 是增函数，（r不是n的函数）， 不等式在nk后成立。 nrcn 即， nr是O(cn), 而cn不是O(nr) O(nr)O(cn) 31 v衡量 两个算 法的好 坏，应 当是在 n足够 大的情 形下， 对算法 的工作 量进行 比较。 32 函数增长表： v一般情况下，随着n的增大，增长较慢的算法为最优的算法。 v应该选择对数阶或多项式阶的算法，避免使用指数阶的算法。 33 进一步分析可知，要比较两个算法的渐近复杂性的 阶不相同时，只要确定出各自的阶，就可以知道哪 一个算法的效率高。 换句话说，渐近复杂性分析只要关心 的阶就 够了，不必关心包含在 中的常数因子。 所以，我们常常可对 的分析进一步简化，即假 设算法中用到的所有不同的运算（基本）各执行一 次所需要的时间都是一个单位时间。 34 2.32.3 复杂性函数的阶复杂性函数的阶 - 求解函数的上界“OO”，下界“”，同阶“” 35 根据以上分析，我们已经给出了简化算法复杂性分 析的方法和步骤，即只考虑当问题的规模充分大时 ，算法复杂性在渐近意义下的阶。 为此引入渐近符号，首先给出常用的渐近函数。 在下面的讨论中，用f(n)表示一个程序的时间 或空间复杂性，它是实例特征n（一般是输入规模 ）的函数。由于一个程序的时间或空间需求是一个 非负的实数，我们假定函数f(n)对于n的所有取值 均为非负实数，而且还可假定n0。 36 1.1.渐近符号渐近符号O O 的定义：的定义： f(n)=O(g(n) 当且仅当存在正的常数c和n0， 使得对于所有的nn0，有f(n)cg(n)。 此时，称g(n)是f(n)的一个上界。 函数函数f f至多至多是函数是函数g g的的c c倍，除非倍，除非n nn n0 0 . . f(n)的阶小于或等于g(n)的阶 37 即是说，当n充分大时，g是 f 的一个上界函 数，在相差一个非零常数倍的情况下。 例如，例如， 要使要使有 f(n)cg(n) 2=O(n): 可取 c1，n02 100n+6=O(n): 可取 c=101，n06 62n+n2=O(2n): 可取 c =7，n0=4 38 三点注意事项：三点注意事项： 用来作比较的函数g(n)应该尽量接近所考虑 的函数f(n)。 例如，3n+2=O(n2) 松散的界限； 3n+2=O(n) 较好的界限。 不要产生错误界限。 例如，n2+100n+6，当nc-100就有n2+100n+6 cn. 同理，3n2+42n=O(n2)是错误的界限。 39 f(n)=O(g(n)不能写成g(n)=O(f(n)，因为 两者并不等价。 实际上，这里的等号并不是通常相等的含义。 按照定义，用集合符号更准确些： O(g(n)=f(n)|f(n)满足：存在正的常数c和n0， 使得当nn0时，f(n)cg(n) 所以，人们常常把f(n)=O(g(n)读作： “f(n)f(n)的渐进复杂性是的渐进复杂性是O(g)O(g)”， 或者 “f(n)f(n)是是g(n)g(n)的一个大的一个大O O成员成员”。 40 大大O O 比率比率定义：定义： 对于函数f(n)和g(n)，如果极限 存在， 则 当且仅当存在正的常数 c，使得 . 41 例如，例如， 因为 ， 所以 ； 因为 ，所以 ； 因为 ，所以 ； 因为 ，所以 ， - 但是，最后的一个例子并不是一个好的上界估 计，问题出在极限值不是正的常数。 42 定理定理1.2.41.2.4： 对于任意一个正实数x和，有下面的不等式： 存在某个n0使得对于任何nn0 ，有 存在某个n0使得对于任何nn0 ，有 下述不等式对于复杂性阶的估算非常有帮助： 43 存在某个n0使得对于任何nn0 ， 有 . 存在某个n0使得对于任何nn0 ， 有 . 对任意实数y，存在某个n0使得对于任何 nn0 ，有 . 44 例，例， 根据渐进控制的定义，我们很容易得出： 45 2.2.符号符号的定义：的定义： f(n)=(g(n)当且仅当存在正的常数c和n0， 使得对于所有的nn0，有f(n)c(g(n)。 此 时，称g(n)是f(n)的一个下界。 函数函数f f至少至少是函数是函数g g的的c c倍，除非倍，除非n nn n0 0 . . f(n)的阶大于或等于g(n)的阶 46 即是说，即是说，当n充分大时，g是f的一个下界函数，在 相差一个非零常数倍的情况下。类似于大O符号，我 们可以参考定理1.2.4.所列的不等式，来估计复杂性 函数的下界，而且有下述判定规则： 大大比率定理比率定理： 对于函数f(n)和g(n)，如果极限 存在， 则 当且仅当存在正的常数c，使得 . 这里，当n充分大时，g(n)cf(n)意味着 ，由 此不难看出上述判别规则的正确性。 47 3.3.符号符号的定义：的定义： f(n)=(g(n)当且仅当存在正的常数C1，C2 和n0，使得对于所有的nn0，有 此时，称f(n)与g(n)同阶。 48 函数函数f f介于函数介于函数g g的的C C 1 1 和和C C 2 2 倍之间。倍之间。 即，当即，当n n充分大时，充分大时，g g既是既是f f的下界，又是的下界，又是f f的上界。的上界。 例如，例如， 49 比率定理比率定理： 对于函数f(n)和g(n)，如果极限 与 都存在，则f(n)=(g(n)当且仅 当存在正的常数C1和C2，使得 50 定理定理1.2.51.2.5： 对于多项式函数 ， 如果am0 ，则 ， ， . 比较大O比率定理和比率定理，可知，比率定 理实际是那两种情况的综合。对于多项式情形的复杂 性函数，其阶函数可取该多项式的最高项，即即 51 一般情况下，我们不能对每个复杂性函数去 估计它们的上界、下界和“双界”。前面介绍的 定理给了一些直接确定这些界的阶函数（或叫 渐近函数）的参考信息。由这些信息可以给出 多个函数经过加、乘运算组合起来的复杂函数 的阶的估计。 52 算法的阶小结 一般采用求极限的方法，来比较两个算法时间复杂 性函数的阶： 当n时，lim f(n)/g(n)=c (1)当c0，f(n)比g(n)低阶，记为f(n) = O(g(n)； (2)当c0，f(n)和g(n)同阶，记为f(n) =(g(n)； (3)当c，f(n)比g(n)高阶，记为f(n) =(g(n)； 53 算法的阶 写法条件假设近似 f = O(g)nn0 , f(n)cg(n) f =(g)f = O(g) and g = O(f) f =(g)g = O(f) 上界“OO”，下界“”，同阶“ ” 54 例 题 例如：2n-5 = O(n2)，因为当n时，lim (2n -5)/n2 = 2/n - 5/n2 0-0=0；-低阶 例如：5n2 -3n=(n2)，因为当n时，lim (5n2 -3n)/n2 = 5 - 3/n5-0=5；-同阶 例如： n2 +5n=(n)，因为当n时，lim (n2 +5n)/n= n +5 ；-高阶 55 最后 给出 折半 搜索 程序 及算 法复 杂性 估计 ： 程序程序1-2-1 1-2-1 折半搜索折半搜索 template int BinarySearch (T a , const T else right = middle 1; return 1; /未找到x 56 折半搜索折半搜索 例：有11个数据元素的顺序表 （05，13，19，21，37，56，64，75，80，88，92） 序号： 1 2 3 4 5 6 7 8 9 10 11 折半查找法在查找成功时进行比较的关键字个数最多不超 过判定树的深度，而具有n个结点的判定树的深度为 logn+1，所以折半查找法在查找成功时和给定值进行比 较的关键字个数至多为logn+1 。 6 3 1 2 4 5 7 8 9 10 11 57 while 的每次循环（最后一次除外）都将以 减半的比例缩小搜索范围，所以，该循环在最 坏的情况下需要执行 次。 由于每次循环需耗时 ，因此在最坏情况 下，总的时间复杂性为 。 58 2.42.4 循环方程的求解循环方程的求解 59 递归方程递归方程: : 递归方程是使用小的输入值来描述一个函 数的方程或不等式。 例如，例如， Merge-sort 排序算法的复杂性方程: T(n) 的解是(nlogn). 60 求解递归方程的求解递归方程的2 2个主要方法个主要方法: : 1. Substitution（猜解替代）: Guess first，然后用数学归纳法证明。 2. Iteration（循环递归）: 把方程转化为一个和式，然后用和估计技术求解。 61 SubstitutionSubstitution（猜解替代） 一般方法: 猜解的形式 用数学归纳法证明猜测的解正确 - 该方法只能用于解可猜的情况。 2.4.12.4.1 62 2.2.Make a good guessMake a good guess ( (猜测猜测) )： 不幸：不幸： 无一般的猜测正确解的方法，需要 经验 机会 创造性和灵感 幸运：幸运： 存在一些启发规则帮助人们去猜测。 63 GuessGuess方法方法： 联想类似的已知联想类似的已知T(n)T(n) 例例 1:1: 求解 , T(1)=1. 解解: :展开T(n)若干步,可以猜测 T(n)=O(nlogn). 我们需要证明T(n)=O(nlogn). 64 设设1.当nm时都成立. 2.则当 n=m+1时 有： 于是有， . （只要C1） 用数 学归 纳法 证明 猜测 的解 正确 65 * *边界条件的问题边界条件的问题: : 设设T(1)=1T(1)=1是边界条件，是边界条件， 则则T(1)C1log1=0T(1)C1log1=0不成立。不成立。 * *边界条件问题的解决边界条件问题的解决： 我们只要求对于我们只要求对于nnnn 0 0 时，时，T(n)=O(nlogn)T(n)=O(nlogn) . . 我们只需看我们只需看n=2n=2，n=3n=3，或，或4 4等，选一个满足等，选一个满足 T(n)Cnlogn T(n)Cnlogn 的最小