復(fù)雜性的漸近性態(tài)及其階

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

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

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

4、下的記號(hào)：0、G、。、o和3。以下設(shè)f(N)和g(N)是定義在正數(shù)集上的正函數(shù)。如果存在正的常數(shù)C和自然數(shù)珞，使得當(dāng)NN0時(shí)有f(N)1有3N1 時(shí)有 N+102410 時(shí)有 2N 2+11N -101有N2N0 時(shí)有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時(shí)有f(N)Cg(N)，則稱函數(shù)f(N)當(dāng)N充分大時(shí)下 有界，且g(N)是它的一個(gè)下界，記為f(N)=c(g(N)。這時(shí)我們還說(shuō)f(N)的階不低于g(N)的 階。Q的這

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

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