6算法復(fù)雜性漸近階的分析

1、算法復(fù)雜性漸近階的分析前兩段講的是算法復(fù)雜性漸近階的概念和對(duì)它進(jìn)行分析的重要性。本段要講如何具體 地分析一個(gè)算法的復(fù)雜性的漸近階，給出一套可操作的規(guī)則。算法最終要落實(shí)到用某種程序 設(shè)計(jì)語(yǔ)言（如Pascal）編寫成的程序。因此算法復(fù)雜性漸近階的分析可代之以對(duì)表達(dá)該算 法的程序的復(fù)雜性漸近階的分析。如前所提出，對(duì)于算法的復(fù)雜性，我們只考慮最壞、最好和平均三種情況，而通常又 著重于最壞情況。為了明確起見，本段限于針對(duì)最壞情況。仍然以時(shí)間復(fù)雜性為例。這里給出分析時(shí)間復(fù)雜性漸近階的八條規(guī)則。這八條規(guī)則已 覆蓋了用Pascal語(yǔ)言程序所能表達(dá)的各種算法在最壞情況下的時(shí)間復(fù)雜性漸近階的分析。在逐條地列出并解

2、釋這入條規(guī)則之前，應(yīng)該指出，當(dāng)我們分析程序的某一局部（如一個(gè) 語(yǔ)句，一個(gè)分程序，一個(gè)程序段，一個(gè)過程或函數(shù)）時(shí)，可以用具體程序的輸入的規(guī)模N作 為復(fù)雜性函數(shù)的自變量，也可以用局部的規(guī)模參數(shù)作為自變量。但是，作為最終結(jié)果的整體 程序的復(fù)雜性函數(shù)只能以整體程序的輸入規(guī)模為自變量。對(duì)于串行的算法，相應(yīng)的Pascal程序是一個(gè)串行的Pascal語(yǔ)句序列，因此，很明顯， 該算法的時(shí)間復(fù)雜性（即所需要的時(shí)間）等于相應(yīng)的Pascal程序的每一個(gè)語(yǔ)句的時(shí)間復(fù)雜性 （即所需要的時(shí)間）之和。所以，如果執(zhí)行Pascal語(yǔ)句中的每一種語(yǔ)句所需要的時(shí)間都有計(jì) 量的規(guī)則，那么，執(zhí)行一個(gè)程序，即執(zhí)行一個(gè)算法所需要的時(shí)間的計(jì)

3、量便只是一個(gè)代數(shù)問題。 接著，應(yīng)用本節(jié)第三段所提供的0、Q和0等運(yùn)算規(guī)則就可以分析出算法時(shí)間復(fù)雜性的漸 近階。因此，我們的時(shí)間計(jì)量規(guī)則只需要針對(duì)Pascal有限的幾種基本運(yùn)算和幾種基本語(yǔ)句。 下面是這些規(guī)則的羅列和必要的說明。規(guī)則（1）賦值、比較、算術(shù)運(yùn)算、邏輯運(yùn)算、讀寫單個(gè)常量或單個(gè)變量等，只需要1個(gè)單位時(shí) 間。規(guī)則條件語(yǔ)句if C then S1 else S2只需要Tc+max（Ts1, Ts2）的時(shí)間，其中Tc是計(jì)算條件表 達(dá)式C需要的時(shí)間，而Ts1和Ts2分別是執(zhí)行語(yǔ)句S1和S2需要的時(shí)間。規(guī)則選擇語(yǔ)句”Case A of a1:S1; a2:S2; . ;am:Sm; end”，需

