時間復雜度--經典解說

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

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

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

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

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

6、):求具有N個元素的全排列的算法優(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 使用所討論的遞推關系，將x(n-1)表示為x(n-2)得函數(shù)，然后把這個結果代入原始方程，來把x(n)表示為x(n-2)的函數(shù)。重復這一過程。X(n)=x(0)+1+2+3+4+5+n=0+1+2+3=4 = n(n+1)/2（3）換名bknfnf)/()(上面形式的在遞推關系式，一個規(guī)模為

7、n的問題，每一次遞歸調用后，都簡化為n/k規(guī)模的問題，為了方便求解，我們通常設定：n=km，則，上面的求解過程可簡化為：f(n)=f(km-1)+b=f(km-2)+2b=f(k0)+mb=f(1)+blogn幾種常見復雜度舉例：1. O(logn)我們學過的算法，二分搜索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);遞歸調用遞歸關系式：11nn1)2/(1)(nCnC因為規(guī)模每一次遞歸調用后，縮減為原來的1/2，所以采用換名方法求解，設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觀察遞歸調用的過程以及遞推關系式：（1）在遞歸關系式中：遞歸調用共有k次，我們設n=2k，k=logn（2）遞歸調用的二叉樹型結構中，調用次數(shù)為二叉樹的深度。2.O(n):表示該算法是線性算法目前所學

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);-遞歸調用遞歸調用 return r1; else /sk int r1=Select(data,s+1,r,k-s);-遞歸調用遞歸調用 return r1; 如果遞歸調用，每次規(guī)模是原來的1/2：1)1()2/(11)(nnnTnnT因為每一次規(guī)模都減到原來的1/2，所以用換名的方法設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算法時間復雜度：O(n)分析：1)1()2/(11)(nnnTnnT算法的復雜度有兩部分決定：遞歸和合并，遞歸的復雜度是：logn，合并的復雜度是n。3.O(nlogn)所學過的算法：快速排序、堆排序等，分治法中的平面中最接近點對問題。遞推關系式：)()2/(2)(1)2(nOnTnTTT(n)=2T(n/2)+n設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不失一般性，設規(guī)模為n的問題，每一次有分解為m個子問題，設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算法時間復雜度：O(nlogn)分析：算法的復雜度有兩部分決定：遞歸和合并，遞歸的復雜度是：n，合并的復雜度是nlogn。)()/()(1)1 (nOmnmTnTT4.O(n2)通常的兩層嵌套循環(huán)，內層的運算執(zhí)行次數(shù)，學過的例子有：

12、比賽日程1) 2/(*3) 2/(11)(2nnnTnnTT(n)=T(n/m)+(n/m)2設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)所學過的：大整數(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);遞歸調用遞歸調用x1y1=Recursive_Miltiply(x1,y1);遞歸調用遞歸調用x0y0=Recursive_Miltiply(x0,y0);遞歸調用遞歸調用returnx1y1*2n+(p-x1y1-x0y0)*2n/2+x0y0;基本操作基本操作11)()2/(3) 1 ()(nnnOnTOnTkkkkikikkkTTTTT3)2(3)2(3)2(3)2(3)2(221設，n=2k, 用反向替換法對它求解：585.13loglog223)(nnnTn分析：在這個遞推關系式中，算法每次遞歸調用3個規(guī)模為1/2的子問題，那么總的規(guī)模

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

15、度為第一臺的64倍，那么在這臺新機器上用同一算法在t秒內能解輸入規(guī)模為多大的問題？設新機器用統(tǒng)一算法能解輸入規(guī)模為n1的問題，則：t=3*2n1/64=3*2n1-6所以，n1=n+6(2)若上述的算法改為T(n)=n2，其他條件不變，則在新機器上用t秒時間能解輸入規(guī)模為多大的問題？n12=64n2=(8n)2能解規(guī)模為8n的問題(3)若上述的算法改為T(n)=8，其他條件不變，則在新機器上用t秒時間能解輸入規(guī)模為多大的問題？由于T(n)是常數(shù)，所以可以解任意規(guī)模的問題。4.對于下列各組函數(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.螺釘和螺母問題假設我們有n個直徑各不相同的螺釘，以及n個相應的螺母。我們一次只能比較一對螺釘和螺母，來判斷螺母是大于螺釘、小于螺釘還是正好合適螺釘。然而，我們不能拿兩個螺母作比較，也不能拿兩個螺釘作比較。我們的問題是要找到每一對匹配的螺