函数的渐进复杂性.ppt

《函数的渐进复杂性.ppt》由会员分享，可在线阅读，更多相关《函数的渐进复杂性.ppt（73页珍藏版）》请在三一办公上搜索。

1、1,2.,函数的渐近复杂性,第一章,2,问题的模数（size）用一个整数n表示，它是输入数据的一个量度。例如，集合的运算，可以是集合的基数；图的运算，可以是V或e。算法的计算复杂性（complexity of computation）-是问题的模数的一个函数。,3,一个算法所需的机时，表示为n的函数，称该算法的时间复杂性（time complexity）。,算法是程序的灵魂，程序的性能一般指程序的空间复杂性和时间复杂性。算法的好坏，关系到我们所求的问题是否有解！,一个算法所需的存储量，表示为n的函数，称该算法的空间复杂性（space complexity）。,4,2.1,一个实例,5,6,货郎

2、担问题,-货郎担问题（公路调度）,货郎担问题,7,货郎担问题,货郎担问题一般提法为：一个货郎从某城镇出发，经过若干个城镇一次，且仅经过一次，最后仍回到原出发的城镇，问应如何选择行走路线可使总行程最短，这是运筹学的一个著名的问题。实际中有很多问题可以归结为这类问题。,8,实际中很多问题都可以归结为货郎担这类问题。如：1)物资运输路线中，汽车应该走怎样的路线使路程最短；2)工厂里在钢板上要挖一些小圆孔，自动焊接机的割咀应走怎样的路线使路程最短；3)城市里有一些地方铺设管道时，管子应走怎样的路线才能使管子耗费最少，等等。,9,我们学的数据结构里面也有很多内容和货郎担问题的思想相似!,10,最小生成树

3、的普里姆算法,11,最短路径问题,Dijkstra提出了一个按路径长度递增的顺序逐步产生最短路径的方法，称为Dijkstra算法。,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个边的相邻矩阵）。

4、显然，时间复杂性 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个一级城市，采用穷举法求连通各个一级城市的最短路径长度，能计算出来吗？理论上计算需要多少年？请思考：

5、采用哪些近似算法可以得到满意解？,17,18,2.2,函数的渐进控制,19,确定程序的操作计数和执行步数的目的：为了比较两个完成同一功能的程序的时间复杂性，预测程序的运行时间随着实例特征变化的变化量。,设 是算法A的复杂性函数。一般说来，当n单调增加趋于时，也将单调增加趋于。,如果存在函数，使得当 时有，则称 是 当 时的渐近性态，或称 是算法A当 的渐近复杂性。,20,定义：渐进控制 设有 N 到 R+(正实数）的映射f和g，那么g渐进控制f,若存在常数m，使 f(n)mg(n),for all nk,k0 即从某一个值k开始，g乘以一固定常数m 之后，总大于f。,21,例1.设f=3n-1

6、,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,定理:设F是N到R+（正实数）函数的集合，那么，F的二元关系“渐进控制”自反和可迁。F的二元关系“相互渐进控制”是F的一个等价关系（自反、可迁、对称）。注：.自反：-若对每个xA，xRx，那么R自反。.可迁：-xRyyRz xRz，那么，R可迁。.对称：-若对每个x,yA，xRy yRx，那么R对称。注：A为某种关系的集合。,24,定义：g渐进控制的所有函数集合，用O(g)表示，称Order g 或 O

7、(g)。若fO(g)，那么称f是O(g)。,25,定理：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,定理：f是O(g),iff（如果且只要是）O(f)O(g).,推理：f是O(g)，g是O(f)，iff O(f)=O(g),这个推理和定理一样重要

8、，举一简单例子，cn2是O(n2),n2是O(cn2),O(cn2)=O(n2)f=an2+bn+c 是O(n2),n2是O(f),O(f)=O(n2),28,定义：渐进复杂性 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)线

9、性对数乘积复杂性 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,衡量两个算法的好坏，应当是在n足够大的情形下，对算法的工作量进行比较。,32,函数增长表：,一般情况下，随着n的增大，增长较慢的算法为最优的算法。,应该选择对数阶或

10、多项式阶的算法，避免使用指数阶的算法。,33,进一步分析可知，要比较两个算法的渐近复杂性的阶不相同时，只要确定出各自的阶，就可以知道哪一个算法的效率高。,换句话说，渐近复杂性分析只要关心 的阶就够了，不必关心包含在 中的常数因子。所以，我们常常可对 的分析进一步简化，即假设算法中用到的所有不同的运算（基本）各执行一次所需要的时间都是一个单位时间。,34,2.3,复杂性函数的阶,-求解函数的上界“O”，下界“”，同阶“”,35,根据以上分析，我们已经给出了简化算法复杂性分析的方法和步骤，即只考虑当问题的规模充分大时，算法复杂性在渐近意义下的阶。,为此引入渐近符号，首先给出常用的渐近函数。在下面的

