函数的渐进复杂性

1、1 2 问题的模数（问题的模数（sizesize）用一个整数）用一个整数n n表示，它是表示，它是输入数据的一个量度。输入数据的一个量度。 例如，集合的运算，可以是集合的基数；例如，集合的运算，可以是集合的基数； 图的运算，可以是图的运算，可以是V V或或e e。 算 法 的 计 算 复 杂 性算 法 的 计 算 复 杂 性 （ c o m p l e x i t y o f c o m p l e x i t y o f computationcomputation）- - 是问题的模数的一个函数。是问题的模数的一个函数。3一个算法所需的机时，表示为一个算法所需的机时，表示为n n的函数，称

2、该算的函数，称该算法的法的时间复杂性时间复杂性（time complexitytime complexity）。）。算法是程序的灵魂，程序的性能一般指程序算法是程序的灵魂，程序的性能一般指程序的空间复杂性和时间复杂性。的空间复杂性和时间复杂性。一个算法所需的存储量，表示为一个算法所需的存储量，表示为n n的函数，称该的函数，称该算法的算法的空间复杂性空间复杂性（space complexityspace complexity）。）。4 56货郎担问题货郎担问题- - 货郎担问题货郎担问题 （公路调度）公路调度）货郎担问题货郎担问题7货郎担问题货郎担问题 货郎担问题一般提法为：一个货郎从货郎担问

3、题一般提法为：一个货郎从某城镇出发，经过若干个城镇一次，且仅某城镇出发，经过若干个城镇一次，且仅经过一次，最后仍回到原出发的城镇，问经过一次，最后仍回到原出发的城镇，问应如何选择行走路线可使总行程最短，这应如何选择行走路线可使总行程最短，这是运筹学的一个著名的问题。是运筹学的一个著名的问题。 实际中有很多问题可以归结为这类问题。实际中有很多问题可以归结为这类问题。8实际中很多问题都可以归结为货郎担这实际中很多问题都可以归结为货郎担这类问题。类问题。 如：如：1) 物资运输路线中，汽车应该走怎样的路线物资运输路线中，汽车应该走怎样的路线使路程最短；使路程最短；2) 工厂里在钢板上要挖一些小圆孔，

4、自动焊工厂里在钢板上要挖一些小圆孔，自动焊接机的割咀应走怎样的路线使路程最短；接机的割咀应走怎样的路线使路程最短；3) 城市里有一些地方铺设管道时，管子应走城市里有一些地方铺设管道时，管子应走怎样的路线才能使管子耗费最少，等等。怎样的路线才能使管子耗费最少，等等。9我们学的数据结构里面也有很多我们学的数据结构里面也有很多内容和货郎担问题的思想相似内容和货郎担问题的思想相似!10最小生成树的普里姆算法最小生成树的普里姆算法11最短路径问题最短路径问题12 三个城市三个城市，有，有2!2!个个“遍历遍历”路径，每个路径需路径，每个路径需做做2 2次加法，一次比较运算。共有次加法，一次比较运算。共有

5、3 32 2！运算。！运算。- - 有有2!2!个个“遍历遍历”路径路径 货郎担问题货郎担问题13 四个城市四个城市，有，有3!3!个个“遍历遍历”路径，每个路径路径，每个路径需做需做3 3次加法次加法, ,一次比较运算。共有一次比较运算。共有4 43 3！运算。！运算。 - - 有有3!3!个个“遍历遍历”路径路径 14 n n个城市个城市，有（，有（n-1n-1）! !个个“遍历遍历”路径，每个路径路径，每个路径 需做需做(n-1)(n-1)次加法次加法, ,一次比较运算。一次比较运算。 共有共有n n(n-1)(n-1)！=n!=n!运算。运算。按上述算法，搜索最短路径需要的按上述算法，

6、搜索最短路径需要的 时间复杂性为：时间复杂性为：f(n)=cf(n)=c* *n!n! 空间复杂性为空间复杂性为n n2 2（n n个边的相邻矩阵）。个边的相邻矩阵）。显然，时间复杂性显然，时间复杂性 n! n! 是个是个explosiveexplosive问题。问题。15 例如例如，若有，若有5656个点：个点： 有有5656个点需做加法：个点需做加法： 5656！7.17.110107474次次 一年秒数：一年秒数： 6060秒秒6060分分2424小时小时365365天天3.153.1510107 7秒秒 每秒每秒1010亿次计算机亿次计算机10109 9次次/ /秒秒 5656！7.1

