第2 章 算法效率分析課件

第二章算法效率分析算法效率（Efficiency）算法效率有什么作用算法效率是怎樣度量的，評價算法優(yōu)劣的依據(jù)是什么怎樣完成算法算法效率分析第二章算法效率分析算法效率（Efficiency）算法的復(fù)雜性算法的復(fù)雜性是算法效率的度量，是評價算法優(yōu)劣的重要依據(jù)。一個算法的復(fù)雜性的高低體現(xiàn)在運(yùn)行該算法所需要的計算機(jī)資源的多少上面，所需的資源越多，我們就說該算法的復(fù)雜性越高；反之，所需的資源越低，則該算法的復(fù)雜性越低。計算機(jī)的資源，最重要的是時間和空間（即存儲器）資源。因而，算法的復(fù)雜性有時間復(fù)雜性和空間復(fù)雜性之分。算法的復(fù)雜性算法的復(fù)雜性是算法效率的度量，是評價算法優(yōu)劣的重算法效率有什么作用不言而喻，對于任意給定的問題，設(shè)計出復(fù)雜性盡可能低的算法是我們在設(shè)計算法的一個重要目標(biāo)；另一方面，當(dāng)給定的問題已有多種算法時，選擇其中復(fù)雜性最低者，是我們在選用算法應(yīng)遵循的一個重要準(zhǔn)則。因此，算法的復(fù)雜性分析對算法的設(shè)計或選用有著重要的指導(dǎo)意義和實用價值。算法效率有什么作用不言而喻，對于任意給定的問題，設(shè)計出復(fù)雜性問題怎樣完成算法算法效率分析？用怎樣的一個量來表達(dá)一個算法的復(fù)雜性；對于給定的一個算法，怎樣具體計算它的復(fù)雜性。問題怎樣完成算法算法效率分析？復(fù)雜性的計量（一）算法的復(fù)雜性是算法運(yùn)行所需要的計算機(jī)資源的量，需要的時間資源的量稱作時間復(fù)雜性，需要的空間（即存儲器）資源的量稱作空間復(fù)雜性。這個量應(yīng)該集中反映算法中所采用的方法的效率，而從運(yùn)行該算法的實際計算機(jī)中抽象出來。換句話說，這個量應(yīng)該是只依賴于算法要解的問題的規(guī)模、算法的輸入和算法本身的函數(shù)。如果分別用N、I和A來表示算法要解問題的規(guī)模、算法的輸入和算法本身，用C表示算法的復(fù)雜性，那么應(yīng)該有：C=F(N,I,A)復(fù)雜性的計量（一）算法的復(fù)雜性是算法運(yùn)行所需要的計算機(jī)資源的復(fù)雜性的計量（二）其中F(N,I,A)是N,I,A的一個確定的三元函數(shù)。如果把時間復(fù)雜性和空間復(fù)雜性分開，并分別用T和S來表示，那么應(yīng)該有：

T=T(N,I,A)(2.1.1)和

S=S(N,I,A)(2.1.2)通常，我們讓A隱含在復(fù)雜性函數(shù)名當(dāng)中，因而將（2.1.1）和（2.1.2）分別簡寫為：

T=T(N,I)和S=S(N,I)。由于時間復(fù)雜性和空間復(fù)雜性概念類同，計算方法相似，且空間復(fù)雜性分析相對地簡單些，所以將主要地討論時間復(fù)雜性。復(fù)雜性的計量（二）其中F(N,I,A)是N,I,A的一個確定復(fù)雜性的計量（三）根據(jù)T(N,I)的概念，它應(yīng)是算法在一臺抽象計算機(jī)上運(yùn)行所需的時間。設(shè)此抽象計算機(jī)所提供的元運(yùn)算有k種，記為O1，O2，...，Ok；再設(shè)這些元運(yùn)算每執(zhí)行一次所需要的時間分別為t1，t2，...，tk。對于給定的算法A，設(shè)經(jīng)過統(tǒng)計，用到元運(yùn)算Oi的次數(shù)分別為ei，i=1，2，...，k，很明顯，對每一個i，1<=i<=k，ei是N和I的函數(shù)，即ei=ei(N,I)。那么有：

T(N,I)=∑tiei(N,I)

