算法設(shè)計(jì)與分析 ch2 學(xué)習(xí)課件

海量數(shù)據(jù)計(jì)算研究中心MassiveDataComputingLab@HIT算法設(shè)計(jì)與分析第二章算法分析的數(shù)學(xué)基礎(chǔ)哈爾濱工業(yè)大學(xué)王宏志wangzh@/pages/wang/請(qǐng)各位評(píng)審老師提出寶貴建議！謝謝！本講內(nèi)容22.1計(jì)算復(fù)雜性函數(shù)的階

2.2和式的估計(jì)與界限2.3遞歸方程3增長(zhǎng)的階如何描述算法的效率？增長(zhǎng)率忽略低階項(xiàng)，保留最高階項(xiàng)忽略常系數(shù)利用(n2)表示插入排序的最壞運(yùn)行時(shí)間(1),(lgn),(n),(n),(nlgn),(n2),(n3),(2n),(n!)4增長(zhǎng)函數(shù)漸進(jìn)效率:輸入規(guī)模非常大忽略低階項(xiàng)和常系數(shù)只考慮最高階(增長(zhǎng)的階)典型的增長(zhǎng)階:(1),(lgn),(n),(n),(nlgn),(n2),(n3),(2n),(n!)增長(zhǎng)的記號(hào):O,,,o,.同階函數(shù)集合

(g(n))={f(n)|c1,c2>0,n0,n>n0,c1g(n)f(n)c2g(n)}稱為與g(n)同階的函數(shù)集合。

如果f(n)∈(g(n))，g(n)與f(n)同階f(n)∈(g(n))，記作f(n)=(g(n))f(n)=(

g(n))nn0c1g(n)c2g(n)f(n)6(g(n))函數(shù)的例子證明1/2n2–3n=(n2).c1n2

1/2n2–3n

c2n2c1

1/2–3/n

c2對(duì)于任意n1,c2?,且對(duì)于任意n7，c1

1/14因此

c1

=1/14,c2=?,n0

=7.證明6n3

(n2).如果存在c1、c2>0，n0使得當(dāng)n

n0時(shí)，c1n2

6n3

c2n2。當(dāng)n>c2/6時(shí)，n

c2/6，矛盾。(g(n))函數(shù)的例子通常f(n)=an2+bn+c=(n2),其中a,b,c是常數(shù)且

a>0.p(n)=

i=0daini,其中ai是常數(shù)且ad>0.p(n)=(nd).(n0)或者(1),常數(shù)時(shí)間復(fù)雜性.8低階函數(shù)集合對(duì)于給定的函數(shù)g(n),O(g(n))={f(n):存在正常數(shù)c和n0

滿足對(duì)于所有n

n0，0

f(n)

cg(n)}記作f(n)

O(

g(n)),或簡(jiǎn)記為f(n)=O(

g(n)).f(n)=O(

g(n))nn0cg(n)f(n)9(g(n))和O(g(n))的關(guān)系f(n)=(

g(n))

f(n)=O(

g(n))

標(biāo)記強(qiáng)于O標(biāo)記.(

g(n))

O(

g(n))an2+bn+c=(n2),且=O(n2)an+b=O(n2).為什么？n=O(n2)!!!O標(biāo)記,表示漸進(jìn)上界

標(biāo)記,表示漸進(jìn)緊界一些討論:當(dāng)我們談到插入排序的最壞運(yùn)行時(shí)間是O(n2),這個(gè)結(jié)論適用于所有的輸入，即使對(duì)于已經(jīng)排序的輸入也成立，因?yàn)镺(n)

O(n2).然而插入排序的最壞運(yùn)行時(shí)間(n2)不能應(yīng)用到每個(gè)輸入，因?yàn)閷?duì)于已經(jīng)排序的輸入,(n)

(n2).如果f(n)=O(nk),

則稱f(n)是多項(xiàng)式界限的。10高階函數(shù)集合對(duì)于給定的函數(shù)g(n),(g(n))={f(n):存在正常數(shù)c和n0

，使得對(duì)于所有n

n0，0

cg(n)<f(n)}記作f(n)(

g(n)),或簡(jiǎn)記為f(n)=(

g(n)).f(n)=

(

g(n))nn0cg(n)f(n)11O,,標(biāo)記的關(guān)系對(duì)于f(n)和g(n),f(n)=(g(n))當(dāng)且僅當(dāng)f(n)=O(g(n))且f(n)=(g(n)).O:漸進(jìn)上界

:漸進(jìn)緊界

:漸進(jìn)下界12關(guān)于