7、7.110107474次加法所需时间：次加法所需时间： 21063 小时 8.21061 天 2.251059 年16由此可见，货郎担问题的时间复杂性是：由此可见，货郎担问题的时间复杂性是： f(n)=cn!f(n)=cn!由以上的条件可知：由以上的条件可知： n n的函数是的函数是N N R R+ +（正实数）的一个映射。（正实数）的一个映射。即，即， 当当n n是是N N中的元时（中的元时（nnN N），），f(n)=cn!f(n)=cn!R R+ +课后思考题？课后思考题？ 中国有中国有34个一级城市，采用穷举法求个一级城市，采用穷举法求连通各个一级城市的最短路径长度，连通各个一级城市的

8、最短路径长度，能计算出来吗？理论上计算需要多少能计算出来吗？理论上计算需要多少年？年？ 请思考：采用哪些近似算法可以得到请思考：采用哪些近似算法可以得到满意解？满意解？1718 19 确定程序的操作计数和执行步数的目的：确定程序的操作计数和执行步数的目的：为了比较两个完成同一功能的程序的时间复杂性，预测程序的运行时间随着实例特征变化的变化量。 设 是算法A的复杂性函数。一般说来，当n单调增加趋于时， 也将单调增加趋于。)(nT)(nT 如果存在函数如果存在函数 ，使得当，使得当 时有时有 ，则称，则称 是是 当当 时的时的渐近性态渐近性态，或称，或称 是算法是算法A当当 的的渐渐近复杂性。近复

9、杂性。 )(nTn0)()()(nTnTnT)(nT)(nTn)(nTn20定义定义1.2.11.2.1：渐进控制渐进控制 设有设有 N N 到到 R R+ +( (正实数）正实数）的映射的映射f f和和g g， 那么那么g g渐进控制渐进控制f,f, 若存在常数若存在常数m m，使，使 f(n)mg(n),f(n)mg(n), for all nk, k0 for all nk, k0 即从某一个值即从某一个值k k开始，开始，g g乘以一固定常数乘以一固定常数m m 之后，总大于之后，总大于f f。 21例例1.1. 设设f=3n-1, g=nf=3n-1, g=n2 2, n, nN N

10、 当当m=1,k=3m=1,k=3时，时， fmg fmg ( (在在n=3n=3之后，总是之后，总是gf)gf) g g渐进控制渐进控制f f。22例例2 2: : 设设f=cn, g=nf=cn, g=n fcg, fcg, 而而g( )g( )* *f, for all nf, for all nN N f f与与g g是相互渐进的控制。是相互渐进的控制。c123定理定理1.2.11.2.1: : 设设F F是是N N到到R R+ +（正实数）（正实数）函数的集合，那么，函数的集合，那么， F F的的二元关系二元关系“渐进控制渐进控制”自反和可迁。自反和可迁。 F F的的二元关系二元关系

11、“相互渐进控制相互渐进控制”是是F F的一个等价关的一个等价关系（自反、可迁、对称）。系（自反、可迁、对称）。注：注：. .自反：自反：- - 若对每个若对每个xAxA，xRxxRx，那么，那么R R自反。自反。 . .可迁：可迁：- xRyyRz xRz- xRyyRz xRz，那么，那么，R R可迁。可迁。 . .对称：对称：- - 若对每个若对每个x,yAx,yA，xRy yRxxRy yRx，那么，那么R R对称。对称。 注：注：A A为某种关系的集合。为某种关系的集合。24定义定义1.2.21.2.2： g g渐进控制的所有函数集合，用渐进控制的所有函数集合，用O(g)O(g)表示，

12、称表示，称OrderOrder g g 或或 O(g)O(g)。 若若fO(g)fO(g)， 那么称那么称f f是是O(g)O(g)。 25定理定理1.2.21.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 3， 2n2+3n+4 n2渐进控制4、3n和2n2， 按定理1.2.2 , 2n2+3n+4 是 O(n2).

13、 27 f f是是O(g),iffO(g),iff（如果且只要是）（如果且只要是）O(f)O(g).O(f)O(g).推理： f f是是O(g)O(g)，g g是是O(f)O(f)，iff O(f)=O(g)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.31.2.3： 渐进复杂性渐进复杂性 asymptotic complexityasymptotic complexity 设算法的复杂性函数是f，那么O(f

14、)叫做该算法的渐进复杂性渐进复杂性。例例4,4, f=an f=an2 2+bn+c, +bn+c, 那么该算法渐进复杂性是那么该算法渐进复杂性是O(f),O(f),即即O(nO(n2 2) )。 g=bn+cg=bn+c的渐进复杂性是的渐进复杂性是O(g),O(g),即即O(n)O(n)。 29渐进复杂性的几个重要的类：渐进复杂性的几个重要的类： O(1) f=c O(1) f=c 是是 O(c)=O(1) O(c)=O(1) 常数复杂性常数复杂性 O(logn) f=logn,logO(logn) f=logn,log1010n=lognn=lognlg10 lg10 对数复杂性对数复杂性

15、 O(n) O(n) 线性复杂性线性复杂性 O(nlogn) O(nlogn) 线性对数乘积复杂性线性对数乘积复杂性 O(n O(n2 2) ) 平方复杂性平方复杂性 O(nO(n3 3) ) 立方复杂性立方复杂性 O(cO(cn n) ) 指数复杂性指数复杂性 O(n!) 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的函数）， 不等式在n

16、k后成立。 n nr rccn n 即， nr是O(cn), 而cn不是O(nr) O(nr)O(cn)nncrloglognnlog31v衡量衡量两个算两个算法的好法的好坏，应坏，应当是在当是在n足够足够大大的情的情形下，形下，对算法对算法的工作的工作量进行量进行比较。比较。32函数增长表函数增长表： n n1 10 01 10 02 21 10 03 31 10 04 41 10 05 5l lo og gn nn nn nl lo og gn n3 3. .3 31 10 03 3. .3 36 6. .6 61 10 01 13 3. .3 31 16 6. .6 61 10 01 1

17、0 02 21 10 03 31 10 04 41 10 05 56 6. .6 61 10 02 21 10 01 10 03 31 13 3. .3 31 10 04 41 16 6. .6 61 10 05 5n n2 21 10 04 41 10 06 61 10 08 81 10 01 10 01 10 02 21 10 06 61 10 09 9- -1 10 01 15 51 10 03 3n n3 32 2n n1 10 02 24 41 1. .3 31 10 03 30 01 1. .1 11 10 03 30 01 1- -n n! !3 3. .6 61 10 06 6

18、9 9. .2 21 10 01 15 57 7- - - -v一般情况下，随着一般情况下，随着n的增大，增长较慢的算法为的增大，增长较慢的算法为最优的算法最优的算法。v应该选择对数阶或多项式阶的算法，避免使用指数阶的算法。应该选择对数阶或多项式阶的算法，避免使用指数阶的算法。33 进一步分析可知，要比较两个算法的渐近复杂性进一步分析可知，要比较两个算法的渐近复杂性的阶不相同时，只要确定出各自的的阶不相同时，只要确定出各自的阶阶，就可以知，就可以知道哪一个算法的效率高。道哪一个算法的效率高。 换句话说，换句话说，渐近复杂性分析只要关心渐近复杂性分析只要关心 的阶的阶就就够了，不必关心包含在够了

19、，不必关心包含在 中的常数因子。中的常数因子。 所以，我们常常可对所以，我们常常可对 的分析进一步简化，即的分析进一步简化，即假设算法中用到的所有不同的运算（基本）各执假设算法中用到的所有不同的运算（基本）各执行一次所需要的时间都是一个单位时间。行一次所需要的时间都是一个单位时间。 )(nT)(nT)(nT34 - 求解函数的上界求解函数的上界“ ”，下界下界“ ”，同阶同阶“ ”35 根据以上分析，我们已经给出了简化算法复杂性根据以上分析，我们已经给出了简化算法复杂性分析的方法和步骤，即只考虑当分析的方法和步骤，即只考虑当问题的规模问题的规模充分充分大大时，时，算法复杂性在渐近意义下的阶算法

20、复杂性在渐近意义下的阶。 为此引入渐近符号，首先给出常用的渐近函数。为此引入渐近符号，首先给出常用的渐近函数。 在下面的讨论中，用在下面的讨论中，用f(n)表示一个程序的时间表示一个程序的时间或空间复杂性，它是实例特征或空间复杂性，它是实例特征n（一般是输入规模）（一般是输入规模）的函数。由于一个程序的时间或空间需求是一个的函数。由于一个程序的时间或空间需求是一个非负的实数，我们假定非负的实数，我们假定函数函数f(n)对于对于n的所有取值的所有取值均为非负实数均为非负实数，而且还可假定，而且还可假定n0。 36 f(n)=O(g(n) 当且仅当当且仅当存在正的常数存在正的常数c和和n0，使得对

21、于所有的使得对于所有的nn0，有，有f(n)cg(n)。 此时，称此时，称g(n)是是f(n)的一个的一个上界上界。 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=438 用来作比较的函数用来作比较的函数g(n)g(n)应该尽量接近所考虑应该尽量接近所考虑 的函数的

22、函数f(n)f(n)。 例如，例如，3n+2=O(n2) 松散的界限； 3n+2=O(n) 较好的界限。 不要产生错误界限。不要产生错误界限。 例如，例如，n2+100n+6，当n3时，n2+100n+6c-100就有n2+100n+6 cn. 同理，3n2+42n=O(n2)是错误的界限。 39 f(n)=O(g(n)f(n)=O(g(n)不能写成不能写成g(n)=O(f(n)g(n)=O(f(n)，因为，因为 两者并不等价。两者并不等价。 实际上，这里的等号并不是通常相等的含义。 按照定义，用集合符号集合符号更准确些： O(g(n)=f(n)|O(g(n)=f(n)|f(n)f(n)满足：

23、存在正的常数满足：存在正的常数c c和和n n0 0， 使得当使得当nnnn0 0时，时，f(n)cg(n)f(n)cg(n) 所以，人们常常把f(n)=O(g(n)读作： “”， 或者 “”。 40 对于函数对于函数f(n)和和g(n)，如果极限，如果极限 存在，存在， 则则 当且仅当当且仅当存在存在正的常数正的常数c，使得，使得 . )()(limngnfn)()(ngOnfcngnfn)()(lim41因为因为 ， 所以所以 ；因为因为 ，所以，所以 ；因为因为 ，所以，所以 ；因为因为 ，所以，所以 ， 622*6lim2nnnn)2(2*62nnOn 02*3lim216nnnn)2

24、(*3216nOnn102410lim22nnnn)(241022nOnn323limnnn)(23nOn- - 但是，最后的一个例子并不是一个好的上界估但是，最后的一个例子并不是一个好的上界估计，问题出在极限值不是正的常数。计，问题出在极限值不是正的常数。42对于任意一个对于任意一个正正实数实数x x和和，有下面的不等式：，有下面的不等式：存在某个存在某个n0使得对于任何使得对于任何nn0 ，有，有存在某个存在某个n0使得对于任何使得对于任何nn0 ，有，有下述不等式对于复杂性下述不等式对于复杂性阶的估算阶的估算非常有帮助：非常有帮助： xxnn)(log)(lognnx)(log43存在某

25、个存在某个n0使得对于任何使得对于任何nn0 ， 有有 .存在某个存在某个n0使得对于任何使得对于任何nn0 ， 有有 .对任意对任意实数实数y，存在某个，存在某个n0使得对于任何使得对于任何 nn0 ，有，有 .xxnnnxn2xyxnnn)(log44 根据渐进控制的定义，我们很容易得出：根据渐进控制的定义，我们很容易得出： )(log323nOnnn)(log4205 . 24nOnnn)log/2(log/2log2353534nnOnnnnnnn 45 f(n)=(g(n)当且仅当存在正的常数当且仅当存在正的常数c和和n0，使得对于所有的使得对于所有的nn0，有，有f(n)c(g(n

26、)。 此此时，称时，称g(n)是是f(n)的一个的一个下界下界。 f(n)的阶的阶大于或等于大于或等于g(n)的阶的阶46当当n充分大时，充分大时，g是是f的一个下界函数，在的一个下界函数，在相差一个非零常数倍的情况下。类似于大相差一个非零常数倍的情况下。类似于大O符号，我符号，我们可以参考定理们可以参考定理1.2.4.所列的不等式，来估计复杂性所列的不等式，来估计复杂性函数的下界，而且有下述判定规则：函数的下界，而且有下述判定规则： 对于函数对于函数f(n)和和g(n)，如果极限，如果极限 存在，存在，则则 当且仅当存在当且仅当存在正的常数正的常数c，使得，使得 . 这里，当这里，当n充分大

27、时，充分大时，g(n)cf(n)意味着意味着 ，由，由此不难看出上述判别规则的正确性。此不难看出上述判别规则的正确性。)(/ )(limnfngn)()(ngnf cnfngn)()(lim)(1)(ngcnf47 f(n)=(g(n)当且仅当存在正的常数当且仅当存在正的常数C1，C2和和n0，使得对于所有的，使得对于所有的nn0，有，有 此时，称此时，称f(n)与与g(n)同阶同阶。 )()()(21ngcnfngc48 )(23nn)(241022nnn)2(252nnn 49 对于函数对于函数f(n)f(n)和和g(n)g(n)，如果极限，如果极限 与与 都存在，则都存在，则f(n)=(

28、g(n)f(n)=(g(n)当且仅当且仅当当存在正的常数存在正的常数C C1 1和和C C2 2，使得，使得 )(/ )(limngnfn)(/ )(limnfngn 2)()(limcnfngn,)()(lim1cngnfn50对于多项式函数对于多项式函数 ，如果如果am0 ，则，则 ， ， . . 比较大比较大O O比率定理和比率定理和比率定理，可知，比率定理，可知，比率定比率定理实际是那两种情况的综合。对于多项式情形的复杂理实际是那两种情况的综合。对于多项式情形的复杂性函数，其阶函数可取该多项式的最高项，性函数，其阶函数可取该多项式的最高项，0111anananammmm)()(mnOn

29、f)()(mnnf)()(mnnf51 一般情况下，我们不能对每个复杂性函数去一般情况下，我们不能对每个复杂性函数去估计它们的上界、下界和估计它们的上界、下界和“双界双界”。前面介绍。前面介绍的定理给了一些直接确定这些界的阶函数（或的定理给了一些直接确定这些界的阶函数（或叫渐近函数）的参考信息。由这些信息可以给叫渐近函数）的参考信息。由这些信息可以给出多个函数经过加、乘运算组合起来的复杂函出多个函数经过加、乘运算组合起来的复杂函数的阶的估计。数的阶的估计。 52算法的阶算法的阶小结小结 一般采用一般采用求极限的方法求极限的方法，来比较两个算法时间复杂，来比较两个算法时间复杂性函数的阶：性函数的

30、阶： 当当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)上界上界“ ”，下界下界“ ”，同阶同阶“ ”54例例 题题 例如：例如：2n-5 = O(n2)，因为当，因为当n时，

31、时，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最后最后给出给出折半折半搜索搜索程序程序及算及算法复法复杂性杂性估计：估计： template int BinarySearch (T a , const T &x, int n) /在在a0=a1=an-1中搜索中搜索x /如果找到，则返回所在位置，

32、否则返回如果找到，则返回所在位置，否则返回 1 int left=0; int right =n-1; while ( leftamiddle) left = middle+1; else right = middle 1; return 1; /未找到未找到x 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 折半查找法在查找成功时进行比较的关键字个数最多不超折半查找法在查找成功时进行比较的关键字个数最多不超过过判定树判定树的深度的深度，而具有而具有

33、n个结点的判定树的深度为个结点的判定树的深度为 logn +1，所以折半查找法在查找成功时和给定值进行比，所以折半查找法在查找成功时和给定值进行比较的关键字个数至多为较的关键字个数至多为 logn +1 。631245789101157 while while 的每次循环（最后一次除外）都将以减半的比例缩小搜索范围，所以，该循环在最坏的情况下需要执行 次。 由于每次循环需耗时 ，因此在最坏情况下，总的时间复杂性为时间复杂性为 。)(lognO) 1 (O)(lognO58 59 递归方程是使用小的输入值来描述一个函数的方程或不等式。Merge-sort 排序算法的复杂性方程排序算法的复杂性方程

34、: : T(n) 的解是的解是(nlogn). 1 nif (n) )2n2T(T(n)1 nif ) 1 ()()(nTnT60 1. Substitution（猜解替代）（猜解替代）: Guess first，然后用数学归纳法证明。，然后用数学归纳法证明。2. Iteration（循环递归）（循环递归）: 把方程转化为一个和式，然后用和估计技术求解。把方程转化为一个和式，然后用和估计技术求解。61（猜解替代）一般方法一般方法: : 猜解的形式猜解的形式 用数学归纳法证明猜测的解正确用数学归纳法证明猜测的解正确 - 该方法只能用于解可猜的情况该方法只能用于解可猜的情况。62 无一般的猜测正确

35、解的方法，需要 经验 机会 创造性和灵感 存在一些启发规则帮助人们去猜测。63 求解 , T(1)=1. T nTnn( ) 22展开展开T(T(n n) )若干步若干步, ,可以猜测可以猜测 T( T(n n)=)=O O( (n nloglogn n).).我们需要证明我们需要证明T(T(n n)=)=O O( (n nloglogn n). ). 641.当nm时都成立. 2.则当 n=m+1时 有： 于是有，于是有， . 1212) 1(mmTmT121log212mmmCC mmm()(lg()1111)1)(1() 1lg() 1(CmmmC) 1lg() 1(mmC （只要（只要C1） )log()(nnOnT用数用数学归学归纳法纳法证明证明猜测猜测的解的解正确正确652log24222222)2(CTT只需只需C C 2 2，这与上页的，这与上页的C1C1不矛盾。不矛盾。66求解 nnTnT1722)(只相差一个只相差一个17. 17. 猜测猜测: : nnTnT1722)(T nTnn( ) 22与与当当n n充分大时充分大时 的差别并不大。的差别并不大。 TnTn