(2.1.3)其中{ti|i=1,2,..,k},是與N,I無關(guān)的常數(shù)。復(fù)雜性的計量（三）根據(jù)T(N,I)的概念，它應(yīng)是算法在一臺抽復(fù)雜性的計量（四）下面只考慮三種情況的復(fù)雜性，即最壞情況、最好情況和平均情況下的時間復(fù)雜性，并分別記為Tmax(N)、Tmin(N)和Tavg(N)。在數(shù)學(xué)上有：其中，DN是規(guī)模為N的合法輸入的集合；I*是DN中一個使T(N,I*)達(dá)到Tmax(N)的合法輸入，I~是DN中一個使T(N,I~)到Tmin(N)的合法輸入；而P(I)是在算法的應(yīng)用中出現(xiàn)輸入I的概率。復(fù)雜性的計量（四）下面只考慮三種情況的復(fù)雜性，即最壞情況、最復(fù)雜性的計量（五）以上三種情況下的時間復(fù)雜性各從某一個角度來反映算法的效率，各有各的用處，也各有各的局限性。但實踐表明可操作性最好的且最有實際價值的是最壞情況下的時間復(fù)雜性。一般來說，最好情況和最壞情況的時間復(fù)雜性是很難計量的，原因是對于問題的任意確定的規(guī)模N達(dá)到了Tmax(N)的合法輸入難以確定，而規(guī)模N的每一個輸入的概率也難以預(yù)測或確定。我們有時也按平均情況計量時間復(fù)雜性，但那時在對P(I)做了一些人為的假設(shè)（比如等概率）之后才進(jìn)行的。所做的假設(shè)是否符合實際總是缺乏根據(jù)。因此，在最好情況和平均情況下的時間復(fù)雜性分析還僅僅是停留在理論上。復(fù)雜性的計量（五）以上三種情況下的時間復(fù)雜性各從某一個角度來復(fù)雜性的漸近性（一）隨著經(jīng)濟(jì)的發(fā)展、社會的進(jìn)步、科學(xué)研究的深入，要求用計算機(jī)解決的問題越來越復(fù)雜，規(guī)模越來越大。但是，如果對這類問題的算法進(jìn)行分析時，把所有的元運(yùn)算都考慮進(jìn)去，精打細(xì)算，那么，由于問題的規(guī)模很大且結(jié)構(gòu)復(fù)雜，算法分析的工作量之大、步驟之繁將令人難以承受。因此，人們提出了對于規(guī)模充分大、結(jié)構(gòu)又十分復(fù)雜的問題的求解算法，其復(fù)雜性分析應(yīng)如何簡化的問題。復(fù)雜性的漸近性（一）隨著經(jīng)濟(jì)的發(fā)展、社會的進(jìn)步、科學(xué)研究的深復(fù)雜性的漸近性（二）設(shè)T(N)是在第二段中所定義的關(guān)于算法A的復(fù)雜性函數(shù)。一般說來，當(dāng)N單調(diào)增加且趨于∞時,T(N)也將單調(diào)增加趨于∞。對于T(N)，如果存在T’(N)，使得當(dāng)N→∞時有：(T(N)-T’(N))/T(N)→0我們就說T’(N)是T(N)當(dāng)N→∞時的漸近性態(tài)，或叫T’(N)為算法A當(dāng)N→∞的漸近復(fù)雜性而與T(N)相區(qū)別，因為在數(shù)學(xué)上，T’(N)是T(N)當(dāng)N→∞時的漸近表達(dá)式。T’(N)是T(N)中略去低階項所留下的主項。所以它無疑比T(N)來得簡單。比如當(dāng)T(N)=3N2+4Nlog2N+7時，T’(N)的一個答案是3N2，顯然3N2比3N2+4Nlog2N+7簡單得多。復(fù)雜性的漸近性（二）設(shè)T(N)是在第二段中所定義的關(guān)于算法A復(fù)雜性的漸近性（三）考慮到分析算法的復(fù)雜性的目的在于比較求解同一間題的兩個不同算法的效率，而當(dāng)要比較的兩個算法的漸近復(fù)雜性的階不相同時，只要能確定出各自的階，就可以判定哪一個算法的效率高。換句話說，這時的漸近復(fù)雜性分析只要關(guān)心T’(N)的階就夠了，不必關(guān)心包含在T’(N)中的常數(shù)因子。所以，我們常常又對T’(N)的分析進(jìn)--步簡化，即假設(shè)算法中用到的所有不同的元運(yùn)算各執(zhí)行一次，所需要的時間都是一個單位時間。由此，只要考察當(dāng)問題的規(guī)模充分大時，算法復(fù)雜性在漸近意義下的階。與此簡化的復(fù)雜性分析方法相配套，需要引入五個漸近意義下的記號：Ο（奧密克戎）、Ω（歐米伽）、θ（西塔）、ο和ω。復(fù)雜性的漸近性（三）考慮到分析算法的復(fù)雜性的目的在于比較求解復(fù)雜性的漸近性（四）設(shè)f(N)和g(N)是定義在正數(shù)集上的正函數(shù)。如果存在正的常數(shù)C和自然數(shù)N0，使得當(dāng)N≥N0時有f(N)≤Cg(N)。則稱函數(shù)f(N)當(dāng)N充分大時上有界，且g(N)是它的一個上界，記為f(N)=Ο(g(N))。這時我們還說f(N)的階不高于g(N)的階。根據(jù)記號Ο的定義，用它評估算法的復(fù)雜性，得到的只是當(dāng)規(guī)模充分大時的一個上界。這個上界的階越低則評估就越精確，結(jié)果就越有價值。復(fù)雜性的漸近性（四）設(shè)f(N)和g(N)是定義在正數(shù)集上的正復(fù)雜性的漸近性（五）按照大Ο的定義，容易證明它有如下運(yùn)算規(guī)則：Ο(f)+Ο(g)=Ο(max(f,g))；Ο(f)+Ο(g)=Ο(f+g)；Ο(f)·Ο(g)=Ο(f·g)；如果g(N)=Ο(f(N))，則Ο(f)+Ο(g)=Ο(f)；Ο(Cf(N))=Ο(f(N))，其中C是一個正的常數(shù)；f=Ο(f)；復(fù)雜性的漸近性（五）按照大Ο的定義，容易證明它有如下運(yùn)算規(guī)則復(fù)雜性的漸近性（六）估計下面二重循環(huán)算法段在最壞情況下的時間復(fù)雜性T(N)的階。

for(i=l;i<N;i++)for(j=l;j<N;j++){S1;S2;S3;S4;}其中Sk(k=1,2,3,4)是單一的賦值語句。對于內(nèi)循環(huán)體，顯然只需Ο(l)時間。因而內(nèi)循環(huán)只需時間。累加起來便是外循環(huán)的時間復(fù)雜性：

