第二章

算法分析的數(shù)學(xué)基礎(chǔ)

2.1.1同階函數(shù)集合2.1.2低階函數(shù)集合2.1.3高階函數(shù)集合2.1.4嚴(yán)格低階函數(shù)集合2.1.5嚴(yán)格高階函數(shù)集合2.1.6函數(shù)階的性質(zhì)2.1計(jì)算復(fù)雜性函數(shù)的階

2.1.1同階函數(shù)集合

定義2.1.1(同階函數(shù)集合)(f(n))={g(n)|c1,c2>0,n0,n>n0,c1f(n)g(n)c2f(n)}稱(chēng)為與f(n)同階的函數(shù)集合。

Example例2證明

證.如果存在c1、c2>0，n0使得當(dāng)nn0時(shí)，c16n3c2n2。于是，當(dāng)n>c2/6時(shí)，

nc2/6，矛盾。

ExampleExample2.1.2低階函數(shù)集合

Example例2證明n=O(n2).2.1.3

高階函數(shù)集合

2.1.4

嚴(yán)格低階函數(shù)集合

2.1.5

嚴(yán)格高階函數(shù)集合

Example例2.證明n2/2

w(n2)2.1.6

函數(shù)階的性質(zhì)

2.1.6函數(shù)階的性質(zhì)(續(xù))注意！Flour和ceiling

多項(xiàng)式

2.2

標(biāo)準(zhǔn)符號(hào)和通用函數(shù)

2.2.1

Flour和ceiling

如果f(n)=O(nk),則稱(chēng)f(n)是多項(xiàng)式界限的。1.線(xiàn)性和

2.3

和式的估計(jì)與界限

2.級(jí)數(shù)

3.和的界限直接求和的界限

遞歸方程:遞歸方程是使用小的輸入值來(lái)描述 一個(gè)函數(shù)的方程或不等式.

2.4遞歸方程

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

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

T(n)的解是(nlogn)

Substitution方法:Guessfirst,然后用數(shù)學(xué)歸納法證明.Iteration方法:把方程轉(zhuǎn)化為一個(gè)和式然后用估計(jì)和的方法來(lái)求解.Master方法:

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

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

例1.求解2T(n/2+17)+n2.4.1Substitution方法

證明：用數(shù)學(xué)歸納法Substitution方法Ⅰ：猜測(cè)上下界，減少不確定性范圍細(xì)微差別的處理

問(wèn)題：猜測(cè)正確，數(shù)學(xué)歸納法的歸納步似乎證不出來(lái)解決方法：從guess中減去一個(gè)低階項(xiàng)，可能work.

避免陷阱

變量替換方法:經(jīng)變量替換把遞歸方程變換為熟悉的方程.

方法：

循環(huán)地展開(kāi)遞歸方程，把遞歸方程轉(zhuǎn)化為和式，然后可使用求和技術(shù)解之。

2.4.2Iteration方法

2.4.3

Mastermethod

Master定理T(n)=(nlogba)T(n)=(f(n))f(n)(f(n)lgn)nn-對(duì)于紅色部分，Master定理無(wú)能為力Master定理的使用

Master定理的使用（續(xù)）地適Master定理的證明

biMaster定理的證明(續(xù))

引理2的證明

引理2的證明（續(xù)）

引理2的證明（續(xù)）

(f(n))Master定理的證明(續(xù))

引理3的證明

Master定理的證明(續(xù))

Master定理的證明(續(xù))

Master定理的證