1、復雜性的漸近性態(tài)及其階隨著經(jīng)濟的發(fā)展、社會的進步、科學研究的深入，要求用計算機解決的問題越來越復 雜，規(guī)模越來越大。但是，如果對這類問題的算法進行分析用的是第二段所提供的方法，把 所有的元運算都考慮進去，精打細算，那么，由于問題的規(guī)模很大且結(jié)構復雜，算法分析的 工作量之大、步驟之繁將令人難以承受。因此，人們提出了對于規(guī)模充分大、結(jié)構又十分復 雜的問題的求解算法，其復雜性分析應如何簡化的問題。我們先要引入復雜性漸近性態(tài)的概念。設丁(N)是在第二段中所定義的關于算法A的復 雜性函數(shù)。一般說來，當N單調(diào)增加且趨于8時,T(N)也將單調(diào)增加趨于“對于T(N)，如 果存在尸(N)，使得當N-8時有：(T

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

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

4、下的記號：0、G、。、o和3。以下設f(N)和g(N)是定義在正數(shù)集上的正函數(shù)。如果存在正的常數(shù)C和自然數(shù)珞，使得當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)當N充分大時下 有界，且g(N)是它的一個下界，記為f(N)=c(g(N)。這時我們還說f(N)的階不低于g(N)的 階。Q的這

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

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