復(fù)雜性的漸近性（六）估計下面二重循環(huán)算法段在最壞情況下的時間復(fù)雜性的漸近性（七）記號Ω，定義如下：如果存在正的常數(shù)C和自然數(shù)N0，使得當(dāng)N≥N0時有f(N)≥Cg(N)，則稱函數(shù)f(N)當(dāng)N充分大時下有界，且g(N)是它的一個下界，記為f(N)=Ω(g(N))。這時我們還說f(N)的階不低于g(N)的階。復(fù)雜性的漸近性（七）記號Ω，定義如下：如果存在正的常數(shù)C和自復(fù)雜性的漸近性（八）Ω的這個定義的優(yōu)點是與Ο的定義對稱，缺點是當(dāng)f(N)對自然數(shù)的不同無窮子集有不同的表達(dá)式，且有不同的階時，未能很好地刻畫出f(N)的下界。比如當(dāng)：時，如果按上述定義，只能得到f(N)=Ω(1)，這是一個平凡的下界，對算法分析沒有什么價值。復(fù)雜性的漸近性（八）Ω的這個定義的優(yōu)點是與Ο的定義對稱，缺點復(fù)雜性的漸近性（九）用Ω評估算法的復(fù)雜性，得到的只是該復(fù)雜性的一個下界。這個下界的階越高，則評估就越精確，結(jié)果就越有價值。對于一個問題和任意給定的充分大的規(guī)模N，下界在該問題的所有算法或某類算法的復(fù)雜性中取，那么它將更有意義。這時得到的相應(yīng)下界，我們稱之為問題的下界或某類算法的下界。它常與Ο配合證明問題的某個特定算法是該問題的最優(yōu)算法或是在某算法類中的最優(yōu)算法。復(fù)雜性的漸近性（九）用Ω評估算法的復(fù)雜性，得到的只是該復(fù)雜性復(fù)雜性的漸近性（十）定義f(N)=θ(g(N))，有f(N)=Ο(g(N))且f(N)=Ω(g(N))。這時，我們說f(N)與g(N)同階。對于任意給定的ε≥0，都存在非負(fù)整數(shù)N0，使得當(dāng)N≥N0時有f(N)≤εg(N)，則稱函數(shù)f(N)當(dāng)N充分大時比g(N)低階，記為f(N)=o(g(N))，例如：4NlogN+7=o(3N2+4NlogN+7)；f(N)=ω(g(N))定義為g(N)=o(f(N))。即當(dāng)N充分大時f(N)的階比g(N)高。我們看到Ο對于O有如ω對于Ω。復(fù)雜性的漸近性（十）定義f(N)=θ(g(N))，有f(N)復(fù)雜性的漸近性（十一）以下表述雖不很精確，但可幫助記憶：

f

=

Ο(g)

?

f≤g

f

=

Ω(g)

?

f≥g

f

=

θ

(g)

?

f=g

f

=

o

(g)

?

f<g

f

=

ω

(g)

?

f>g復(fù)雜性的漸近性（十一）以下表述雖不很精確，但可幫助記憶：

復(fù)雜性漸近階的重要性（一）隨著計算機(jī)的設(shè)計和制造技術(shù)的突飛猛進(jìn)，計算機(jī)的計算速度和存儲容量在直線增長。有人從而認(rèn)為不必要再去苦苦地追求高效算法，不必去無謂地進(jìn)行復(fù)雜性的分析。以為低效的算法可以由高速的計算機(jī)來彌補(bǔ)。但實際上，計算機(jī)解決的問題復(fù)雜程度和規(guī)模的線性增長，對低效算法來說，導(dǎo)致的時耗和空間需求是以幾何的方式增長的，計算機(jī)速度和容量的需求將入不付出。復(fù)雜性漸近階的重要性（一）隨著計算機(jī)的設(shè)計和制造技術(shù)的突飛猛算法與漸近階的關(guān)系（一）設(shè)A1,A2,…和A6，它們的漸近時間復(fù)雜性分別為N，NlogN，N2，N3，2N，N!，是求解同一間題的6種不同的算法，這六種算法分別在C1和C2兩臺計算機(jī)上運(yùn)行，設(shè)計算機(jī)C2的計算速度是計算機(jī)C1的10倍。在可接受的一段時間內(nèi)，設(shè)在C1上算法Ai可能求解的問題的規(guī)模為N1i，而在C2上可能求解的問題的規(guī)模為N2i，那么，我們就應(yīng)該有Ti(N2i)=10Ti(N1i)，其中Ti(N)是算法Ai漸近的時間復(fù)雜性，i=1,2,…,6。分別解出N2i和N1i的關(guān)系，可列成下表。算法與漸近階的關(guān)系（一）設(shè)A1,A2,…和A6，它們的漸近時表2-1表2-1算法與漸近階的關(guān)系（二）從表2-1可以清楚地看到，對于低效的算法，計算速度增長基本上不帶來求解規(guī)模的增益。對表的最后一列觀察發(fā)現(xiàn)，限制求解問題規(guī)模的關(guān)鍵因素是算法漸近復(fù)雜性的階?？梢?，算法的漸近復(fù)雜性的階對于算法的效率有著決定性的意義。所以在討論算法的復(fù)雜性時基本上都只關(guān)心它的漸近階。多項式算法是有效的算法。絕大多數(shù)的問題都有多項式算法。但也有一些問題還未找到多項式算法，只找到指數(shù)型算法。算法與漸近階的關(guān)系（二）從表2-1可以清楚地看到，對于低效的算法與漸近階的關(guān)系（三）“復(fù)雜性的漸近階比較低的算法比復(fù)雜性的漸近階比較高的算法有效”這個結(jié)論，只是在問題的求解規(guī)模充分大時才成立。比如算法A4比A5有效只是在N3<2N，即N≥c時才成立。其中c是方程N(yùn)3=2N的解。當(dāng)N<c時，A5反而比A4有效。所以對于規(guī)模小的問題，不要盲目地選用復(fù)雜性階比較低的算法。其原因一方面是如上所說，復(fù)雜性階比較低的算法在規(guī)模小時不一定比復(fù)雜性階比較高的算法更有效；另方面，在規(guī)模小時，決定工作效率的可能不是算法的效率而是算法的簡單性，哪一種算法簡單，實現(xiàn)起來快，就選用那一種算法。算法與漸近階的關(guān)系（三）“復(fù)雜性的漸近階比較低的算法比復(fù)雜性算法與漸近階的關(guān)系（四）當(dāng)要比較的兩個算法的漸近復(fù)雜性的階相同時，必須進(jìn)一步考察漸近復(fù)雜性表達(dá)式中常數(shù)因子才能判別它們誰好誰差。顯然常數(shù)因子小的優(yōu)于常數(shù)因子大的算法。比如漸近復(fù)雜性為N1ogN/l00的算法顯然比漸近復(fù)雜性為l00NlogN的算法來得有效。算法與漸近階的關(guān)系（四）當(dāng)要比較的兩個算法的漸近復(fù)雜性的階相算法復(fù)雜性漸近階的分析算法復(fù)雜性漸近階的分析可以對表達(dá)該算法的程序的復(fù)雜性漸近階的分析來代替。對于算法的復(fù)雜性，我們只考慮最壞、最好和平均三種情況，而通常又著重于最壞情況?，F(xiàn)限于最壞情況分析。當(dāng)我們分析程序的某一局部(如一個語句，一個分程序，一個程序段，一個過程或函數(shù))時，可以用具體程序的輸入的規(guī)模N作為復(fù)雜性函數(shù)的自變量，也可以用局部的規(guī)模參數(shù)作為自變量。但作為最終結(jié)果的整體程序的復(fù)雜性函數(shù)只能以整體程序的輸入規(guī)模為自變量。算法復(fù)雜性漸近階的分析算法復(fù)雜性漸近階的分析可以對表達(dá)該算法時間復(fù)雜性漸近階的分析規(guī)則算法復(fù)雜性漸近階的分析可以對表達(dá)該算法的程序的復(fù)雜性漸近階的分析來代替。對于算法的復(fù)雜性，我們只考慮最壞、最好和平均三種情況，而通常又著重于最壞情況。當(dāng)我們分析程序的某一局部(如一個語句，一個分程序，一個程序段，一個過程或函數(shù))時，可以用具體程序的輸入的規(guī)模N作為復(fù)雜性函數(shù)的自變量，也可以用局部的規(guī)模參數(shù)作為自變量。但是，作為最終結(jié)果的整體程序的復(fù)雜性函數(shù)只能以整體程序的輸入規(guī)模為自變量。時間復(fù)雜性漸近階的分析規(guī)則算法復(fù)雜性漸近階的分析可以對表達(dá)該規(guī)則（A）賦值、比較、算術(shù)運(yùn)算、邏輯運(yùn)算、讀寫等，只需要1個單位時間。訪問一個數(shù)組的單個分量或一個記錄的單個域，只需要1個單位時間。規(guī)則（A）賦值、比較、算術(shù)運(yùn)算、邏輯運(yùn)算、讀寫等，只需要1個規(guī)則（B）語句“ifCthenS1elseS2”只要Tc+max(Ts1，Ts2)的時間，其中Tc是計算條件表達(dá)式C需要的時間，而Ts1和Ts2分別是執(zhí)行語句S1和S2需要的時間。語句"CaseAofa1:S1;a2:S2;…;am:Sm;

end"，需要max(Ts1,Ts2，…，Tsm)的時間，其中Tsi是執(zhí)行語句Si所需要的時間，i=l,2,…,m。規(guī)則（B）語句“ifCthenS1elseS2”只規(guī)則（C）執(zhí)行一個for循環(huán)語句需要的時間等于執(zhí)行該循環(huán)體所需要的時間乘上循環(huán)的次數(shù)。執(zhí)行一個while循環(huán)語句"while"或一個"dowhile"類循環(huán)語句需要的時間等于計算條件表達(dá)式需要的時間與執(zhí)行循環(huán)S體需要的時間之和乘以循環(huán)的次數(shù)。與for循環(huán)語句不同，這里的循環(huán)次數(shù)是隱含的。規(guī)則（C）執(zhí)行一個for循環(huán)語句需要的時間等于執(zhí)行該循環(huán)體所規(guī)則（D）對goto語句。在時間復(fù)雜性分析時可以假設(shè)它不需要任何額外的時間。如果程序濫用了goto語句，即控制轉(zhuǎn)移到前面的語句，那么情況將變得復(fù)雜起來。當(dāng)這種轉(zhuǎn)移造成某種循環(huán)時，只要與別的循環(huán)不交叉，保持循環(huán)的內(nèi)外嵌套，則可以比照前面的規(guī)則進(jìn)行分析。當(dāng)由于使用goto語句而使程序結(jié)構(gòu)混亂時，建議改寫程序然后再做分析。規(guī)則（D）對goto語句。在時間復(fù)雜性分析時可以假設(shè)它不需要規(guī)則（E）對函數(shù)調(diào)用語句，它們需要的時間包括兩部分，一部分用于實現(xiàn)控制轉(zhuǎn)移，另一部分用于執(zhí)行或函數(shù)本身，這時可以根據(jù)函數(shù)調(diào)用的層次，由里向外運(yùn)用規(guī)則(A)-(D)進(jìn)行分析，直到計算出最外層的運(yùn)行時間。如果出現(xiàn)遞歸調(diào)用，我們可以對其中的各個遞歸過程，所需要的時間假設(shè)為一個相應(yīng)規(guī)模的待定函數(shù)。然后一一根據(jù)過程(或函數(shù))的內(nèi)涵建立起這些待定函數(shù)之間的遞歸關(guān)系得到遞歸方程。最后用求遞歸方程解的漸進(jìn)階的方法確定最壞情況下的復(fù)雜性的漸進(jìn)階。在出現(xiàn)遞歸調(diào)用時要考慮其中隱含的存儲空間的額外開銷。所需要的額外存儲空間的大小(即棧的規(guī)模)與遞歸調(diào)用的深度成正比，其比例因子等于每深入一層需要保存的數(shù)據(jù)量。規(guī)則（E）對函數(shù)調(diào)用語句，它們需要的時間包括兩部分，一部分用遞歸方程解的漸近階的求法遞歸方程的形式多種多樣，求其解的漸近階的方法也多種多樣。比較實用的有：代入法迭代法套用公式法差分方程法母函數(shù)法遞歸方程解的漸近階的求法遞歸方程的形式多種多樣，求其解的漸近代入法?這個方法的基本步驟是先推測遞歸方程的顯式解，然后用數(shù)學(xué)歸納法證明這一推測的正確性。那么，顯式解的漸近階即為所求。代入法?這個方法的基本步驟是先推測遞歸方程的顯式解，然后用數(shù)迭代法?這個方法的基本步驟是通過反復(fù)迭代，將遞歸方程的右端變換成一個級數(shù)，然后求級數(shù)的和，再估計和的漸近階；或者，不求級數(shù)的和而直接估計級數(shù)的漸近階，從而達(dá)到對遞歸方程解的漸近階的估計。迭代法?這個方法的基本步驟是通過反復(fù)迭代，將遞歸方程的右端變套用公式法?這個方法針對形如：T(n)=aT(n/b)+f(n)的遞歸方程，給出三種情況下方程解的漸近階的三個相應(yīng)估計公式供套用。套用公式法?這個方法針對形如：T(n)=aT(n/b差分方程法?有些遞歸方程可以看成一個差分方程，因而可以用解差分方程(初值問題)的方法來解遞歸方程。然后對得到的解作漸近階的估計。差分方程法?有些遞歸方程可以看成一個差分方程，因而可以用解差母函數(shù)法?這是一個有廣泛適用性的方法。它不僅可以用來求解線性常系數(shù)高階齊次和非齊次的遞歸方程，而且可以用來求解線性變系數(shù)高階齊次和非齊次的遞歸方程，甚至可以用來求解非線性遞歸方程。方法的基本思想是設(shè)定遞歸方程解的母函數(shù)，努力建立一個關(guān)于母函數(shù)的可解方程，將其解出，然后返回遞歸方程的解。母函數(shù)法?這是一個有廣泛適用性的方法。它不僅可以用來求解線性算法分析的內(nèi)容和意義介紹一般的算法設(shè)計策略，闡述各方法的理論基礎(chǔ)、主要思想及其適用范圍。同時針對一些具體問題來講述如何用這些一般的理論以及各種抽象數(shù)據(jù)類型對問題進(jìn)行抽象描述，并用最有效的方式設(shè)計出解決問題的高效算法。計算機(jī)程序設(shè)計方法學(xué)的理論、抽象和設(shè)計三個過程，通過對算法正確性的證明和復(fù)雜性的分析，深化對大問題的復(fù)雜性、概念和形式模型、效率和抽象的層次、折衷和結(jié)論等在計算機(jī)學(xué)科中重復(fù)出現(xiàn)的概念的理解。算法分析的內(nèi)容和意義介紹一般的算法設(shè)計策略，闡述各方法的理論第二章算法效率分析算法效率（Efficiency）算法效率有什么作用算法效率是怎樣度量的，評價算法優(yōu)劣的依據(jù)是什么怎樣完成算法算法效率分析第二章算法效率分析算法效率（Efficiency）算法的復(fù)雜性算法的復(fù)雜性是算法效率的度量，是評價算法優(yōu)劣的重要依據(jù)。一個算法的復(fù)雜性的高低體現(xiàn)在運(yùn)行該算法所需要的計算機(jī)資源的多少上面，所需的資源越多，我們就說該算法的復(fù)雜性越高；反之，所需的資源越低，則該算法的復(fù)雜性越低。計算機(jī)的資源，最重要的是時間和空間（即存儲器）資源。因而，算法的復(fù)雜性有時間復(fù)雜性和空間復(fù)雜性之分。算法的復(fù)雜性算法的復(fù)雜性是算法效率的度量，是評價算法優(yōu)劣的重算法效率有什么作用不言而喻，對于任意給定的問題，設(shè)計出復(fù)雜性盡可能低的算法是我們在設(shè)計算法的一個重要目標(biāo)；另一方面，當(dāng)給定的問題已有多種算法時，選擇其中復(fù)雜性最低者，是我們在選用算法應(yīng)遵循的一個重要準(zhǔn)則。因此，算法的復(fù)雜性分析對算法的設(shè)計或選用有著重要的指導(dǎo)意義和實用價值。算法效率有什么作用不言而喻，對于任意給定的問題，設(shè)計出復(fù)雜性問題怎樣完成算法算法效率分析？用怎樣的一個量來表達(dá)一個算法的復(fù)雜性；對于給定的一個算法，怎樣具體計算它的復(fù)雜性。問題怎樣完成算法算法效率分析？復(fù)雜性的計量（一）算法的復(fù)雜性是算法運(yùn)行所需要的計算機(jī)資源的量，需要的時間資源的量稱作時間復(fù)雜性，需要的空間（即存儲器）資源的量稱作空間復(fù)雜性。這個量應(yīng)該集中反映算法中所采用的方法的效率，而從運(yùn)行該算法的實際計算機(jī)中抽象出來。換句話說，這個量應(yīng)該是只依賴于算法要解的問題的規(guī)模、算法的輸入和算法本身的函數(shù)。如果分別用N、I和A來表示算法要解問題的規(guī)模、算法的輸入和算法本身，用C表示算法的復(fù)雜性，那么應(yīng)該有：C=F(N,I,A)復(fù)雜性的計量（一）算法的復(fù)雜性是算法運(yùn)行所需要的計算機(jī)資源的復(fù)雜性的計量（二）其中F(N,I,A)是N,I,A的一個確定的三元函數(shù)。如果把時間復(fù)雜性和空間復(fù)雜性分開，并分別用T和S來表示，那么應(yīng)該有：

