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

《《函数的渐进复杂性》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

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

3、也有很多内容和货郎担问题的思想相似!10最小生成树的普里姆算法11最短路径问题Dijkstra提出了一个按路径长度递增的顺序逐步产生最短路径的方法，称为Dijkstra算法。12①三个城市，有2!个“遍历”路径，每个路径需做2次加法，一次比较运算。共有3×2！运算。----有2!个“遍历”路径货郎担问题13②四个城市，有3!个“遍历”路径，每个路径需做3次加法,一次比较运算。共有4×3！运算。----有3!个“遍历”路径14③n个城市，有（n-1）!个“遍历”路径，每个路径需做(n-1)次加法,一次比较运算。共有n×(n-1)！=n!运算。按上述算法

4、，搜索最短路径需要的时间复杂性为：f(n)=c*n!空间复杂性为n2（n个边的相邻矩阵）。显然，时间复杂性n!是个explosive问题。15例如，若有56个点：●有56个点需做加法：56！＝7.1×1074次●一年秒数：60秒×60分×24小时×365天＝3.15×107秒●每秒10亿次计算机＝109次/秒●56！＝7.1×1074次加法所需时间：2×1063小时8.2×1061天2.25×1059年16由此可见，货郎担问题的时间复杂性是：f(n)=cn!由以上的条件可知：n的函数是N→R+（正实数）的一个映射。即，当n是N中的元时（n∈N），f(

5、n)=cn!∈R+课后思考题？中国有34个一级城市，采用穷举法求连通各个一级城市的最短路径长度，能计算出来吗？理论上计算需要多少年？请思考：采用哪些近似算法可以得到满意解？1718§2.2函数的渐进控制19确定程序的操作计数和执行步数的目的：为了比较两个完成同一功能的程序的时间复杂性，预测程序的运行时间随着实例特征变化的变化量。设是算法A的复杂性函数。一般说来，当n单调增加趋于∞时，也将单调增加趋于∞。如果存在函数，使得当时有，则称是当时的渐近性态，或称是算法A当的渐近复杂性。20定义1.2.1：渐进控制设有N到R+(正实数）的映射f和g，那么g渐进

6、控制f,若存在常数m，使f(n)≤mg(n),foralln≥k,k≥0即从某一个值k开始，g乘以一固定常数m之后，总大于f。21例1.设f=3n-1,g=n2,n∈N∵当m=1,k=3时，f≤mg(在n=3之后，总是g≥f)∴g渐进控制f。22例2:设f=cn,g=nf≤cg,而g≤()*f,foralln∈N∴f与g是相互渐进的控制。23定理1.2.1:设F是N到R+（正实数）函数的集合，那么，⑴F的二元关系“渐进控制”自反和可迁。⑵F的二元关系“相互渐进控制”是F的一个等价关系（自反、可迁、对称）。注：①.自反：--若对每个x∈A，xRx，那么

7、R自反。②.可迁：--xRy∧yRzxRz，那么，R可迁。③.对称：--若对每个x,y∈A，xRyyRx，那么R对称。注：A为某种关系的集合。24定义1.2.2：g渐进控制的所有函数集合，用O(g)表示，称Orderg或O(g)。若f∈O(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)证⑶：设f≤m1gforn≥k1h≤m2gforn≥k2那么，f+h≤(m1+m2)gforn≥max(k1,k2)推理：多项式a0+a1n+a2n2+…+arnr是O(nr

8、).26例3，2n2+3n+4∴n2渐进控制4、3n和2n2，按定理1.2.2⑶,2n2+3n+4是O(n2