时间复杂度--经典解说

,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,时间复杂度分析,算法时间,复,复杂度的,数,数学意义,从数学上,定,定义，给,定,定算法A,，,，如果存,在,在函数f(n)，,当,当n=k,时,时，f(k)表示,算,算法A在,输,输入规模,为,为k的情,况,况下的运,行,行时间，,则,则称f(n)为算,法,法A的时,间,间复杂度,。,。,其中：输,入,入规模是,指,指算法A,所,所接受输,入,入的自然,独,独立体的,大,大小，我,们,们总是假,设,设算法的,输,输入规模,是,是用大于,零,零的整数,表,表示的，,即,即n=1,2,3,k,对于同一,个,个算法，,每,每次执行,的,的时间不,仅,仅取决于,输,输入规模,，,，还取决,于,于输入的,特,特性和具,体,体的硬件,环,环境在某,次,次执行时,的,的状态。,所,所以想要,得,得到一个,统,统一精确,的,的F(n)是不可,能,能的。为,此,此，通常,做,做法：1.,忽,忽略硬件,及,及环境因,素,素，假设,每,每次执行,时,时硬件条,件,件和环境,条,条件是完,全,全一致的,。,。2.对于,输,输入特性,的,的差异，,我,我们将从,数,数学上进,行,行精确分,析,析并带入,函,函数解析,式,式。,例子：,x=1;for(i=1;i=n;i+)for(j=1;j=i;j+)for(k=1;k=j;k+)x+;,x+运,行,行次数：,算法的渐,近,近时间复,杂,杂度,很多时候,，,，我们不,需,需要进行,如,如此精确,的,的分析，,究,究其原因,：,：1.在较,复,复杂的算,法,法中，进,行,行精确分,析,析是非常,复,复杂的。2.实际上,，,，大多数,时,时候我们,并,并不关心F(n),的,的精确度,量,量，而只,是,是关心其,量,量级。,算法复杂,度,度的考察,方,方法,（1）考,察,察一个算,法,法的复杂,度,度，一般,考,考察的是,当,当问题复,杂,杂度n的,增,增加时，,运,运算所需,时,时间、空,间,间代价f(n)的,上,上下界。,（2）进,一,一步而言,，,，又分为,最,最好情况,、,、平均情,况,况、最坏,情,情况三种,情,情况。通,常,常最坏情,况,况往往是,我,我们最关,注,注的。,（1）,上,上界函,数,数,定义1,如,如,果,果存在,两,两个正,常,常数c,和,和n,0,，对于,所,所有的n,n,0,，有,|T(n)|,c|f(n)|,则记作T(n)=,(f(n),含义：,如果算,法,法用n,值,值不变,的,的同一,类,类数据,在,在某台,机,机器上,运,运行时,，,，所用,的,的时间,总,总是小,于,于|f(n)|的一,个,个常数,倍,倍。所,以,以f(n)是,计,计算时,间,间T(n)的,一,一个上,界,界函数,。,。,试图求,出,出最小,的,的f(n)，,使,使得T(n)=,(f(n),。,。,在分析,算,算法的,时,时间复,杂,杂度时,，,，我们,更,更关心,最,最坏情,况,况而不,是,是最好,情,情况，,理,理由如,下,下：,（1）,最,最坏情,况,况给出,了,了算法,执,执行时,间,间的上,界,界，我,们,们可以,确,确信，,无,无论给,什,什么输,入,入，算,法,法的执,行,行时间,都,都不会,超,超过这,个,个上界,，,，这样,为,为比较,和,和分析,提,提供了,便,便利。,（2）,虽,虽然最,坏,坏情况,是,是一种,悲,悲观估,计,计，但,是,是对于,很,很多问,题,题，平,均,均情况,和,和最坏,情,情况的,时,时间复,杂,杂度差,不,不多，,比,比如插,入,入排序,这,这个例,子,子，平,均,均情况,和,和最坏,情,情况的,时,时间复,杂,杂度都,是,是输入,长,长度n,的,的二次,函,函数。,定义1.2,如,如果,存,存在两,个,个正常,数,数c和n,0,，对于,所,所有的n,n,0,，,有,|T(n)|,c|g(n)|,则记作T(n)=,(g(n),含义：,如果算,法,法用n,值,值不变,的,的同一,类,类数据,在,在某台,机,机器上,运,运行时,，,，所用,的,的时间,总,总是不,小,小于|g(n)|的,一,一个常,数,数倍。,所,所以g(n),是,是计算,时,时间T(n),的,的一个,下,下界函,数,数。,试图求,出,出“最,大,大”的g(n)，使,得,得T(n)=,(g(n),。,。,（2）,下,下界函,数,数,定义1.3,如,如果,存,存在正,常,常数,c,1,，,c,2,和n,0,，对于,所,所有的n,n,0,，有,c,1,|g(n)|,|T(n)|,c,2,|g(n)|,则记作,含义：,算法在,最,最好和,最,最坏情,况,况下的,计,计算时,间,间就一,个,个常数,因,因子范,围,围内而,言,言是相,同,同的。,可,可看作,：,：,既有T(n)=,(g(n),，,，又有T(n)=,(g(n),（3）,“平均,情,情况”,限,限界函,数,数,常见算,法,法时间,复,复杂度,：,：,O(1):,表,表示算,法,法的运,行,行时间,为,为常量O(n):,表,表示,该,该算法,是,是线性,算,算法O(,2,n):,二,二分,搜,搜索算,法,法O(n,2,n):,快,快速,排,排序算,法,法,O(n,2,):,对,对数组,进,进行排,序,序的各,种,种简单,算,算法，,例,例如直,接,接插入,排,排序的,算,算法。O(n,3,):,做,做两个n阶矩,阵,阵的乘,法,法运算O(2,n,):,求,求具有n个元,素,素集合,的,的所有,子,子集的,算,算法O(n!):,求,求具,有,有N个,元,元素的,全,全排列,的,的算法,优-,劣,劣,O(1)O(,2,n)O(n)O(n,2,n):O(n,2,)1,X(1)=1,x(1)=1,x(2)=2x(1)+1=2*1+1=3,x(3)=2x(2)+1=2*3+1=7,x(4)=2x(3)+1=2*7+1=15,X(n)=,2n,-1n0,（2）反向替,换,换法,例如：X(n)=x(n-1)+n,使用所讨论的,递,递推关系，将x(n-1),表,表示为x(n-2)得函数,，,，然后把这个,结,结果代入原始,方,方程，来把x(n)表示为x(n-2),的,的函数。重复,这,这一过程。,X(n)=x(0)+1+2+3+4+5+n=0+1+2+3=4 =n(n+1)/2,（3）换名,上面形式的在,递,递推关系式，,一,一个规模为n,的,的问题，每一,次,次递归调用后,，,，都简化为n/k规模的问,题,题，为了方便,求,求解，我们通,常,常设定：n=k,m,，,则，上面的求,解,解过程可简化,为,为：,f(n)=f(k,m-1,)+b,=f(k,m-2,)+2b,=,=f(k,0,)+mb,=f(1)+blog n,几种常见复杂,度,度举例：,O(logn),我们学过的算,法,法，二分搜索,int BinSrch(Type A,inti,int n,Type x),/Ai.n是非递,减,减排列 且1=i=n;,if(n=i)if(x=Ai)returni;,else return0;,else,int mid=(i+n)/2;,if(x=Amid)return mid;-,基本操作,elseif(xAmid)return BinSrh(A,mid+1,n,x);递归调用,递归关系式：,因为规模每一,次,次递归调用后,，,，缩减为原来,的,的1/2，所,以,以采用换名方,法,法求解，设n=2,k,：,C(n)=C(2,k,)=C(2,k-1,)+1,=C(2,k-2,)+2,=,=C(2,k-k,)+k,=C(1)+k,=logn+1,3,9,17,21,34,57,69,84,92,10,3,9,17,21,57,69,84,92,10,3,17,21,57,69,92,10,69,10,21,观察递归调用,的,的过程以及递,推,推关系式：,（1）在递归,关,关系式中：递,归,归调用共有k,次,次，我们设n=2,k,，k=logn,（2）递归调,用,用的二叉树型,结,结构中，调用,次,次数为二叉树,的,的深度。,2.O(n):表,示,示该算法是线,性,性算法,目,目前所,学,学的算法中有,：,：线性选择算,法,法,intSelect(intdata,intp,intr,intk),if(pr)return-1;/p不能大,于,于r,if(p=r)returndatap;/pk),intr1=Select(data,p,s-1,k);-,递归调用,returnr1;,else/sk,intr1=Select(data,s+1,r,k-s);-,递归调用,returnr1;,如果递归,调,调用，每,次,次规模是,原,原来的1/2：,因为每一,次,次规模都,减,减到原来,的,的1/2,，,，所以用,换,换名的方,法,法设 n=2,k,：,T(n)=T(n/2)+(n-1),=T(2,k-1,)+(2,k,-1),=T(2,k-2,)+(2,k-1,-1)+(2,k,-1),=,=T(2,k-k,)+(2,1,-1)+(2,k-1,-1)+(2,k,-1),=T(1)+(2,k+1,-2)-k,=2n-logn-1,算法时间,复,复杂度：O(n),分析：,算法的复,杂,杂度有两,部,部分决定,：,：递归和,合,合并，递,归,归的复杂,度,度是：logn，,合,合并的复,杂,杂度是n。,3.O(nlogn),所学过的,算,算法：快,速,速排序、,堆,堆排序等,，,，分治法,中,中的平面,中,中最接近,点,点对问题,。,。,递推关系,式,式：,T(n)=2T(n/2)+n,设,设n=2,k,=2T(2,k-1,)+2,k,=22T(2,k-2,)+2,k-1,+2,k,=2,2,T(2,k-2,)+2*2,k,=,=2,k-1,T(2,k-(k-1),)+(k-1)*2,k,=n/2+(logn-1)*n,不失一般,性,性，设规,模,模为n的,问,问题，每,一,一次有分,解,解为m个,子,子问题，,设,设n=m,k,，则：,T(n)=mT(n/m)+n,=mT(m,k-1,)+m,k,=mmT(m,k-2,)+m,k-1,+m,k,=m,2,T(m,k-2,)+2*m,k,=,=m,k,T(2,k-k,)+k*m,k,=n+logn*n,算法时间,复,复杂度：O(nlogn),分析：,算法的复,杂,杂度有两,部,部分决定,：,：递归和,合,合并，递,归,归的复杂,度,度是：n,，,，合并的,复,复杂度是nlogn。,4.O(n,2,),通常的两,层,层嵌套循,环,环，内层,的,的运算执,行,行次数，,学,学过的例,子,子有：比,赛,赛日程,T(n)=T(n/m)+(n/m),2,设n=m,k,=T(m,k-1,)+m,2(k-1),=T(m,k-2,)+m,2(k-2),+m,2(k-1),=,=T(m,k-k,)+m,0,+m,2(k-2),+m,2(k-1),=1+(m,2k,-1)/(m,2,-1),=(n,2,-1)/(m,2,-1)+1,所以：O(n,2,),4.O(n,k,),所学过的,：,：大整数,乘,乘法,Recursive_Miltiply(x,y),if n=1,if(X=1)and(Y=1)return(1),else return(0),x,1,=X的左边n/2位;,x,0,=X的右边n/2位;,y,1,=Y的左边n/2位;,y,0,=Y的右边n/2位;,p=Recursive_Miltiply(x,1,+x,0,y,1,+y,0,);,递归调用,x,1,y,1,=Recursive_Miltiply(x,1,y,1,);,递归调用,x,0,y,0,=Recursive_Miltiply(x,0,y,0,);,递归调用,returnx,1,y,1,*2,n,+(p-x,1,y,1,-x,0,y,0,)*2,n/2,+x,0,y,