時(shí)間復(fù)雜度--經(jīng)典解說(shuō)

1、時(shí)間復(fù)雜度分析時(shí)間復(fù)雜度分析算法時(shí)間復(fù)雜度的數(shù)學(xué)意義算法時(shí)間復(fù)雜度的數(shù)學(xué)意義從數(shù)學(xué)上定義，給定算法A，如果存在函數(shù)f(n)，當(dāng)n=k時(shí)，f(k)表示算法A在輸入規(guī)模為k的情況下的運(yùn)行時(shí)間，則稱f(n)為算法A的時(shí)間復(fù)雜度。其中：輸入規(guī)模是指算法A所接受輸入的自然獨(dú)立體的大小，我們總是假設(shè)算法的輸入規(guī)模是用大于零的整數(shù)表示的，即n=1,2,3,k,對(duì)于同一個(gè)算法，每次執(zhí)行的時(shí)間不僅取決于輸入規(guī)模，還取決于輸入的特性和具體的硬件環(huán)境在某次執(zhí)行時(shí)的狀態(tài)。所以想要得到一個(gè)統(tǒng)一精確的F(n)是不可能的。為此，通常做法：1.忽略硬件及環(huán)境因素，假設(shè)每次執(zhí)行時(shí)硬件條件和環(huán)境條件是完全一致的。2.對(duì)于輸入特性

