1、復(fù)雜性的漸近性態(tài)及其階隨著經(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ù)雜性漸近性態(tài)的概念。設(shè)丁(N)是在第二段中所定義的關(guān)于算法A的復(fù) 雜性函數(shù)。一般說來，當(dāng)N單調(diào)增加且趨于8時,T(N)也將單調(diào)增加趨于“對于T(N)，如 果存在尸(N)，使得當(dāng)N-8時有：(T

2、(N )-T,(N )/T(N) 0那么，我們就說廠(N)是T(N)當(dāng)NT”時的漸近性態(tài)，或叫T(N)為算法A當(dāng)N-8的漸近復(fù) 雜性而與T(N)相區(qū)別，因為在數(shù)學(xué)上，尸(N)是T(N)當(dāng)NT”時的漸近表達(dá)式。直觀上，T(N)是T(N)中略去低階項所留下的主項。所以它無疑比T(N)來得簡單。比如 當(dāng)T(N)=3N 2+4Nlog2N +7時，廠(N)的一個答案是3N2，因為這時有：顯然3N 2比3N 2 +4Nlog2N +7簡單得多。由于當(dāng)NT”時T(N)漸近于廠(N)，我們有理由用廠(N)來替代T(N)作為算法A在Nt” 時的復(fù)雜性的度量。而且由于于廠(N)明顯地比T(N)簡單，這種替代明顯

3、地是對復(fù)雜性分析 的一種簡化。進(jìn)一步，考慮到分析算法的復(fù)雜性的目的在于比較求解同一間題的兩個不同算法的效 率，而當(dāng)要比較的兩個算法的漸近復(fù)雜性的階不相同時，只要能確定出各自的階，就可以判 定哪一個算法的效率高。換句話說，這時的漸近復(fù)雜性分析只要關(guān)心廠(川)的階就夠了，不 必關(guān)心包含在廠(N)中的常數(shù)因子。所以，我們常常又對廠(N)的分析進(jìn)-步簡化，即假設(shè)算 法中用到的所有不同的元運(yùn)算各執(zhí)行一次，所需要的時間都是一個單位時間。綜上所述，我們已經(jīng)給出了簡化算法復(fù)雜性分析的方法和步驟，即只要考察當(dāng)問題的 規(guī)模充分大時，算法復(fù)雜性在漸近意義下的階。與此簡化的復(fù)雜性分析方法相配套，需要引 入五個漸近意義

4、下的記號：0、G、。、o和3。以下設(shè)f(N)和g(N)是定義在正數(shù)集上的正函數(shù)。如果存在正的常數(shù)C和自然數(shù)珞，使得當(dāng)NN0時有f(N)1有3N1 時有 N+102410 時有 2N 2+11N -101有N2N0 時有N3C N2,即NN1， 有F(N)N2 有 G(N)N3有：F(N)C1 f(N)C1 h(N)C3h(N)類似地，有：G(N)C2g(N)C2h(N)C3h(N)因而O(f)+O(g) =F(N)+G(N)N0時有f(N)Cg(N)，則稱函數(shù)f(N)當(dāng)N充分大時下 有界，且g(N)是它的一個下界，記為f(N)=c(g(N)。這時我們還說f(N)的階不低于g(N)的 階。Q的這

5、個定義的優(yōu)點是與0的定義對稱，缺點是當(dāng)/(對自然數(shù)的不同無窮子集有不 同的表達(dá)式，且有不同的階時，未能很好地刻畫出f(N)的下界。比如當(dāng)：11006泌困為正偶數(shù)泌正奇數(shù)時，如果按上述定義 值。只能得到f(N)=Q(1)，這是一個平凡的下界，對算法分析沒有什么價然而，考慮到。的上述定義有與0的定義的對稱性，又考慮到常用的算法都沒出現(xiàn)上 例中那種情況，所以本文還是選用它。我們同樣也可以列舉Q的一些運(yùn)算規(guī)則。但這里從略，只提供一個應(yīng)用的例子。還是 考慮算法Search在最壞情況下的時間復(fù)雜性函數(shù)Tmax(m)。由它的表達(dá)式(2.7)及已知a,s,t 均為大于0的常數(shù)，可推得，當(dāng)m1時有：XTmax(

6、m)(m+1)a+(2m+V)tma+2mt=(a+2t)m，于是 T(m)=Q(m)omax我們同樣要指出，用。評估算法的復(fù)雜性，得到的只是該復(fù)雜性的一個下界。這個下 界的階越高，則評估就越精確，結(jié)果就越有價值。再則，這里的Q只對問題的一個算法而 言。如果它是對一個問題的所有算法或某類算法而言，即對于一個問題和任意給定的充分大 的規(guī)模N，下界在該問題的所有算法或某類算法的復(fù)雜性中取，那么它將更有意義。這時得 到的相應(yīng)下界，我們稱之為問題的下界或某類算法的下界。它常常與0配合以證明某問題 的一個特定算法是該問題的最優(yōu)算法或該問題在某算法類中的最優(yōu)算法。明白了記號0和Q之后，記號3將隨之清楚，因為我們定義f(N)=Q(g(N)則f(N)=0(g(N) 且f(N)=Q(g(N)o這時，我們說f(N)與g(N)同階。比如，對于算法Search在最壞情況下的 時間復(fù)雜性 Tmax(m)o 已有 Tmax(m)=0(m)和 Tmax(m)=Q(m)，所以有 Tmax(m)=6(m)，這是對 Tmax(m)的階的精確估計。最后，如果對于任意給定的形0,都存在非負(fù)整數(shù)珞，使得當(dāng)NN0時有f(N)eg(N), 則稱函數(shù)f(N)當(dāng)N充分大時比g(N)低階，記