標(biāo)記用來描述運(yùn)行時(shí)間的最好情況對(duì)所有輸入都正確比如，對(duì)于插入排序最好運(yùn)行時(shí)間是(n),

或者說，運(yùn)行時(shí)間是(n).最壞運(yùn)行時(shí)間是(n2)但是說運(yùn)行時(shí)間是(n2)則有誤可以用來描述問題排序問題的時(shí)間復(fù)雜性是(n)13嚴(yán)格低階函數(shù)給定一個(gè)函數(shù)g(n),o(g(n))={f(n):對(duì)于任意正常數(shù)c，存在一個(gè)正數(shù)n0

，從而對(duì)所有n

n0，滿足0

f(n)<cg(n)

}記作f(n)

o(

g(n)),或者簡(jiǎn)寫為f(n)=o(

g(n)).f(n)=o(

g(n))nn0g(n)f(n)1/2g(n)2g(n)n0n015關(guān)于o標(biāo)記O標(biāo)記可能是或不是緊的2n2=O(n2)是緊的,但2n=O(n2)不是緊的.o標(biāo)記用于標(biāo)記上界但不是緊的情況2n=o(n2),但是2n2

o(n2).區(qū)別:某個(gè)正常數(shù)c在O標(biāo)記中，

但所有正常數(shù)c在o標(biāo)記中.16嚴(yán)格高階函數(shù)集合對(duì)于給定函數(shù)g(n),(g(n))={f(n):對(duì)于任意正常數(shù)c,存在正數(shù)n0

對(duì)于n

n0，0

cg(n)<f(n)}記作f(n)(

g(n)),或者簡(jiǎn)記為f(n)=(

g(n)).

標(biāo)記,類似o標(biāo)記,表示不緊的下界.n2/2=(n),但n2/2(n2)f(n)=(

g(n))當(dāng)且僅當(dāng)g(n)=o(f(n)).lim=f(n)g(n)n

17漸進(jìn)符號(hào)的性質(zhì)傳遞性:所有五個(gè)標(biāo)記f(n)=

(g(n))且g(n)=

(h(n))

f(n)=

(h(n))自反性:O,,.f(n)=

(f(n))對(duì)稱性:

f(n)=

(g(n))當(dāng)且僅當(dāng)g(n)=

(f(n))反對(duì)稱性:f(n)=O(

g(n))當(dāng)且僅當(dāng)

g(n)=

(f(n)).f(n)=o(

g(n))當(dāng)且僅當(dāng)

g(n)=

(f(n)).注意！請(qǐng)各位評(píng)審老師提出寶貴建議！謝謝！本講內(nèi)容192.1計(jì)算復(fù)雜性函數(shù)的階2.2和式的估計(jì)與界限2.3遞歸方程為什么需要和式的估計(jì)與界限FORl=2TOn

FORi=1TOn-l+1DO

j=i+l-1;

m[i,j]=∞;

FORk

iToj-1DO

q=m[i,k]+m[k+1,j]+pi-1pkpjIFq<m[i,j]THENm[i,j]=q;

1.線性和

和式的估計(jì)2.級(jí)數(shù)

3.和的界限3/2直接求和的界限請(qǐng)各位評(píng)審老師提出寶貴建議！謝謝！本講內(nèi)容322.1計(jì)算復(fù)雜性函數(shù)的階2.2和式的估計(jì)與界限2.3遞歸方程遞歸方程:遞歸方程是使用小的輸入值來描述一個(gè)函數(shù)的方程或不等式.

遞歸方程

遞歸方程例:Merge-sort排序算法的復(fù)雜性方程

T(n)=

(1) ifn=1T(n)=2T(n/2)+

(n) ifn>1.

T(n)的解是

(nlogn)

替換方法:首先猜想,然后用數(shù)學(xué)歸納法證明.迭代方法:把方程轉(zhuǎn)化為一個(gè)和式然后用估計(jì)和的方法來求解.Master定理方法:

求解型為T(n)=aT(n/b)+f(n)的遞歸方程

求解遞歸方程的三個(gè)主要方法替換方法Ⅰ：聯(lián)想已知的T(n)

例1.求解2T(n/2+17)+n替換方法

證明：用數(shù)學(xué)歸納法替換方法Ⅰ：猜測(cè)上下界，減少不確定性范圍問題：猜測(cè)正確，數(shù)學(xué)歸納法的歸納步似乎證不出來解決方法：從guess中減去一個(gè)低階項(xiàng)，可能work.細(xì)微差別的處理

DKE-LAB(2009)避免陷阱

變量替換方法: