算法設計與分析 ch2 學習課件

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

2.2和式的估計與界限2.3遞歸方程3增長的階如何描述算法的效率？增長率忽略低階項，保留最高階項忽略常系數(shù)利用(n2)表示插入排序的最壞運行時間(1),(lgn),(n),(n),(nlgn),(n2),(n3),(2n),(n!)4增長函數(shù)漸進效率:輸入規(guī)模非常大忽略低階項和常系數(shù)只考慮最高階(增長的階)典型的增長階:(1),(lgn),(n),(n),(nlgn),(n2),(n3),(2n),(n!)增長的記號: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對于任意n1,c2?,且對于任意n7，c1

1/14因此

c1

=1/14,c2=?,n0

=7.證明6n3

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

n0時，c1n2

6n3

c2n2。當n>c2/6時，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ù)時間復雜性.8低階函數(shù)集合對于給定的函數(shù)g(n),O(g(n))={f(n):存在正常數(shù)c和n0

滿足對于所有n

n0，0

f(n)

cg(n)}記作f(n)

O(

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

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

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

g(n))

f(n)=O(

g(n))

標記強于O標記.(

g(n))

O(

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

標記,表示漸進緊界一些討論:當我們談到插入排序的最壞運行時間是O(n2),這個結論適用于所有的輸入，即使對于已經(jīng)排序的輸入也成立，因為O(n)

O(n2).然而插入排序的最壞運行時間(n2)不能應用到每個輸入，因為對于已經(jīng)排序的輸入,(n)

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

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

，使得對于所有n

n0，0

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

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

g(n)).f(n)=

(

g(n))nn0cg(n)f(n)11O,,標記的關系對于f(n)和g(n),f(n)=(g(n))當且僅當f(n)=O(g(n))且f(n)=(g(n)).O:漸進上界

:漸進緊界

:漸進下界12關于

標記用來描述運行時間的最好情況對所有輸入都正確比如，對于插入排序最好運行時間是(n),

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

，從而對所有n

n0，滿足0

f(n)<cg(n)

}記作f(n)

o(

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

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

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

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

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

對于n

n0，0

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

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

g(n)).

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

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

17漸進符號的性質(zhì)傳遞性:所有五個標記f(n)=

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

(h(n))

f(n)=

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

(f(n))對稱性:

f(n)=

(g(n))當且僅當g(n)=

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

g(n))當且僅當

g(n)=

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

g(n))當且僅當

g(n)=

(f(n)).注意！請各位評審老師提出寶貴建議！謝謝！本講內(nèi)容192.1計算復雜性函數(shù)的階2.2和式的估計與界限2.3遞歸方程為什么需要和式的估計與界限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.線性和

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

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

遞歸方程

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

T(n)=

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

(n) ifn>1.

T(n)的解是

(nlogn)

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

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

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

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

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

DKE-LAB(2009)避免陷阱

變量替換方法: