1、2. 算法的時(shí)間復(fù)雜性分析基礎(chǔ),2.1影響問(wèn)題求解時(shí)間的因素 A：算法 n：?jiǎn)栴}的規(guī)模 I ：輸入數(shù)據(jù) 復(fù)雜性的形式化表示T(A,n,I) 對(duì)于特定算法，時(shí)間復(fù)雜性為： T(n,I),2.1時(shí)間復(fù)雜性函數(shù),T(N,I) 是算法在一臺(tái)抽象的計(jì)算機(jī)上運(yùn)行所需的時(shí)間。設(shè)此抽象的計(jì)算機(jī)所提供的元運(yùn)算有k種，他們分別記為O1,O2 ,.,Ok；設(shè)這些元運(yùn)算每執(zhí)行一次所需要的時(shí)間分別為t1,t2,.,tk 。 對(duì)于給定的算法A，用到元運(yùn)算Oi的次數(shù)為ei，i=1,2,.,k ，很明顯，對(duì)于每一個(gè)i， ei是n和I的函數(shù)，即ei=ei(n,I)。那么有：,其中ti，i=1,2,.,k,是與N,I無(wú)關(guān)的常數(shù)。

2、,先看一個(gè)實(shí)例： 改進(jìn)冒泡如排序算法的基本步驟如下： for i 1 to n-1 do flag 1 for j 1 to n-i do if ajaj+1 then 交換aj、aj+1 flag 0 /*發(fā)生了交換*/ if flag then beak /* 沒(méi)有交換，排序結(jié)束*/ enddo 如果將if ajaj+1 then . 當(dāng)做一個(gè)元運(yùn)算，花的時(shí)間為C 當(dāng)輸入的數(shù)據(jù)已經(jīng)排好序，做了n-1次元運(yùn)算； 當(dāng)輸入的數(shù)據(jù)是增序，則需要做n(n-1)/2次元運(yùn)算。,顯然，不可能對(duì)規(guī)模n的每一種合法的輸入I都去統(tǒng)計(jì)ei(n,I),i=1,2,k。因此T(n,I)的表達(dá)式還得進(jìn)一步簡(jiǎn)化。 只能

3、在規(guī)模為n的某些或某類(lèi)有代表性的合法輸入中統(tǒng)計(jì)相應(yīng)的ei , i=1,2,k，評(píng)價(jià)時(shí)間復(fù)雜性。,一般只考慮三種情況下的時(shí)間復(fù)雜性，即最壞情況、最好情況和平均情況下的時(shí)間復(fù)雜性，井分別記為： W(n) = max T(n，I) , IDn B(n) = min T(n，I) , IDn A(n)P( I )T(n，I) IDn Dn是規(guī)模為n的合法輸入的集合，P(I)是在算法的應(yīng)用中 出現(xiàn)輸入I 的概率。 最具有可操作性和實(shí)際價(jià)值的是最壞情況下的時(shí)間復(fù)雜 性。我們對(duì)算法的時(shí)間復(fù)雜性分析的興趣主要將放在W(n) 上。沒(méi)有特殊說(shuō)明時(shí)，T(n)一般指的就是W(n)。,對(duì)于同一類(lèi)問(wèn)題，采用這類(lèi)算法的基本

4、運(yùn)算次數(shù)作為算法的運(yùn)算時(shí)間。 例如： “漢諾塔”算法的基本運(yùn)算是圓盤(pán)的移動(dòng)； 比較排序算法，用算法所用的比較次數(shù)作為該類(lèi)算法的 運(yùn)算時(shí)間； 矩陣相乘：基本運(yùn)算是兩個(gè)數(shù)的相乘； 樹(shù)的搜索：基本運(yùn)算是節(jié)點(diǎn)的訪(fǎng)問(wèn)； 圖的算法：節(jié)點(diǎn)和邊的運(yùn)算。,2.2.1算法時(shí)間復(fù)雜性計(jì)量,2.2.2 時(shí)間復(fù)雜性的計(jì)算規(guī)則,分析時(shí)間復(fù)雜性漸近階的8條規(guī)則 ： 規(guī)則1： 賦值、比較、算術(shù)運(yùn)算、邏輯運(yùn)算、讀寫(xiě)單個(gè)常量或單個(gè)變量等，只需要1個(gè)單位時(shí)間。 規(guī)則2 條件語(yǔ)句if C then S1 else S2需要Tc+max(Ts1，Ts2)的時(shí)間，其中Tc是計(jì)算條件表達(dá)式C需要的時(shí)間，而Ts1和Ts2分別是執(zhí)行語(yǔ)句S1和

5、S2需要的時(shí)間。 規(guī)則3 選擇語(yǔ)句Case A a1:S1; a2:S2; ;am:Sm; end，需要max(Ts1, Ts2，Tsm)的時(shí)間，其中Tsi是執(zhí)行語(yǔ)句Si所需要的時(shí)間，i=l,2,m。,規(guī)則4 訪(fǎng)問(wèn)一個(gè)數(shù)組的單個(gè)分量或一個(gè)記錄的單個(gè)域，只需要1個(gè)單位時(shí)間。 規(guī)則5 執(zhí)行一個(gè)for循環(huán)語(yǔ)句需要的時(shí)間等于執(zhí)行該循環(huán)體所需要的時(shí)間乘上循環(huán)的次數(shù)。 規(guī)則6 執(zhí)行一個(gè)while循環(huán)語(yǔ)句“while C do S”，需要的時(shí)間等于 (計(jì)算條件表達(dá)式C的時(shí)間+執(zhí)行循環(huán)S體的時(shí)間)*循環(huán)的次數(shù)。,規(guī)則6與規(guī)則5不同，循環(huán)次數(shù)是隱含的。 例如，b_search函數(shù)中的while循環(huán)語(yǔ)句。按規(guī)則(

6、1)-(4)， while (not found)and(U=L) m(U+L) div 2 if c=Am then foundtrue else if cAm then L I+1 else U m-1 ,規(guī)則7 對(duì)于break語(yǔ)句。為了便于表達(dá)從循環(huán)體的中途跳轉(zhuǎn)到循環(huán)體的結(jié)束,引入break 語(yǔ)句。在時(shí)間復(fù)雜性分析時(shí)可以假設(shè)它不需要任何額外的時(shí)間。 規(guī)則8 對(duì)于過(guò)程調(diào)用和函數(shù)調(diào)用語(yǔ)句，它們需要的時(shí)間包括兩部分，一部分用于實(shí)現(xiàn)控制轉(zhuǎn)移，另一部分用于執(zhí)行過(guò)程(或函數(shù))本身，這時(shí)可以根據(jù)過(guò)程(或函數(shù))調(diào)用的層次，由里向外運(yùn)用規(guī)則(l)-(7)進(jìn)行分析，一層一層地剝，直到計(jì)算出最外層的運(yùn)行時(shí)間便

7、是所求。 如果過(guò)程(或函數(shù))出現(xiàn)直接或間接的遞歸調(diào)用，則根據(jù)過(guò)程(或函數(shù))的內(nèi)涵建立起這些待定函數(shù)之間的遞歸關(guān)系得到遞歸方程。最后用求遞歸方程解的漸進(jìn)階的方法確定最壞情況下的復(fù)雜性的漸進(jìn)階。,經(jīng)驗(yàn)和技巧是非常重要的,BUILD-MAX-HEAP(A) 1 heap-sizeA lengthA 2 for i lengthA/2 downto 1 n/2次 3 do MAX-HEAPIFY(A, i) 歸結(jié)到分析 MAX-HEAPIFY(A, i)的時(shí)間,例：建最大堆算法的復(fù)雜性分析,MAX-HEAPIFY(A, i) 1 l LEFT(i) 2 r RIGHT(i) 3 if l heap-s

8、izeA and Al Ai /與左孩子比較，不滿(mǎn)足堆的條件 4 then largest l /記下較大者的下標(biāo) 5 else largest i 6 if r heap-sizeA and Ar Alargest 7 then largest r /與右孩子比較，不滿(mǎn)足堆的條件 8 if largest i 9 then exchange Ai Alargest 10 MAX-HEAPIFY(A, largest) 每層比較2次，整理時(shí)間與i的高度成正比。,整理堆的實(shí)例,有n個(gè)節(jié)點(diǎn)的堆，最大整理時(shí)間為 2 log n。 粗略分析建堆的時(shí)間為 n log n，但似乎太不精確了。,考察實(shí)例的

9、建堆過(guò)程， 總體比較時(shí)間為所有節(jié)點(diǎn)的整理時(shí)間之和，各層上的節(jié)點(diǎn)的整理時(shí)間是相同的。,BUILD-MAX-HEAP(A) 1 heap-sizeA lengthA 2 for i lengthA/2 downto 1 3 do MAX-HEAPIFY(A, i),i在第h層上，整理的時(shí)間與h成正比，用O(h)表示。 第h層的節(jié)點(diǎn)數(shù)為n/2h+1 整理時(shí)間為n/2h+1 O(h)。 建構(gòu)堆的時(shí)間：,復(fù)雜性的漸近性態(tài)的概念,一個(gè)算法的時(shí)間復(fù)雜度(Time Complexity)T(n)是該算法的時(shí)間耗費(fèi)，是該算法所求解問(wèn)題規(guī)模n的函數(shù)。當(dāng)問(wèn)題的規(guī)模n趨向無(wú)窮大時(shí)，時(shí)間復(fù)雜度T(n)的數(shù)量級(jí)(階)稱(chēng)為

10、算法的復(fù)雜性的漸近性態(tài)（漸進(jìn)時(shí)間復(fù)雜度）。,分析算法的時(shí)間復(fù)雜性的目的是為了比較完成同一功能的程序的算法之間的最主要的差別。如果兩個(gè)算法執(zhí)行步數(shù)分別是 3n+2，3n+20， 時(shí)間復(fù)雜性至多相差一個(gè)常數(shù)倍。 對(duì)于兩個(gè)具有時(shí)間復(fù)雜性： 2n ，cn 對(duì)于充分大的n，兩者的復(fù)雜性差別是很大的。所以，我們 要引進(jìn)漸進(jìn)性，用復(fù)雜性的階描述算法的復(fù)雜性。,2.2 復(fù)雜性的漸近性態(tài),設(shè)T(N)是關(guān)于算法A的復(fù)雜性函數(shù)。一般說(shuō)來(lái)，當(dāng)N單調(diào)增加且趨于時(shí),T(N)也將單調(diào)增加趨于。對(duì)于T(N)，如果存在T(N)，使得當(dāng)N時(shí)有： (T(N )-T(N )/T(N ) 0 那么，我們就說(shuō)T(N)是T(N)當(dāng)N時(shí)的漸

11、近性態(tài)，或叫T(N)為算法A當(dāng)N的漸近復(fù)雜性，因?yàn)樵跀?shù)學(xué)上，T(N)是T(N)當(dāng)N時(shí)的漸近表達(dá)式。 T(N)是T(N)中略去低階項(xiàng)所留下的主項(xiàng)。所以它無(wú)疑比T(N)來(lái)得簡(jiǎn)單。,例如 T(n)=3N 2+4Nlog2N +7 時(shí)， T(N)的一個(gè)答案是3N 2。 顯然3N 2比3N 2 +4Nlog2N +7簡(jiǎn)單得多。 由于當(dāng)N時(shí)T(N)漸近于T(N)，我們有理由用T(N)來(lái)替代T(N)作為算法A在N時(shí)的復(fù)雜性的度量。這種替代是對(duì)復(fù)雜性分析的一種簡(jiǎn)化。,即當(dāng)問(wèn)題的規(guī)模充分大時(shí)，只要考察算法復(fù)雜性在漸近意義下的階。有3種漸近性態(tài)和其意義下的記號(hào)：、需要掌握。,f(n)是某一算法的時(shí)間復(fù)雜性函數(shù)，g

12、(n)是某一函數(shù)，當(dāng)且僅當(dāng)存在正的常數(shù)C和N0，使得對(duì)于所有的n=N0，有 f(n)=Cg(n)，記作 f(n)=O(g(n) 即函數(shù)f至多是函數(shù)g的C倍，當(dāng)充分大時(shí)，g是f的一個(gè)上 界函數(shù)，在相差一個(gè)非零常數(shù)倍的情況下。通常情況下，g 取下列單項(xiàng)的形式： 1 ，log n，n，n log n ，n2 ， n3 ， 2n ，n！,漸進(jìn)符號(hào)O的定義,例：C0=O(1): f(n) 等于非零常數(shù) 3n+2=O(n): 取C4，N02。 100n+6=O(n): 取 C=101，N 06。 62n+n2=O(n2): 取C=7，N0=4. 3log n + 2n + n2 =O(n2). nlog

13、n +n2=O(n2). 3n2+2=O(n2) g也稱(chēng)作f的階函數(shù)。對(duì)于多項(xiàng)式情形的復(fù)雜性函數(shù)，其階函數(shù)可取該多項(xiàng)式的最高項(xiàng)。,按照大的定義，有如下運(yùn)算規(guī)則：,1)(f)+(g)=(max(f,g)； 2)(f)+ (g)=(f +g)； 3)(f)(g)= (fg)； 4) 如果g(N)= (f(N)，則(f)+ (g)= (f)； 5)(Cf(N)= (f(N)，其中C是一個(gè)正的常數(shù)； 6) f =(f)；,規(guī)則1的證明： 設(shè)F(N)= (f) 。根據(jù)記號(hào)的定義，存在正常數(shù)C1和自然數(shù)N1，使得對(duì)所有的NN1，有F(N)C1 f(N)。類(lèi)似地，設(shè)G(N)=(g)，則存在正的常數(shù)C2和自然

14、數(shù)N2使得對(duì)所有的NN2有G(N)C2g(N)，令： C3=max(C1, C2)，N3=max(N1, N2) 和對(duì)任意的非負(fù)整數(shù)N， h(N)=max(f,g), 則對(duì)所有的NN3有：F(N)C1f(N)C1h(N)C3h(N) 類(lèi)似地，有：G(N)C2g(N)C2h(N)C3h(N) 因而 (f)+(g) =F(N)+G(N)C3h(N)+ C3h(N) =2C3h(N) =(h) =( max(f,g) ) 作業(yè)：證明規(guī)則 2)6),分析冒泡排序算法的時(shí)間復(fù)雜性。,for i 1 to n-1 do for j 1 to n-i do if ajaj+1 then 交換aj、aj+1；

15、,內(nèi)循環(huán)比較 次數(shù)：,外循環(huán)：,例 估計(jì)下面二重循環(huán)算法段在最壞情況下的時(shí)間復(fù)雜性T(N)的階,for il to N do for j 1 to i do S1 /S1是單一的賦值語(yǔ)句 對(duì)于內(nèi)循環(huán)體，顯然只需(l)時(shí)間。因而內(nèi)循環(huán)只需時(shí)間：,根據(jù)記號(hào)的定義，得到的只是當(dāng)規(guī)模充分大時(shí)的一個(gè)上界。這個(gè)上界的階越低則評(píng)估就越精確，結(jié)果就越有價(jià)值。,累加起來(lái)便是外循環(huán)的時(shí)間復(fù)雜性：,下界符號(hào)的定義,f(n)是某一算法的時(shí)間復(fù)雜性函數(shù)， g(n)是某一函數(shù)，當(dāng)且僅當(dāng)存在正的 常數(shù)C和N0，使得對(duì)于所有的n=N0， 有f(n)Cg(n)，記作 f(n)= (g(n) 當(dāng)n充分大時(shí)，在相差一個(gè)非零常數(shù)倍的

16、情況下， g是f的一個(gè)下界函數(shù)。 同理，這個(gè)下界的階越高，則評(píng)估就越精確，結(jié)果就越有價(jià)值。,符號(hào)的定義,當(dāng)且僅當(dāng)存在正的常數(shù)C1和C2，使得對(duì)于所有的n=N0，有 C1g(n) f(n) C2g(n )， 記作： f(n)= (g(n) 例：算法Search在最壞情況下的時(shí)間復(fù)雜性Tmax(m)。已有Tmax(m)=(m)和Tmax(m)=(m)，所以有Tmax(m)=(m)，這是對(duì)Tmax(m)的階的精確估計(jì)。,Procedure hanoi( n,a,b,c) T(n) if (n=1) then move(a,c); 1 else hanoi( n-1,a, c, b); T(n-1)

17、move(a,c); 1 hanoi( n-1, b, a , c); T(n-1) end. 設(shè)hanoi( n,a,b,c)的時(shí)間復(fù)雜性函數(shù)為T(mén)(n),這是一個(gè)遞歸方程?？梢杂玫ǎǖ幕静襟E是通過(guò)反復(fù)迭代，將遞歸方程的右端變換成一個(gè)級(jí)數(shù)，然后求級(jí)數(shù)的和。 T(n)=2T(n-1)+1 =22T(n-2)+1+1= 22T(n-2)+2+1 = 23T(n-3)+22+2+1 = 2n-1T(1)+2n-2+.2+1 = 2n-1,遞歸方程：,遞歸方程組解的漸進(jìn)階的求法母函數(shù)法,設(shè)關(guān)于T(n)的遞歸方程的解的母函數(shù)為：,(1)-(2)-(3)得,(1),(2),(3),根據(jù)G(x)的形式：,有T(n)=a2-b2,作業(yè),1 分析算法的時(shí)間復(fù)雜性 int Horner(int coeff, int n, const int x) /計(jì)算n次多項(xiàng)式的值，coeff 0:n 為多項(xiàng)式的系數(shù) int value= coeff n for ( int i = 1; i =