2、的差異，我們將從數(shù)學(xué)上進(jìn)行精確分析并帶入函數(shù)解析式。例子：例子： x=1;for(i=1;i=n;i+) for(j=1;j=i;j+) for(k=1;k=j;k+) x+;x+運(yùn)行次數(shù)：運(yùn)行次數(shù)：2/2/)1(6/)12)(1(2/)1(1111111 nnnnniijniijjkniniij算法的漸近時(shí)間復(fù)雜度算法的漸近時(shí)間復(fù)雜度很多時(shí)候，我們不需要進(jìn)行如此精確的分析，究其原因：1.在較復(fù)雜的算法中，進(jìn)行精確分析是非常復(fù)雜的。2.實(shí)際上，大多數(shù)時(shí)候我們并不關(guān)心F(n)的精確度量，而只是關(guān)心其量級(jí)。算法復(fù)雜度的考察方法算法復(fù)雜度的考察方法（1）考察一個(gè)算法的復(fù)雜度，一般考察的是當(dāng)問(wèn)題復(fù)雜度

3、n的增加時(shí)，運(yùn)算所需時(shí)間、空間代價(jià)f(n)的上下界。（2）進(jìn)一步而言，又分為最好情況、平均情況、最壞情況三種情況。通常最壞情況往往是我們最關(guān)注的。定義1如果存在兩個(gè)正常數(shù)c和n0，對(duì)于所有的nn0，有 |T(n)| c|f(n)| 則記作T(n) = (f(n)含義： 如果算法用n值不變的同一類數(shù)據(jù)在某臺(tái)機(jī)器上運(yùn)行時(shí)，所用的時(shí)間總是小于|f(n)|的一個(gè)常數(shù)倍。所以f(n)是計(jì)算時(shí)間T(n)的一個(gè)上界函數(shù)。 試圖求出最小的f(n)，使得T(n) = (f(n)。 在分析算法的時(shí)間復(fù)雜度時(shí)，我們更關(guān)心最壞情況而不是最好情況，理由如下：（1）最壞情況給出了算法執(zhí)行時(shí)間的上界，我們可以確信，無(wú)論給什

4、么輸入，算法的執(zhí)行時(shí)間都不會(huì)超過(guò)這個(gè)上界，這樣為比較和分析提供了便利。（2）雖然最壞情況是一種悲觀估計(jì)，但是對(duì)于很多問(wèn)題，平均情況和最壞情況的時(shí)間復(fù)雜度差不多，比如插入排序這個(gè)例子，平均情況和最壞情況的時(shí)間復(fù)雜度都是輸入長(zhǎng)度n的二次函數(shù)。定義1.2如果存在兩個(gè)正常數(shù)c和n0，對(duì)于所有的nn0， 有 |T(n)| c|g(n)| 則記作T(n) = (g(n)含義： 如果算法用n值不變的同一類數(shù)據(jù)在某臺(tái)機(jī)器上運(yùn)行時(shí)，所用的時(shí)間總是不小于|g(n)|的一個(gè)常數(shù)倍。所以g(n)是計(jì)算時(shí)間T(n)的一個(gè)下界函數(shù)。 試圖求出“最大”的g(n)，使得T(n) = (g(n)。（2）下界函數(shù)定義1.3如果存

5、在正常數(shù)c1，c2和n0，對(duì)于所有的nn0，有 c1|g(n)| |T(n)| c2|g(n)| 則記作含義： 算法在最好和最壞情況下的計(jì)算時(shí)間就一個(gè)常數(shù)因子范圍內(nèi)而言是相同的。可看作： 既有 T(n) = (g(n)，又有T(n) = (g(n)()(ngnT（3） “平均情況”限界函數(shù)常見(jiàn)算法時(shí)間復(fù)雜度：常見(jiàn)算法時(shí)間復(fù)雜度：O(1):表示算法的運(yùn)行時(shí)間為常量O(n):表示該算法是線性算法O(2n):二分搜索算法O(n2n):快速排序算法O(n2):對(duì)數(shù)組進(jìn)行排序的各種簡(jiǎn)單算法，例如直接插入排序的算法。O(n3):做兩個(gè)n階矩陣的乘法運(yùn)算O(2n):求具有n個(gè)元素集合的所有子集的算法O(n!

6、):求具有N個(gè)元素的全排列的算法優(yōu)-劣O(1)O(2n)O(n)O(n2n):O(n2)1X(1)=1x(1)=1x(2)=2x(1)+1=2*1+1=3x(3)=2x(2)+1=2*3+1=7x(4)=2x(3)+1=2*7+1=15X(n)=2n-1n0（2）反向替換法例如：X(n)=x(n-1)+n 使用所討論的遞推關(guān)系，將x(n-1)表示為x(n-2)得函數(shù)，然后把這個(gè)結(jié)果代入原始方程，來(lái)把x(n)表示為x(n-2)的函數(shù)。重復(fù)這一過(guò)程。X(n)=x(0)+1+2+3+4+5+n=0+1+2+3=4 = n(n+1)/2（3）換名bknfnf)/()(上面形式的在遞推關(guān)系式，一個(gè)規(guī)模為

7、n的問(wèn)題，每一次遞歸調(diào)用后，都簡(jiǎn)化為n/k規(guī)模的問(wèn)題，為了方便求解，我們通常設(shè)定：n=km，則，上面的求解過(guò)程可簡(jiǎn)化為：f(n)=f(km-1)+b=f(km-2)+2b=f(k0)+mb=f(1)+blogn幾種常見(jiàn)復(fù)雜度舉例：1. O(logn)我們學(xué)過(guò)的算法，二分搜索intBinSrch(TypeA,inti,intn,Typex)/Ai.n是非遞減排列且1=i=n;if(n=i)if(x=Ai)returni;elsereturn0;elseintmid=(i+n)/2;if(x=Amid)returnmid;-基本操作基本操作elseif(xAmid)returnBinSrh(A,m

8、id+1,n,x);遞歸調(diào)用遞歸關(guān)系式：11nn1)2/(1)(nCnC因?yàn)橐?guī)模每一次遞歸調(diào)用后，縮減為原來(lái)的1/2，所以采用換名方法求解，設(shè)n=2k：C(n)=C(2k)=C(2k-1)+1=C(2k-2)+2=C(2k-k)+k=C(1)+k=logn+139 17 21 34 57 69 84 92 1039 17 2157 69 84 92 10317 2157 6992 10691021觀察遞歸調(diào)用的過(guò)程以及遞推關(guān)系式：（1）在遞歸關(guān)系式中：遞歸調(diào)用共有k次，我們?cè)O(shè)n=2k，k=logn（2）遞歸調(diào)用的二叉樹(shù)型結(jié)構(gòu)中，調(diào)用次數(shù)為二叉樹(shù)的深度。2.O(n):表示該算法是線性算法目前所學(xué)

9、的算法中有：線性選擇算法int Select(int data,int p,int r,int k) if(pr) return -1; /p不能大于r if(p=r) return datap; /pk) int r1= Select(data,p,s-1,k);-遞歸調(diào)用遞歸調(diào)用 return r1; else /sk int r1=Select(data,s+1,r,k-s);-遞歸調(diào)用遞歸調(diào)用 return r1; 如果遞歸調(diào)用，每次規(guī)模是原來(lái)的1/2：1)1()2/(11)(nnnTnnT因?yàn)槊恳淮我?guī)模都減到原來(lái)的1/2，所以用換名的方法設(shè)n=2k：T(n)=T(n/2)+(n-1)

10、=T(2k-1)+(2k-1)=T(2k-2)+(2k-1-1)+(2k-1)=T(2k-k)+(21-1)+(2k-1-1)+(2k-1)=T(1)+(2k+1-2)-k=2n-logn-1算法時(shí)間復(fù)雜度：O(n)分析：1)1()2/(11)(nnnTnnT算法的復(fù)雜度有兩部分決定：遞歸和合并，遞歸的復(fù)雜度是：logn，合并的復(fù)雜度是n。3.O(nlogn)所學(xué)過(guò)的算法：快速排序、堆排序等，分治法中的平面中最接近點(diǎn)對(duì)問(wèn)題。遞推關(guān)系式：)()2/(2)(1)2(nOnTnTTT(n)=2T(n/2)+n設(shè)n=2k=2T(2k-1)+2k=22T(2k-2)+2k-1+2k=22T(2k-2)+

11、2*2k=2k-1T(2k-(k-1)+(k-1)*2k=n/2+(logn-1)*n不失一般性，設(shè)規(guī)模為n的問(wèn)題，每一次有分解為m個(gè)子問(wèn)題，設(shè)n=mk，則：)()/()(1) 1 (nOmnmTnTTT(n)=mT(n/m)+n=mT(mk-1)+mk=mmT(mk-2)+mk-1+mk=m2T(mk-2)+2*mk=mkT(2k-k)+k*mk=n+logn*n算法時(shí)間復(fù)雜度：O(nlogn)分析：算法的復(fù)雜度有兩部分決定：遞歸和合并，遞歸的復(fù)雜度是：n，合并的復(fù)雜度是nlogn。)()/()(1)1 (nOmnmTnTT4.O(n2)通常的兩層嵌套循環(huán)，內(nèi)層的運(yùn)算執(zhí)行次數(shù)，學(xué)過(guò)的例子有：

12、比賽日程1) 2/(*3) 2/(11)(2nnnTnnTT(n)=T(n/m)+(n/m)2設(shè)n=mk=T(mk-1)+m2(k-1)=T(mk-2)+m2(k-2)+m2(k-1)=T(mk-k)+m0+m2(k-2)+m2(k-1)=1+(m2k-1)/(m2-1)=(n2-1)/(m2-1)+1所以：O(n2)4.O(nk)所學(xué)過(guò)的：大整數(shù)乘法Recursive_Miltiply(x,y)ifn=1if(X=1)and(Y=1)return(1)elsereturn(0)x1=X的左邊n/2位;x0=X的右邊n/2位;y1=Y的左邊n/2位;y0=Y的右邊n/2位;p=Recursiv

13、e_Miltiply(x1+x0,y1+y0);遞歸調(diào)用遞歸調(diào)用x1y1=Recursive_Miltiply(x1,y1);遞歸調(diào)用遞歸調(diào)用x0y0=Recursive_Miltiply(x0,y0);遞歸調(diào)用遞歸調(diào)用returnx1y1*2n+(p-x1y1-x0y0)*2n/2+x0y0;基本操作基本操作11)()2/(3) 1 ()(nnnOnTOnTkkkkikikkkTTTTT3)2(3)2(3)2(3)2(3)2(221設(shè)，n=2k, 用反向替換法對(duì)它求解：585.13loglog223)(nnnTn分析：在這個(gè)遞推關(guān)系式中，算法每次遞歸調(diào)用3個(gè)規(guī)模為1/2的子問(wèn)題，那么總的規(guī)模

14、3/2，大小，所以，粗略估算要在O(nlogn)、O(n2)之間。11)()2/(3) 1 ()(nnnOnTOnT相關(guān)習(xí)題1. 求下列函數(shù)的漸進(jìn)表達(dá)式：3n2+10nn2/10+2n21+1/nlogn310log3n=O(n2)=O(2n)=O(1)=O(logn)=O(n)2.討論O(1)和O(2)區(qū)別：定義1如果存在兩個(gè)正常數(shù)c和n0，對(duì)于所有的nn0，有|f(n)|c|g(n)|則記作f(n)=(g(n)O(1)=O(2)相差的只是常數(shù)因子3.算法效率（1）假設(shè)某算法在輸入規(guī)模為n時(shí)的計(jì)算時(shí)間為T(n)=3*2n。在某臺(tái)計(jì)算機(jī)上實(shí)現(xiàn)并完成該算法的時(shí)間為t。現(xiàn)在有另一臺(tái)計(jì)算機(jī)，其運(yùn)行速

15、度為第一臺(tái)的64倍，那么在這臺(tái)新機(jī)器上用同一算法在t秒內(nèi)能解輸入規(guī)模為多大的問(wèn)題？設(shè)新機(jī)器用統(tǒng)一算法能解輸入規(guī)模為n1的問(wèn)題，則：t=3*2n1/64=3*2n1-6所以，n1=n+6(2)若上述的算法改為T(n)=n2，其他條件不變，則在新機(jī)器上用t秒時(shí)間能解輸入規(guī)模為多大的問(wèn)題？n12=64n2=(8n)2能解規(guī)模為8n的問(wèn)題(3)若上述的算法改為T(n)=8，其他條件不變，則在新機(jī)器上用t秒時(shí)間能解輸入規(guī)模為多大的問(wèn)題？由于T(n)是常數(shù)，所以可以解任意規(guī)模的問(wèn)題。4.對(duì)于下列各組函數(shù)f(n)g(n)，確定f(n)=O(g(n)，或f（n)=(g(n)，或f(n)=(g(n)(1) f(n)=logn2g(n)=logn+5(2) f(n)=logn2g(n)=(3) f(n)=ng(n)=log2n(4) f(n)=nlogng(n)=log(n)(5) f(n)=10g(n)=log10(6) f(n)=log2ng(n)=logn(7) f(n)=2ng(n)=100n2(8) f(n)=2ng(n)=3nn5.螺釘和螺母問(wèn)題假設(shè)我們有n個(gè)直徑各不相同的螺釘，以及n個(gè)相應(yīng)的螺母。我們一次只能比較一對(duì)螺釘和螺母，來(lái)判斷螺母是大于螺釘、小于螺釘還是正好合適螺釘。然而，我們不能拿兩個(gè)螺母作比較，也不能拿兩個(gè)螺釘作比較。我們的問(wèn)題是要找到每一對(duì)匹配的螺