11、讨论中，用f(n)表示一个程序的时间或空间复杂性，它是实例特征n（一般是输入规模）的函数。由于一个程序的时间或空间需求是一个非负的实数，我们假定函数f(n)对于n的所有取值均为非负实数，而且还可假定n0。,36,1.渐近符号O 的定义：,f(n)=O(g(n)当且仅当存在正的常数c和n0，使得对于所有的nn0，有f(n)cg(n)。此时，称g(n)是f(n)的一个上界。,函数f至多是函数g的c倍，除非nn0.,f(n)的阶小于或等于g(n)的阶,37,即是说，当n充分大时，g是 f 的一个上界函数，在相差一个非零常数倍的情况下。例如，要使有 f(n)cg(n)2=O(n):可取 c1，n021

12、00n+6=O(n):可取 c=101，n0662n+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，使得当n

13、n0时，f(n)cg(n)所以，人们常常把f(n)=O(g(n)读作：“f(n)的渐进复杂性是O(g)”，或者“f(n)是g(n)的一个大O成员”。,40,大O 比率定义：,对于函数f(n)和g(n)，如果极限 存在，则 当且仅当存在正的常数c，使得.,41,例如，因为，所以；因为，所以；因为，所以；因为，所以，,-但是，最后的一个例子并不是一个好的上界估计，问题出在极限值不是正的常数。,42,定理：对于任意一个正实数x和，有下面的不等式：存在某个n0使得对于任何nn0，有存在某个n0使得对于任何nn0，有,下述不等式对于复杂性阶的估算非常有帮助：,43,存在某个n0使得对于任何nn0，有.存

14、在某个n0使得对于任何nn0，有.对任意实数y，存在某个n0使得对于任何 nn0，有.,44,例，根据渐进控制的定义，我们很容易得出：,45,2.符号的定义：,f(n)=(g(n)当且仅当存在正的常数c和n0，使得对于所有的nn0，有f(n)c(g(n)。此时，称g(n)是f(n)的一个下界。,函数f至少是函数g的c倍，除非nn0.,f(n)的阶大于或等于g(n)的阶,46,即是说，当n充分大时，g是f的一个下界函数，在相差一个非零常数倍的情况下。类似于大O符号，我们可以参考定理1.2.4.所列的不等式，来估计复杂性函数的下界，而且有下述判定规则：,大比率定理：对于函数f(n)和g(n)，如果

15、极限 存在，则 当且仅当存在正的常数c，使得.这里，当n充分大时，g(n)cf(n)意味着，由此不难看出上述判别规则的正确性。,47,3.符号的定义：,f(n)=(g(n)当且仅当存在正的常数C1，C2和n0，使得对于所有的nn0，有 此时，称f(n)与g(n)同阶。,48,函数f介于函数g的C1和C2倍之间。即，当n充分大时，g既是f的下界，又是f的上界。,例如，,49,比率定理：对于函数f(n)和g(n)，如果极限 与 都存在，则f(n)=(g(n)当且仅当存在正的常数C1和C2，使得,50,定理：对于多项式函数，如果am0，则，.,比较大O比率定理和比率定理，可知，比率定理实际是那两种情

16、况的综合。对于多项式情形的复杂性函数，其阶函数可取该多项式的最高项，即,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)；,

17、53,算法的阶,上界“O”，下界“”，同阶“”,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 折半搜索 template int BinarySearch(T a,const T/未找到x,56,折半搜索,例：有11个数据元素的顺序表（05，13，19，21，37，56，64，75，80

18、，88，92）序号：1 2 3 4 5 6 7 8 9 10 11折半查找法在查找成功时进行比较的关键字个数最多不超过判定树的深度，而具有n个结点的判定树的深度为logn+1，所以折半查找法在查找成功时和给定值进行比较的关键字个数至多为logn+1。,57,while 的每次循环（最后一次除外）都将以减半的比例缩小搜索范围，所以，该循环在最坏的情况下需要执行 次。由于每次循环需耗时，因此在最坏情况下，总的时间复杂性为。,58,2.4,循环方程的求解,59,递归方程:递归方程是使用小的输入值来描述一个函数的方程或不等式。,例如，,Merge-sort 排序算法的复杂性方程:T(n)的解是(nlo

19、gn).,60,求解递归方程的2个主要方法:,1.Substitution（猜解替代）:Guess first，然后用数学归纳法证明。2.Iteration（循环递归）:把方程转化为一个和式，然后用和估计技术求解。,61,Substitution（猜解替代）,一般方法:猜解的形式 用数学归纳法证明猜测的解正确-该方法只能用于解可猜的情况。,62,2.Make a good guess(猜测)：,不幸：无一般的猜测正确解的方法，需要 经验 机会 创造性和灵感幸运：存在一些启发规则帮助人们去猜测。,63,Guess方法：联想类似的已知T(n),例1:,求解,T(1)=1.,解:,展开T(n)若干步

20、,可以猜测 T(n)=O(nlogn).我们需要证明T(n)=O(nlogn).,64,设,1.当nm时都成立.2.则当 n=m+1时 有：,于是有，.,（只要C1）,用数学归纳法证明猜测的解正确,65,*边界条件的问题:设T(1)=1是边界条件，则T(1)C1log1=0不成立。*边界条件问题的解决：我们只要求对于nn0时，T(n)=O(nlogn).我们只需看n=2，n=3，或4等，选一个满足 T(n)Cnlogn 的最小n0即可。,只需C 2，这与上页的C1不矛盾。,66,例2:,求解,证明:可用数学归纳法证明T(n)=O(nlogn).,67,Guess方法：-猜测loose上、下界，

21、然后减少不确定性范围,后面一个包含前面一个（一个比一个高阶）：O(1)O(logn)O(n)O(nlogn)O(n2)O(n3)O(cn)O(n!),(n)的上一个阶是(nlogn),O(n2)的下一个阶是O(nlogn)。,68,Iteration（循环递归-迭代法）,方法:循环地展开递归方程，把递归方程转化为和式，然后可使用求和技术得解。,69,例如:,70,令,71,方法的关键：达到边界条件时，展开需要的循环次数。由循环递归过程而得到和式。,注意：在循环中间可能猜出解，此时应停止循环。floor和ceiling使问题复杂化，我们可以假设 方程定义在一个量的幂，如 n=4k 则 可以省略。,72,73,