漸進(jìn)復(fù)雜性第九章算法設(shè)計(jì)與

第九章算法設(shè)計(jì)與分析本章學(xué)習(xí)的主要內(nèi)容第9.1節(jié)

漸進(jìn)復(fù)雜性第9.2節(jié)分治法

第9.3節(jié)貪心法第9.4節(jié)動(dòng)態(tài)規(guī)劃法第9.5節(jié)回溯法第9.5節(jié)分支限界法第9.1節(jié)漸進(jìn)復(fù)雜性假設(shè)T(n)是算法A的復(fù)雜性函數(shù)。通常T(n)有比較多的項(xiàng)，例如：T(n)=3n2+nlog(n)+7人們希望將T(n)簡化，提出了漸進(jìn)復(fù)雜性的概念。漸進(jìn)意義下的記號O漸進(jìn)的定義(上界)漸進(jìn)的定義(下界)漸進(jìn)的定義o漸進(jìn)的定義如何確定兩個(gè)函數(shù)之間的關(guān)系常見的算法時(shí)間復(fù)雜度O漸進(jìn)的定義(上界)如果存在正的常數(shù)C和自然數(shù)N0，使得當(dāng)NN0時(shí)有f(N)C.g(N)，則稱函數(shù)f(N)當(dāng)N充分大時(shí)有上界，且g(N)是它的一個(gè)上界,記為f(N)＝O(g(N))。例如：

(1)f(N)=2N2+11N-10,g(N)=N2

常數(shù)C=3，N0=11，當(dāng)N>N0,f(N)3g(N),因此2N2+11N-10=O(N2)可以理解為：f(N)的上界是N2級別的。

(2)f(N)=N-1,f(N)=O(N)可以理解為：f(N)的上界是N級別的。O的性質(zhì)(1)O(f)+O(g)=O(max(f,g))(2)O(f)+O(g)=O(f+g)(3)O(f)O(g)=O(f.g)(4)如果g(N)=O(f(N))，則O(f)+O(g)=O(f)(5)O(C.f(N))=O(f(N))，C是一個(gè)正常數(shù)(6)f(N)=O(f)性質(zhì)(2)O(f)+O(g)=O(f+g)的證明證明：設(shè)F(N)=O(f)，G(N)=O(g)，則根據(jù)O的定義有:存在常數(shù)C1和自然數(shù)N1，使得當(dāng)NN1，有F(N)C1.f(N)存在常數(shù)C2和自然數(shù)N2，使得當(dāng)NN2，有G(N)C2.g(N)令C3=max{C1,C2},F(N)C1.f(N)C3.f(N)G(N)C2.g(N)C3.g(N)當(dāng)Nmax{N1,N2},F(N)+G(N)C3.(f(N)+g(N))F(N)+G(N)=O(f+g),即O(f)+O(g)=O(f+g)返回漸進(jìn)的定義(下界)如果存在正的常數(shù)C和自然數(shù)N0，使得當(dāng)NN0時(shí)有f(N)C.g(N)，則稱函數(shù)f(N)當(dāng)N充分大時(shí)有下界，且g(N)是它的一個(gè)下界，記為f(N)＝(g(N))。例如：f(N)=2N2+11N-10g(N)=N2,f(N)=(g(N))=(N2)

常數(shù)C=1，N0=1，當(dāng)N>N0,f(N)c.g(N),因此2N2+11N-10=(N2)返回漸進(jìn)的定義f(N)=(g(N))當(dāng)且僅當(dāng)f(N)=O(g(N))且f(N)=(g(N))，我們稱f(N)與g(N)同階。例如：2N2+11N-10=(N2)返回o漸進(jìn)的定義如果對于任意給定的>0，都存在N0，使得當(dāng)NN0時(shí)有f(N)/g(N)<，則稱函數(shù)f(N)當(dāng)N充分大時(shí)的階比g(N)低，記f(N)=o(g(N))例如：2N2+11N-10=o(N3)當(dāng)N>100,2N2+11N-103N2任意給定的>0,當(dāng)N>3/，有3N2<.N3取N0=max(100,3/+1),當(dāng)NN0,2N2+11N-10<3N2<.N3返回如何確定兩個(gè)函數(shù)之間的關(guān)系對于下列各組函數(shù)f(n)和g(n)，確定

f（n）=O(g(n))或

f（n）=Ω(g(n))或

f（n）=θ(g(n))并簡述理由。（1）f（n）=log(n2)

；

g（n）=log(n)+5（2） f（n）=log(n2)

；

g（n）=n1/2（3） f（n）=n；g（n）=log2n（1）f（n）=宴lo膊g(廟n2)；g（n）=l福og個(gè)(n懼)+慌5（2）f（n）=