二講算法復雜度篇

算法復雜度曾華琳1算法復雜性分析算法復雜性=算法所需要的計算機資源C=F(N,I,A) 問題的規(guī)模、算法的輸入、算法本身算法的時間復雜性T(n)；算法的空間復雜性S(n)。其中n是問題的規(guī)模（輸入大?。?。需要對算法復雜度進行具體化，簡化。2算法的時間復雜性（1）最壞情況下的時間復雜性

Tmax(n)=max{T(I)|size(I)=n}（2）最好情況下的時間復雜性

Tmin(n)=min{T(I)|size(I)=n}（3）平均情況下的時間復雜性

Tavg(n)=

其中I是問題的規(guī)模為n的實例，p(I)是實例I出現(xiàn)的概率。3算法漸近復雜性T(n)

,asn

;(T(n)-t(n))/T(n)0

，asn;t(n)是T(n)的漸近性態(tài)，為算法的漸近復雜性。在數(shù)學上，t(n)是T(n)的漸近表達式，是T(n)略去低階項留下的主項。它比T(n)簡單。引入漸近符號，以便表示算法的運行時間與輸入規(guī)模之間的主要關(guān)系，即漸近時間復雜性，來衡量算法的好壞。4漸近記號，O，5漸近分析的記號在下面的討論中，對所有n，f(n)

0，g(n)

0。

=代表屬于（1）緊漸近界記號

(g(n))={f(n)|存在正常數(shù)c1,c2和n0使得對所有n

n0有：c1g(n)

f(n)

c2g(n)} f(n)=3n+3, 3n+3≤3n+n=4nforn≥3, 3n+3≥3nforn≥0,

f(n)=Θ(n).67

定理1：

(g(n))=O(g(n))

(g(n))兩個函數(shù)f(n)和g(n)同階，即高階項的增長次數(shù)相同在下面的討論中，對所有n，f(n)

0，g(n)

0。（2）漸近上界記號O O(g(n))={f(n)|存在正常數(shù)c和n0使得對所有n

n0有：0

f(n)

cg(n)}8漸近分析的記號9漸近上界記號O

103n=O(n)3n<=4nn=O(n)n<=1025n,n>=n03n2+5n+3=O(n2)3n2+5n+3<=11n2n2=O(n3)n3<>O(n2)若A(n)=│am│nm+…+│a1│n+│a0│

是一個m次多項式,則A(n)=O(nm)證明:

取n0=1,當n>=n0時,利用A(n)的定義和一個簡單的不等式,有

A(n)<=│am│nm+…+│a1│n+│a0│ <=(│am│+│am-1│/n+…+│a0│/nm)nm <=(│am│+…+│a0│)nm選取c=│am│+…+│a0│，得證。1112（3）漸近下界記號

(g(n))={f(n)|存在正常數(shù)c和n0使得對所有n

n0有：0

cg(n)

f(n)}13漸近分析的記號14漸近下界記號

1516實際中，通常根據(jù)漸近上界和漸近下界來證明漸近緊界，而不是根據(jù)漸近緊界來得到漸近上界和漸近下界）定理:對于任意給定的函數(shù)f(n),g(n)，f(n)=Θ(g(n))

當且僅當f(n)=O(g(n))且f(n)=Ω(g(n))。Writef(n)=O(g(n))toindicatethatafunctionf(n)isamemberofthesetO(g(n)).

f(n)=Θ(g(n))意味著

f(n)=O(g(n))O記號是用來表示上界的，當用它作為算法的最壞情況運行時間的上界時，就有對任意輸入的運行時間的上界。17若f(n)=O(g(n))且g(n)=O(f(n)),則f,g具有相同的增長率

若f(n)=O(g(n))且g(n)<>O(f(n)),則稱g(n)比f(n)增長得快18關(guān)于O的延伸理解O是一種機制，對給定的一個算法，找出其時間、空間上限的機制，而不是此算法寫成程序后所需的具體時間。O是一種增長趨勢，不依賴于某一臺機器，是計算時間的漸進表示。算法計算時間的數(shù)量級若算法A中有順序的數(shù)量級分別為，，…， 共k個運算，則A的數(shù)量級為 取，等于19（4）非緊上界記號o

o(g(n))={f(n)|對于任何正常數(shù)c>0，存在正數(shù)和n0>0使得對所有n

n0有：0

f(n)<cg(n)}

等價于

f(n)/g(n)0

，asn

。（5）非緊下界記號

(g(n))={f(n)|對于任何正常數(shù)c>0，存在正數(shù)和n0>0使得對所有n

n0有：0

cg(n)

<f(n)}

等價于

f(n)/g(n)

，asn

。

f(n)

(g(n))

g(n)

o(f(n))20漸近分析記號在等式和不等式中的意義f(n)=

(g(n))的確切意義是：f(n)

(g(n))。一般情況下，等式和不等式中的漸近記號

(g(n))表示

(g(n))中的某個函數(shù)。例如：2n2+3n+1=2n2+

(n)表示

2n2+3n+1=2n2+f(n)，其中f(n)是

(n)中某個函數(shù)。等式和不等式中漸近記號O,o,

和

的意義是類似的。21漸近分析中函數(shù)比較（類比實數(shù)集）f(n)=O(g(n))

ab; f(n)=

(g(n))

ab;f(n)=

(g(n))

a=b;f(n)=o(g(n))

a<b;f(n)=

(g(n))

a>b.實數(shù)集的三分性不能類比：對于兩個實數(shù)a和b，下列三種情況恰有一種成立：a<b,a=b,a>b例，函數(shù)和22漸近分析記號的若干性質(zhì)（1）傳遞性：f(n)=

(g(n))，g(n)=

(h(n))

f(n)=

(h(n))；f(n)=O(g(n))，g(n)=O

(h(n))

f(n)=O

(h(n))；f(n)=

(g(n))，g(n)=

(h(n))

f(n)=

(h(n))；f(n)=o(g(n))，g(n)=o(h(n))

f(n)=o(h(n))；f(n)=

(g(n))，g(n)=

(h(n))

f(n)=

(h(n))；23（2）反身性：f(n)=

(f(n))；f(n)=O(f(n))；f(n)=

(f(n)).（3）對稱性：f(n)=

(g(n))

g(n)=

(f(n)).（4）互對稱性：f(n)=O(g(n))

g(n)=

(f(n))；f(n)=o(g(n))

g(n)=

(f(n))；24（5）算術(shù)運算：O(f(n))+O(g(n))=

O(max{f(n),g(n)})；O(f(n))+O(g(n))=

O(f(n)+g(n))；O(f(n))*O(g(n))=

O(f(n)*g(n))；O(cf(n))=

O(f(n))；g(n)=O(f(n))

O(f(n))+O(g(n))=

O(f(n))。25規(guī)則O(f(n))+O(g(n))=

O(max{f(n),g(n)})的證明：對于任意f1(n)

O(f(n))，存在正常數(shù)c1和自然數(shù)n1，使得對所有n

n1，有f1(n)

c1f(n)。類似地，對于任意g1(n)

O(g(n))，存在正常數(shù)c2和自然數(shù)n2，使得對所有n

n2，有g(shù)1(n)

c2g(n)。令c3=max{c1,c2}，n3=max{n1,n2}，h(n)=max{f(n),g(n)}。則對所有的n

n3，有f1(n)+g1(n)

c1f(n)+c2g(n)

c3f(n)+c3g(n)=c3(f(n)+g(n))

c32max{f(n),g(n)}=2c3h(n)=O(max{f(n),g(n)}).26算法漸近復雜性分析中常用函數(shù)（1）單調(diào)函數(shù)單調(diào)遞增：m

n

f(m)

f(n);單調(diào)遞減：m

n

f(m)

f(n);嚴格單調(diào)遞增：m

<n

f(m)<f(n);嚴格單調(diào)遞減：m

<n

f(m)>f(n).（2）取整函數(shù)

x

：不大于x的最大整數(shù)；

x

：不小于x的最小整數(shù)。27取整函數(shù)的若干性質(zhì)

x-1<x

x

x<x+1；

n/2

+n/2=n;

對于n

0，a,b>0，有：

n/a/b=n/ab;

n/a/b=n/ab;

a/b(a+(b-1))/b;

a/b(a-(b-1))/b;

f(x)=x,g(x)=x

為單調(diào)遞增函數(shù)。28（3）多項式函數(shù)

p(n)=a0+a1n+a2n2+…+adnd；ad>0;

p(n)=

(nd);

f(n)=O(nk)

f(n)多項式有界；

f(n)=O(1)

f(n)

c;

k

d

p(n)=O(nk);k

d

p(n)=

(nk);k>

d

p(n)=o(nk);k<d

p(n)=

(nk).29（4）指數(shù)函數(shù)對于正整數(shù)m,n和實數(shù)a>0:a0=1;

a1=a;

a-1=1/a;(am)n=amn;

(am)n=(an)m;

aman=

am+n;

a>1

an為單調(diào)遞增函數(shù);a>1

nb=o(an)30ex

1+x;|x|11+x

ex

1+x+x2;

ex

=1+x+(x2),asx0;31（5）對數(shù)函數(shù)

logn=log2n;

lgn=log10n;

lnn=logen;

logkn=(logn)kl;loglogn=log(logn);fora>0,b>0,c>03233|x|1forx>-1,foranya>0,,logbn=o(na)34（6）階層函數(shù)Stirling’sapproximation

3536算法分析中常見的復雜性函數(shù)37小規(guī)模數(shù)據(jù)38中等規(guī)模數(shù)據(jù)3940example41例，L(1:n)是一張表，x是輸入，若x∈L，就輸出x在表中位置；若x∈L，則輸出信息。以比較基礎(chǔ)的算法算法AA1.輸入L，n，x；A2.j<-1;A3.當j<=n且x<>L(j)時做j<-j+1;A4.若j>n，則j<-0;A5.輸出j.分析：最好情況：O(1)最差情況：平均性態(tài)：42設(shè)的概率為q，為對任意j<i,,為當輸入為時，再設(shè)x∈L中每個位置上的概率是一樣的，q/n最壞情況：x=L(n)n次

x<>Ln次A1.輸入L，n，x；A2.j<-1;A3.當j<=n且x<>L(j)時做j<-j+1;A4.若j>n，則j<-0;A5.輸出j.算法分析方法例：順序搜索算法44template<classType>intseqSearch(Type*a,intn,Typek){for(inti=0;i<n;i++) if(a[i]==k)returni;return-1;}（1）Tmax(n)=max{T(I)|size(I)=n}=O(n)（2）Tmin(n)=min{T(I)|size(I)=n}=O(1)（3）在平均情況下，假設(shè)：

(a)搜索成功的概率為p(0

p

1)；

(b)在數(shù)組的每個位置i(0

i<n)搜索成功的概率相同，均為p/n。45算法分析的基本法則非遞歸算法：（1）for/while循環(huán)循環(huán)體內(nèi)計算時間*循環(huán)次數(shù)；（2）嵌套循環(huán)循環(huán)體內(nèi)計算時間*所有循環(huán)次數(shù)；（3）順序語句各語句計算時間相加；（4）if-else語句if語句計算時間和else語句計算時間的較大者。4647template<classType>voidinsertion_sort(Type*a,intn){Typekey;//costtimesfor(inti=1;i<n;i++){//c1n

key=a[i];//c2n-1

intj=i-1;