资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2016-12-26,#,2016,数据结构,Data structure,讲授：简勇,算法的时间和空间复杂度,常州信息职业技术学院,02,三、链表的插入,03,算法的时间和空间复杂度,0.4,一、,算法的时间复杂度,1,2,设问题的规模为,n,，把一个算法的时间耗费,T(n),称为该算法的,时间复杂度,，它是问题规模为,n,的函数。,（,1,）定义：,（,2,）算法的渐进时间复杂度,设,T(n),为一个算法的时间复杂度，如果存在一个函数,f,(n),，当,n,趋向无穷大时,T(n),与函数,f,(n),比值的极限是一个非零常数,M,，即,，则称,O(,f,(n),为算法的渐进时间复杂度，简称,时间复杂度,，也称,T(n),与,f,(n),的数量级相同，记作,T(n)=O(,f,(n),，通常，,f,(n),应该是算法中频度最高的语句的频度。,因此，计算算法的时间复杂度只需计算算法中执行频度最高的语句的频度。,04,算法的时间和空间复杂度,0.4,一、,算法的时间复杂度,算法的时间复杂度有很多，常用的时间复杂度及顺序如下：,O(1)O(lgn)O(n)O(nlgn)O(n,2,)O(n,3,)=0&(Ai!=K),(3)i-;,(4)return i;,此算法中第,(3),行语句的频度最高，它不仅与问题规模,n,有关，还与输入实例中数组,A,各元素的取值及,K,的取值有关：,若,A,中没有与,K,相等的元素，则语句,i-;,的频度,f,(n)=n,；,若,A,的最后一个元素等于,K,，则语句,i-;,的频度,f,(n),是常数,0,。,3,4,（,3,）常用算法时间复杂度的顺序,（,4,）,算法的时间复杂度不仅仅依赖于问题的规模，还与输入实例的初始状态有关。,05,算法的时间和空间复杂度,0.4,一、,算法的时间复杂度,（,5,）最坏时间复杂度和平均时间复杂度,最坏情况下的时间复杂度称为最坏时间复杂度。最坏情况下的时间复杂度是算法在任何输入实例上运行时间的上界。,平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下，算法的期望运行时间。,如果不作特别说明，我们讨论的时间复杂度均是平均时间复杂度。,【例,1-1,】求在含有,n,（,n3,）个元素的数组,array,中输出第,3,个元素的算法时间复杂度。,(1) i=3;,(2) printf(%dn,arrayi);,【例,1-2,】求下列算法的时间复杂度。,(1) x=1;,(2) for(i=1;i=n;i+),(3) for(j=1;j=i;j+),(4),for,(k=1;k=j;k+),(5)x+;,06,算法的时间和空间复杂度,0.4,二、算法的空间,复杂度,空间复杂度,(Space complexity),：是指算法编写成程序后，在计算机中运行时所需存储空间大小的度量。记作：,S(n)=O(f(n),其中：,n,为问题的规模,(,或大小,),该存储空间一般包括三个方面：,指令常数变量所占用的存储空间,;,输入数据所占用的存储空间,;,辅助,(,存储,),空间。,一般地，算法的空间复杂度指的是辅助空间。,一维数组,an,： 空间复杂度,O(n),二维数组,anm,： 空间复杂度,O(n*m),THANKS,2016.9.18,
展开阅读全文