4、要 max（Ts1, Ts2，.， Tsm）的時(shí)間，其中Tsii是執(zhí)行語(yǔ)句Si所需要的時(shí)間，i=l,2,.,m。規(guī)則（4）訪問一個(gè)數(shù)組的單個(gè)分量或一個(gè)記錄的單個(gè)域，只需要1個(gè)單位時(shí)間。規(guī)則執(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”或一個(gè)repeat循環(huán)語(yǔ)句”repeat S until C，需 要的時(shí)間等于計(jì)算條件表達(dá)式C需要的時(shí)間與執(zhí)行循環(huán)S體需要的時(shí)間之和乘以循環(huán)的次 數(shù)。與規(guī)則5不同，這里的循環(huán)次數(shù)是隱含的。例如，b_search函數(shù)中的while循環(huán)語(yǔ)句。按規(guī)則(1)-(4)，計(jì)算條件表達(dá)

5、式” (not found)and(U=L)與執(zhí)行循環(huán)體I:=(U+L)div 2;if c=AI then found:=trueelse if cAI then L:=I+1else U:=I-1;只需要0(1)時(shí)間，而循環(huán)次數(shù)為logm，所以，執(zhí)行此while語(yǔ)句只需要G(logm)時(shí)間。在許多情況下，運(yùn)用規(guī)則(5)和(6)常常須要借助具體算法的內(nèi)涵來確定循環(huán)的次數(shù)，才 不致使時(shí)間的估計(jì)過于保守。這里舉一個(gè)例子。考察程序段：Size:=m;1i：=1；while i0 then begin1在1到Size的范圍內(nèi)任選一個(gè)數(shù)賦值給t;。Size:=Size-t; for j:=l to t

6、 do2end;end;成n)程序在各行右端頂格處標(biāo)注著執(zhí)行相應(yīng)各行所需要的時(shí)間。如果不對(duì)算法的內(nèi)涵作較 深入的考察，只看到1tSzem,就草率地估計(jì)while的內(nèi)循環(huán)for的循環(huán)次數(shù)為0(m)， 那么，程序在最壞情況下的時(shí)間復(fù)雜性將被估計(jì)為0( 2+mn 2)。反之，如果對(duì)算法的內(nèi)涵 認(rèn)真地分析，結(jié)果將兩樣。事實(shí)上，在while的循環(huán)體內(nèi)t是動(dòng)態(tài)的,size也是動(dòng)態(tài)的，它們 都取決while的循環(huán)參數(shù)i，即t=t(i)記為； size=size(i)記為size、i=l,2,.,n-1。對(duì)于各個(gè) i，1in-1, t與m的關(guān)系是隱含的，這給準(zhǔn)確地計(jì)算for循環(huán)的循環(huán)體S2被執(zhí)行的次數(shù)帶 來困

7、難。上面的估計(jì)比較保守的原因在于我們把S2的執(zhí)行次數(shù)的統(tǒng)計(jì)過于局部化。如果不n-1局限于for循環(huán)，而是在整個(gè)程序段上統(tǒng)計(jì)S2被執(zhí)行的總次數(shù)，那么，這個(gè)總次數(shù)等于H ，n-1 切又根據(jù)算法中t.的取法及size =size.-t.，i=1,2,.,n-1有size =size，=1 。最后利用ii+1 i in 1n-1asize1=m和sizen=0得到日 =m。于是在整個(gè)程序段上，S2被執(zhí)行的總次數(shù)為m，所需 要的時(shí)間為&(mn)。執(zhí)行其他語(yǔ)句所需要的時(shí)間直接運(yùn)用規(guī)則(l)-(6)容易計(jì)算。累加起來， 整個(gè)程序段在最壞情況下時(shí)間復(fù)雜性漸近階為0(n 2+mn)。這個(gè)結(jié)果顯然比前面粗糙的估計(jì)

8、 準(zhǔn)確。規(guī)則對(duì)于goto語(yǔ)句。在Pascal中為了便于表達(dá)從循環(huán)體的中途跳轉(zhuǎn)到循環(huán)體的結(jié)束或跳 轉(zhuǎn)到循環(huán)語(yǔ)句的后面語(yǔ)句，引入goto語(yǔ)句。如果我們的程序按照這一初衷使用goto語(yǔ)句， 那么，在時(shí)間復(fù)雜性分析時(shí)可以假設(shè)它不需要任何額外的時(shí)間。因?yàn)檫@樣做既不會(huì)低估也不 會(huì)高估程序在最壞情況下的運(yùn)行時(shí)間的階。如果有的程序?yàn)E用了 goto語(yǔ)句，即控制轉(zhuǎn)移到 前面的語(yǔ)句，那么情況將變得復(fù)雜起來。當(dāng)這種轉(zhuǎn)移造成某種循環(huán)時(shí)，只要與別的循環(huán)不交 叉，保持循環(huán)的內(nèi)外嵌套，則可以比照規(guī)則(1)-(6)進(jìn)行分析。當(dāng)由于使用goto語(yǔ)句而使程 序結(jié)構(gòu)混亂時(shí)，建議改寫程序然后再做分析。規(guī)則(8)對(duì)于過程調(diào)用和函數(shù)調(diào)用語(yǔ)