T=T(N,I,A)(2.1.1)和

S=S(N,I,A)(2.1.2)通常，我們讓A隱含在復(fù)雜性函數(shù)名當(dāng)中，因而將（2.1.1）和（2.1.2）分別簡寫為：

T=T(N,I)和S=S(N,I)。由于時間復(fù)雜性和空間復(fù)雜性概念類同，計算方法相似，且空間復(fù)雜性分析相對地簡單些，所以將主要地討論時間復(fù)雜性。復(fù)雜性的計量（二）其中F(N,I,A)是N,I,A的一個確定復(fù)雜性的計量（三）根據(jù)T(N,I)的概念，它應(yīng)是算法在一臺抽象計算機(jī)上運(yùn)行所需的時間。設(shè)此抽象計算機(jī)所提供的元運(yùn)算有k種，記為O1，O2，...，Ok；再設(shè)這些元運(yùn)算每執(zhí)行一次所需要的時間分別為t1，t2，...，tk。對于給定的算法A，設(shè)經(jīng)過統(tǒng)計，用到元運(yùn)算Oi的次數(shù)分別為ei，i=1，2，...，k，很明顯，對每一個i，1<=i<=k，ei是N和I的函數(shù)，即ei=ei(N,I)。那么有：

T(N,I)=∑tiei(N,I)

(2.1.3)其中{ti|i=1,2,..,k},是與N,I無關(guān)的常數(shù)。復(fù)雜性的計量（三）根據(jù)T(N,I)的概念，它應(yīng)是算法在一臺抽復(fù)雜性的計量（四）下面只考慮三種情況的復(fù)雜性，即最壞情況、最好情況和平均情況下的時間復(fù)雜性，并分別記為Tmax(N)、Tmin(N)和Tavg(N)。在數(shù)學(xué)上有：其中，DN是規(guī)模為N的合法輸入的集合；I*是DN中一個使T(N,I*)達(dá)到Tmax(N)的合法輸入，I~是DN中一個使T(N,I~)到Tmin(N)的合法輸入；而P(I)是在算法的應(yīng)用中出現(xiàn)輸入I的概率。復(fù)雜性的計量（四）下面只考慮三種情況的復(fù)雜性，即最壞情況、最復(fù)雜性的計量（五）以上三種情況下的時間復(fù)雜性各從某一個角度來反映算法的效率，各有各的用處，也各有各的局限性。但實踐表明可操作性最好的且最有實際價值的是最壞情況下的時間復(fù)雜性。一般來說，最好情況和最壞情況的時間復(fù)雜性是很難計量的，原因是對于問題的任意確定的規(guī)模N達(dá)到了Tmax(N)的合法輸入難以確定，而規(guī)模N的每一個輸入的概率也難以預(yù)測或確定。我們有時也按平均情況計量時間復(fù)雜性，但那時在對P(I)做了一些人為的假設(shè)（比如等概率）之后才進(jìn)行的。所做的假設(shè)是否符合實際總是缺乏根據(jù)。因此，在最好情況和平均情況下的時間復(fù)雜性分析還僅僅是停留在理論上。復(fù)雜性的計量（五）以上三種情況下的時間復(fù)雜性各從某一個角度來復(fù)雜性的漸近性（一）隨著經(jīng)濟(jì)的發(fā)展、社會的進(jìn)步、科學(xué)研究的深入，要求用計算機(jī)解決的問題越來越復(fù)雜，規(guī)模越來越大。但是，如果對這類問題的算法進(jìn)行分析時，把所有的元運(yùn)算都考慮進(jìn)去，精打細(xì)算，那么，由于問題的規(guī)模很大且結(jié)構(gòu)復(fù)雜，算法分析的工作量之大、步驟之繁將令人難以承受。因此，人們提出了對于規(guī)模充分大、結(jié)構(gòu)又十分復(fù)雜的問題的求解算法，其復(fù)雜性分析應(yīng)如何簡化的問題。復(fù)雜性的漸近性（一）隨著經(jīng)濟(jì)的發(fā)展、社會的進(jìn)步、科學(xué)研究的深復(fù)雜性的漸近性（二）設(shè)T(N)是在第二段中所定義的關(guān)于算法A的復(fù)雜性函數(shù)。一般說來，當(dāng)N單調(diào)增加且趨于∞時,T(N)也將單調(diào)增加趨于∞。對于T(N)，如果存在T’(N)，使得當(dāng)N→∞時有：(T(N)-T’(N))/T(N)→0我們就說T’(N)是T(N)當(dāng)N→∞時的漸近性態(tài)，或叫T’(N)為算法A當(dāng)N→∞的漸近復(fù)雜性而與T(N)相區(qū)別，因為在數(shù)學(xué)上，T’(N)是T(N)當(dāng)N→∞時的漸近表達(dá)式。T’(N)是T(N)中略去低階項所留下的主項。所以它無疑比T(N)來得簡單。比如當(dāng)T(N)=3N2+4Nlog2N+7時，T’(N)的一個答案是3N2，顯然3N2比3N2+4Nlog2N+7簡單得多。復(fù)雜性的漸近性（二）設(shè)T(N)是在第二段中所定義的關(guān)于算法A復(fù)雜性的漸近性（三）考慮到分析算法的復(fù)雜性的目的在于比較求解同一間題的兩個不同算法的效率，而當(dāng)要比較的兩個算法的漸近復(fù)雜性的階不相同時，只要能確定出各自的階，就可以判定哪一個算法的效率高。換句話說，這時的漸近復(fù)雜性分析只要關(guān)心T’(N)的階就夠了，不必關(guān)心包含在T’(N)中的常數(shù)因子。所以，我們常常又對T’(N)的分析進(jìn)--步簡化，即假設(shè)算法中用到的所有不同的元運(yùn)算各執(zhí)行一次，所需要的時間都是一個單位時間。由此，只要考察當(dāng)問題的規(guī)模充分大時，算法復(fù)雜性在漸近意義下的階。與此簡化的復(fù)雜性分析方法相配套，需要引入五個漸近意義下的記號：Ο（奧密克戎）、Ω（歐米伽）、θ（西塔）、ο和ω。復(fù)雜性的漸近性（三）考慮到分析算法的復(fù)雜性的目的在于比較求解復(fù)雜性的漸近性（四）設(shè)f(N)和g(N)是定義在正數(shù)集上的正函數(shù)。如果存在正的常數(shù)C和自然數(shù)N0，使得當(dāng)N≥N0時有f(N)≤Cg(N)。則稱函數(shù)f(N)當(dāng)N充分大時上有界，且g(N)是它的一個上界，記為f(N)=Ο(g(N))。這時我們還說f(N)的階不高于g(N)的階。根據(jù)記號Ο的定義，用它評估算法的復(fù)雜性，得到的只是當(dāng)規(guī)模充分大時的一個上界。這個上界的階越低則評估就越精確，結(jié)果就越有價值。復(fù)雜性的漸近性（四）設(shè)f(N)和g(N)是定義在正數(shù)集上的正復(fù)雜性的漸近性（五）按照大Ο的定義，容易證明它有如下運(yùn)算規(guī)則：Ο(f)+Ο(g)=Ο(max(f,g))；Ο(f)+Ο(g)=Ο(f+g)；Ο(f)·Ο(g)=Ο(f·g)；如果g(N)=Ο(f(N))，則Ο(f)+Ο(g)=Ο(f)；Ο(Cf(N))=Ο(f(N))，其中C是一個正的常數(shù)；f=Ο(f)；復(fù)雜性的漸近性（五）按照大Ο的定義，容易證明它有如下運(yùn)算規(guī)則復(fù)雜性的漸近性（六）估計下面二重循環(huán)算法段在最壞情況下的時間復(fù)雜性T(N)的階。

for(i=l;i<N;i++)for(j=l;j<N;j++){S1;S2;S3;S4;}其中Sk(k=1,2,3,4)是單一的賦值語句。對于內(nèi)循環(huán)體，顯然只需Ο(l)時間。因而內(nèi)循環(huán)只需時間。累加起來便是外循環(huán)的時間復(fù)雜性：

復(fù)雜性的漸近性（六）估計下面二重循環(huán)算法段在最壞情況下的時間復(fù)雜性的漸近性（七）記號Ω，定義如下：如果存在正的常數(shù)C和自然數(shù)N0，使得當(dāng)N≥N0時有f(N)≥Cg(N)，則稱函數(shù)f(N)當(dāng)N充分大時下有界，且g(N)是它的一個下界，記為f(N)=Ω(g(N))。這時我們還說f(N)的階不低于g(N)的階。復(fù)雜性的漸近性（七）記號Ω，定義如下：如果存在正的常數(shù)C和自復(fù)雜性的漸近性（八）Ω的這個定義的優(yōu)點是與Ο的定義對稱，缺點是當(dāng)f(N)對自然數(shù)的不同無窮子集有不同的表達(dá)式，且有不同的階時，未能很好地刻畫出f(N)的下界。比如當(dāng)：時，如果按上述定義，只能得到f(N)=Ω(1)，這是一個平凡的下界，對算法分析沒有什么價值。復(fù)雜性的漸近性（八）Ω的這個定義的優(yōu)點是與Ο的定義對稱，缺點復(fù)雜性的漸近性（九）用Ω評估算法的復(fù)雜性，得到的只是該復(fù)雜性的一個下界。這個下界的階越高，則評估就越精確，結(jié)果就越有價值。對于一個問題和任意給定的充分大的規(guī)模N，下界在該問題的所有算法或某類算法的復(fù)雜性中取，那么它將更有意義。這時得到的相應(yīng)下界，我們稱之為問題的下界或某類算法的下界。它常與Ο配合證明問題的某個特定算法是該問題的最優(yōu)算法或是在某算法類中的最優(yōu)算法。復(fù)雜性的漸近性（九）用Ω評估算法的復(fù)雜性，得到的只是該復(fù)雜性復(fù)雜性的漸近性（十）定義f(N)=θ(g(N))，有f(N)=Ο(g(N))且f(N)=Ω(g(N))。這時，我們說f(N)與g(N)同階。對于任意給定的ε≥0，都存在非負(fù)整數(shù)N0，使得當(dāng)N≥N0時有f(N)≤εg(N)，則稱函數(shù)f(N)當(dāng)N充分大時比g(N)低階，記為f(N)=o(g(N))，例如：4NlogN+7=o(3N2+4NlogN+7)；f(N)=ω(g(N))定義為g(N)=o(f(N))。即當(dāng)N充分大時f(N)的階比g(N)高。我們看到Ο對于O有如ω對于Ω。復(fù)雜性的漸近性（十）定義f(N)=θ(g(N))，有f(N)復(fù)雜性的漸近性（十一）以下表述雖不很精確，但可幫助記憶：

f

=

Ο(g)

?

f≤g

f

=

Ω(g)

?

f≥g

f

=

θ

(g)

?

f=g

f

=

o

(g)

?

f<g

f

=

ω

(g)

?

f>g復(fù)雜性的漸近性（十一）以下表述雖不很精確，但可幫助記憶：

復(fù)雜性漸近階的重要性（一）隨著計算機(jī)的設(shè)計和制造技術(shù)的突飛猛進(jìn)，計算機(jī)的計算速度和存儲容量在直線增長。有人從而認(rèn)為不必要再去苦苦地追求高效算法，不必去無謂地進(jìn)行復(fù)雜性的分析。以為低效的算法可以由高速的計算機(jī)來彌補(bǔ)。但實際上，計算機(jī)解決的問題復(fù)雜程度和規(guī)模的線性增長，對低效算法來說，導(dǎo)致的時耗和空間需求是以幾何的方式增長的，計算機(jī)速度和容量的需求將入不付出。復(fù)雜性漸近階的重要性（一）隨著計算機(jī)的設(shè)計和制造技術(shù)的突飛猛算法與漸近階的關(guān)系（一）設(shè)A1,A2,…和A6，它們的漸近時間復(fù)雜性分別為N，NlogN，N2，N3，2N，N!，是求解同一間題的6種不同的算法，這六種算法分別在C1和C2兩臺計算機(jī)上運(yùn)行，設(shè)計算機(jī)C2的計算速度是計算機(jī)C1的10倍。在可接受的一段時間內(nèi)，設(shè)在C1上算法Ai可能求解的問題的規(guī)模為N1i，而在C2上可能求解的問題的規(guī)模為N2i，那么，我們就應(yīng)該有Ti(N2i)=10Ti(N1i)，其中Ti(N)是算法Ai漸近的時間復(fù)雜性，i=1,2,…,6。分別解出N2i和N1i的關(guān)系，可列成下表。算法與漸近階的關(guān)系（一）設(shè)A1,A2,…和A6，它們的漸近時表2-1表2-1算法與漸近階的關(guān)系（二）從表2-1可以清楚地看到，對于低效的算法，計算速度增長基本上不帶來求解規(guī)模的增益。對表的最后一列觀察發(fā)現(xiàn)，限制求解問題規(guī)模的關(guān)鍵因素是算法漸近復(fù)雜性的階。可見，算法的漸近復(fù)雜性的階對于算法的效率有著決定性的意義。所以在討論算法的復(fù)雜性時基本上都只關(guān)心它的漸近階。多項式算法是有效的算法。絕大多數(shù)的問題都有多項式算法。但也有一些問題還未找到多項式算法，只找到指數(shù)型算法。算法與漸近階的關(guān)系（二）從表2-1可以清楚地看到，對于低效的算法與漸近階的關(guān)系（三）“復(fù)雜性的漸近階比較低的算法比復(fù)雜性的漸近階比較高的算法有效”這個結(jié)論，只是在問題的求解規(guī)模充分大時才成立。比如算法A4比A5有效只是在N3<2N，即N≥c時才成立。其中c是方程N(yùn)3=2N的解。當(dāng)N<c時，A5反而比A4有效。所以對于規(guī)模小的問題，不要盲目地選用復(fù)雜性階比較低的算法。其原因一方面是如上所說，復(fù)雜性階比較低的算法在規(guī)模小時不一定比復(fù)雜性階比較高的算法更有效；另方面，在規(guī)模小時，決定工作效率的可能不是算法的效率而是算法的簡單性，哪一種算法簡單，實現(xiàn)起來快，就選用那一種算法。算法與漸近階的關(guān)系（三）“復(fù)雜性的漸近階比較低的算法比復(fù)雜性算法與漸近階的關(guān)系（四）當(dāng)要比較的兩個算法的漸近復(fù)雜性的階相同時，必須進(jìn)一步考察漸近復(fù)雜性表達(dá)式中常數(shù)因子才能判別它們誰好誰差。顯然常數(shù)因子小的優(yōu)于常數(shù)因子大的算法。比如漸近復(fù)雜性為N1ogN/l00的算法顯然比漸近復(fù)雜性為l00NlogN的算法來得有效。算法與漸近階的關(guān)系（四）當(dāng)要比較的兩個算法的漸近復(fù)雜性的階相算法復(fù)雜性漸近階的分析算法復(fù)雜性漸近階的分析可以對表達(dá)該算法的程序的復(fù)雜性漸近階的分析來代替。對于算法的復(fù)雜性，我們只考慮最壞、最好和平均三種情況，而通常又著重于最壞情況?，F(xiàn)限于最壞情況分析。當(dāng)我們分析程序的某一局部(如一個語句，一個分程序，一個程序段，一個過程或函數(shù))時，可以用具體程序的輸入的規(guī)模N作為復(fù)雜性函數(shù)的自變量，也可以用局部的規(guī)模參數(shù)作為自變量。但作為最終結(jié)果的整體程序的復(fù)雜性函數(shù)只能以整體程序的輸入規(guī)模為自變量。算法復(fù)雜性漸近階的分析算法復(fù)雜性漸近階的分析可以對表達(dá)該算法時間復(fù)雜性漸近階的分析規(guī)則算法復(fù)雜性漸近階的分析可以對表達(dá)該算法的程序的復(fù)雜性漸近階的分析來代替。對于算法的復(fù)雜性，我們只考慮最壞、最好和平均三種情況，而通常又著重于最壞情況。當(dāng)我們分析程序的某一局部(如一個語句，一個分程序，一個程序段，一個過程或函數(shù))時，可以用具體程序的輸入的規(guī)模N作為復(fù)雜性函數(shù)的自變量，也可以用局部的規(guī)模參數(shù)作為自變量。但是，作為最終結(jié)果的整體程序的復(fù)雜性函數(shù)只能以整體程序的輸入規(guī)模為自變量。時間復(fù)雜性漸近階的分析規(guī)則算法復(fù)雜性漸近階的分析可以對表達(dá)該規(guī)則（A）賦值、比較、算術(shù)運(yùn)算、邏輯運(yùn)算、讀寫等，只需要1個單位時間。訪問一個數(shù)組的單個分量或一個記錄的單個域，只需要1個單位時間。規(guī)則（A）賦值、比較、算術(shù)運(yùn)算、邏輯運(yùn)算、讀寫等，只需要1個規(guī)則（B）語句“ifCthenS1elseS2”只要Tc+max(Ts1，Ts2)的時間，其中Tc是計算條件表達(dá)式C需要的時間，而Ts1和Ts2分別是執(zhí)行語句S1和S2需要的時間。語句"CaseAofa1:S1;a2:S2;…;am:Sm;

end"，需要max(Ts1,Ts2，…，Tsm)的時間，其中Ts