時間復(fù)雜度--經(jīng)典解說.ppt

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

2、確分析并帶入函數(shù)解析式。,例子： x=1;for(i=1;i=n;i+) for(j=1;j=i;j+) for(k=1;k=j;k+) x+; x+運行次數(shù)：,算法的漸近時間復(fù)雜度 很多時候，我們不需要進(jìn)行如此精確的分析，究其原因： 1.在較復(fù)雜的算法中，進(jìn)行精確分析是非常復(fù)雜的。 2.實際上，大多數(shù)時候我們并不關(guān)心F(n)的精確度量，而只是關(guān)心其量級。,算法復(fù)雜度的考察方法 （1）考察一個算法的復(fù)雜度，一般考察的是當(dāng)問題復(fù)雜度n的增加時，運算所需時間、空間代價f(n)的上下界。 （2）進(jìn)一步而言，又分為最好情況、平均情況、最壞情況三種情況。通常最壞情況往往是我們最關(guān)注的。,（1）上界函數(shù),

3、定義1 如果存在兩個正常數(shù)c和n0，對于所有的nn0，有 |T(n)| c|f(n)| 則記作T(n) = (f(n) 含義： 如果算法用n值不變的同一類數(shù)據(jù)在某臺機(jī)器上運行時，所用的時間總是小于|f(n)|的一個常數(shù)倍。所以f(n)是計算時間T(n)的一個上界函數(shù)。 試圖求出最小的f(n)，使得T(n) = (f(n)。,在分析算法的時間復(fù)雜度時，我們更關(guān)心最壞情況而不是最好情況，理由如下： （1）最壞情況給出了算法執(zhí)行時間的上界，我們可以確信，無論給什么輸入，算法的執(zhí)行時間都不會超過這個上界，這樣為比較和分析提供了便利。 （2）雖然最壞情況是一種悲觀估計，但是對于很多問題，平均情況和最壞情

4、況的時間復(fù)雜度差不多，比如插入排序這個例子，平均情況和最壞情況的時間復(fù)雜度都是輸入長度n的二次函數(shù)。,定義1.2 如果存在兩個正常數(shù)c和n0，對于所有的nn0， 有 |T(n)| c|g(n)| 則記作T(n) = (g(n) 含義： 如果算法用n值不變的同一類數(shù)據(jù)在某臺機(jī)器上運行時，所用的時間總是不小于|g(n)|的一個常數(shù)倍。所以g(n)是計算時間T(n)的一個下界函數(shù)。 試圖求出“最大”的g(n)，使得T(n) = (g(n)。,（2）下界函數(shù),定義1.3 如果存在正常數(shù)c1，c2和n0，對于所有的nn0，有 c1|g(n)| |T(n)| c2|g(n)| 則記作 含義： 算法在最好和

5、最壞情況下的計算時間就一個常數(shù)因子范圍內(nèi)而言是相同的?？煽醋鳎?既有 T(n) = (g(n)，又有T(n) = (g(n),（3） “平均情況”限界函數(shù),常見算法時間復(fù)雜度：O(1): 表示算法的運行時間為常量O(n): 表示該算法是線性算法O(2n): 二分搜索算法O(n2n): 快速排序算法 O(n2): 對數(shù)組進(jìn)行排序的各種簡單算法，例如直接插入排序的算法。O(n3): 做兩個n階矩陣的乘法運算O(2n): 求具有n個元素集合的所有子集的算法O(n!): 求具有N個元素的全排列的算法 優(yōu)-劣 O(1)O(2n)O(n) O(n2n): O(n2)O(2n),典型的計算時間函數(shù)曲線,計算

6、算法時間復(fù)雜度過程： （1）確定基本操作 （2）構(gòu)造基于基本操作的函數(shù)解析式 （3）求解函數(shù)解析式,如果構(gòu)建的是遞推關(guān)系式，那么常用的求解方法有： （1）前向替換法 可以從初始條件給出的序列初始項開始，使用遞推方程生成序列的前面若干項，寄希望于從中找出一個能夠用閉合公式表示的模式。如果找到了這樣的公式，我們可以用兩種方法對它進(jìn)行驗證：第一，將它直接代入遞歸方程和初始條件中。第二，用數(shù)學(xué)歸納法來證明。,例如，考慮如下遞推式： X(n) = 2X(n-1) +1 n1 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)=

7、2x(3)+1=2*7+1=15 X(n)=2n-1 n0,（2）反向替換法 例如：X(n)=x(n-1)+n 使用所討論的遞推關(guān)系，將x(n-1)表示為x(n-2)得函數(shù)，然后把這個結(jié)果代入原始方程，來把x(n)表示為x(n-2)的函數(shù)。重復(fù)這一過程。,X(n)=x(0)+1+2+3+4+5+n=0+1+2+3=4 = n(n+1)/2,（3）換名,上面形式的在遞推關(guān)系式，一個規(guī)模為n的問題，每一次遞歸調(diào)用后，都簡化為n/k規(guī)模的問題，為了方便求解，我們通常設(shè)定：n=km， 則，上面的求解過程可簡化為： f(n)= f(km-1)+b = f(km-2)+2b = = f(k0)+mb =

8、f(1) + blog n,幾種常見復(fù)雜度舉例： O(logn) 我們學(xué)過的算法，二分搜索,int BinSrch(Type A,int i, int n, Type x) /Ai.n是非遞減排列 且 1Amid) return BinSrh(A, mid+1, n, x);遞歸調(diào)用 ,遞歸關(guān)系式：,因為規(guī)模每一次遞歸調(diào)用后，縮減為原來的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+1,觀察遞歸調(diào)用的過程以及遞推關(guān)系式： （1）在遞歸關(guān)系式中：遞歸調(diào)用共有

9、k次，我們設(shè)n= 2k，k=logn （2）遞歸調(diào)用的二叉樹型結(jié)構(gòu)中，調(diào)用次數(shù)為二叉樹的深度。,2. O(n): 表示該算法是線性算法 目前所學(xué)的算法中有：線性選擇算法,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)用 return r1; else /sk int r1=Select(data,s+1,r,k-s);-遞歸調(diào)用 return r1; ,如果遞歸調(diào)用，每次規(guī)模是原來的1/2：,

10、因為每一次規(guī)模都減到原來的1/2，所以用換名的方法設(shè) n = 2k： T(n) = T(n/2) + (n-1) = 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,算法時間復(fù)雜度：O(n) 分析：,算法的復(fù)雜度有兩部分決定：遞歸和合并，遞歸的復(fù)雜度是：logn，合并的復(fù)雜度是 n。,3.O(nlogn) 所學(xué)過的算法：快速排序、堆排序等，分治法中的平面中最接近點對問題。 遞推關(guān)系式：,T(n)=2T(n/2) +n

11、設(shè)n= 2k =2T(2k-1)+2k =22T(2k-2)+2k-1+2k =22T(2k-2)+2*2k = =2k-1T(2k-(k-1) + (k-1)*2k =n/2 + (logn-1) *n,不失一般性，設(shè)規(guī)模為n的問題，每一次有分解為m個子問題，設(shè)n =mk，則：,T(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,算法時間復(fù)雜度：O(nlogn) 分析：,算法的復(fù)雜度有兩部分決定：遞歸和合并，遞歸的復(fù)雜度是：n，合并的復(fù)雜度是 nlog

12、n。,4. O(n2) 通常的兩層嵌套循環(huán)，內(nèi)層的運算執(zhí)行次數(shù)，學(xué)過的例子有：比賽日程,T(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é)過的：大整數(shù)乘法,Recursive_Miltiply(x,y) if n=1 if (X=1)and(Y=1) return(1) else return(0) x1 =X的左邊n/2位; x0 =

13、X的右邊n/2位; y1 =Y的左邊n/2位; y0 =Y的右邊n/2位; p = Recursive_Miltiply(x1+x0,y1+y0);遞歸調(diào)用 x1y1 = Recursive_Miltiply(x1,y1);遞歸調(diào)用 x0y0 = Recursive_Miltiply(x0,y0);遞歸調(diào)用 return x1y1*2n + (p-x1y1-x0y0)*2n/2+x0y0;基本操作 ,設(shè)，n=2k, 用反向替換法對它求解：,分析： 在這個遞推關(guān)系式中，算法每次遞歸調(diào)用3個規(guī)模為1/2的子問題，那么總的規(guī)模3/2，大小，所以，粗略估算要在O(nlogn)、O(n2)之間。,相關(guān)習(xí)

14、題 求下列函數(shù)的漸進(jìn)表達(dá)式： 3n2+10n n2/10+2n 21+1/n logn3 10log3n,=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）假設(shè)某算法在輸入規(guī)模為n時的計算時間為 T(n)=3*2n。在某臺計算機(jī)上實現(xiàn)并完成該算法的時間為t?，F(xiàn)在有另一臺計算機(jī)，其運行速度為第一臺的64倍，那么在這臺新機(jī)器上用同一算法在t秒內(nèi)能解輸入規(guī)模為多大的

15、問題？,設(shè)新機(jī)器用統(tǒng)一算法能解輸入規(guī)模為n1的問題，則： t=3*2n1/64=3*2n1-6 所以，n1=n+6,(2) 若上述的算法改為T(n)=n2，其他條件不變，則在新機(jī)器上用t秒時間能解輸入規(guī)模為多大的問題？,n12=64n2=(8n)2 能解規(guī)模為8n的問題,(3) 若上述的算法改為T(n)=8，其他條件不變，則在新機(jī)器上用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) f(n) = logn2 g(n)=logn +5 f(n)=logn2 g(n) = f(n)=n g(n)=log2n f(n)= nlogn g(n)=log(n) f(n)=10 g(n)=log10 f(n)=log2n g(n)=logn f(n)=2n g(n)=100n2 f(n)=2n g(n)=3n,5.螺釘和螺母問題 假設(shè)我們有n個直徑各不相同的螺釘，以及n個相應(yīng)的螺母。我們一次只能比較一對螺釘和螺母，來判斷螺母是大于螺釘、小于螺釘還是正好合適螺釘。然而，我們不能拿兩個螺母作比較，也不能拿兩個螺釘作比較。我們的問題是要找到每一對匹配的螺釘和螺母，