9、句，它們需要的時(shí)間包括兩部分，一部分用于實(shí)現(xiàn)控制轉(zhuǎn) 移，另一部分用于執(zhí)行過程(或函數(shù))本身，這時(shí)可以根據(jù)過程(或函數(shù))調(diào)用的層次，由里向 外運(yùn)用規(guī)則(l)-(7 )進(jìn)行分析，一層一層地剝，直到計(jì)算出最外層的運(yùn)行時(shí)間便是所求。如果 過程(或函數(shù))出現(xiàn)直接或間接的遞歸調(diào)用，則上述由里向外逐層剝的分析行不通。這時(shí)我們 可以對(duì)其中的各個(gè)遞歸過程(或函數(shù))，所需要的時(shí)間假設(shè)為一個(gè)相應(yīng)規(guī)模的待定函數(shù)。然后 一一根據(jù)過程(或函數(shù))的內(nèi)涵建立起這些待定函數(shù)之間的遞歸關(guān)系得到遞歸方程。最后用求 遞歸方程解的漸進(jìn)階的方法確定最壞情況下的復(fù)雜性的漸進(jìn)階。遞歸方程的種類很多，求它們的解的漸近階的方法也很多，我們將在下

10、一段比較系統(tǒng) 地給予介紹。本段只舉一個(gè)簡(jiǎn)單遞歸過程(或函數(shù))的例子來說明如何建立相應(yīng)的遞歸方程， 同時(shí)不加推導(dǎo)地給出它們?cè)谧顗那闆r下的時(shí)間復(fù)雜性的漸近階。例：再次考察函數(shù)b_search，這里將它改寫成一個(gè)遞歸函數(shù)。為了簡(jiǎn)明，我們已經(jīng)運(yùn) 用前面的規(guī)則(1)-(6)，統(tǒng)計(jì)出執(zhí)行各行語(yǔ)句所需要的時(shí)間，并標(biāo)注在相應(yīng)行的右端：Function b_search(C,L,U:integer):integer; var index,element:integer;begin單位時(shí)間數(shù)if (UC thenb_search:=b_search(C,L,index-1) else3+T(m/2)b_searc

11、h:=b_search(C,index+1,U); end;3+T(m/2)end;其中T(m)是當(dāng)問題的規(guī)模U-L+1=m時(shí)b_search在最壞情況下(這時(shí)，數(shù)組AL.U中沒有給定的C)的時(shí)間復(fù)雜性。根據(jù)規(guī)則(l)-(8)，我們有：T(m)= /2)m = m 或化簡(jiǎn)為1311+丁伽 / 2)這是一個(gè)關(guān)于T(m)的遞歸方程。用下一段將介紹的迭代法，容易解得：T(m)=11logm +l3= Rlogm)在結(jié)束這一段之前，我們要提一下關(guān)于算法在最壞情況下的空間復(fù)雜性分析。我們照 樣可以給出與分析時(shí)間復(fù)雜性類似的規(guī)則。這里不贅述。然而應(yīng)該指出，在出現(xiàn)過程;或函 數(shù))遞歸調(diào)用時(shí)要考慮到其中隱含的存儲(chǔ)空間的額外開銷。因?yàn)楝F(xiàn)有的實(shí)現(xiàn)過程(或函數(shù))遞歸調(diào)用的編程技術(shù)需要一個(gè)隱含的、額外（即不出現(xiàn)在程序的說明中）的棧來支持。過程（或函數(shù)） 的遞歸調(diào)用每深人一