算法設(shè)計與分析講義chapter2

1、第二章 算法分析的數(shù)學(xué)基礎(chǔ)outline 1 算法復(fù)雜性的階 2 和式的估計與界限 3 遞歸方程 4 集合、關(guān)系、函數(shù)、圖、樹等 5 計數(shù)原理和概率論2.1 復(fù)雜性函數(shù)的階2.1.1同階函數(shù)集合 定義2.1.1(同階函數(shù)集合). q(f(n)=g(n)|$c1,c2>0,n0 ,當(dāng)n³ n0 ,c1f(n)£g(n)£c2f(n)稱為與f(n)同階的函數(shù)集合。 *如果g(n)Îq(f(n),我們稱個g(n)與f(n)同階。 *g(n)Îq(f(n)常記作g(n)=q(f(n)。 *f(n)必須是極限非負(fù)的，即當(dāng)n充分大以后，f(n)是非負(fù)

2、的，否則=空集。 例1 證明 證. 設(shè) ，令c1=a/4, c2=7a/4,則， 令。當(dāng)時成立。 例2 證明 證. 如果存在c1、c2 >0，n0使得當(dāng)n³n0時，c1£6n3£c2n2。于是，當(dāng)n>c2/6時，n£c2/6，矛盾。 例3 例4 因任何常數(shù)，如果令 。2.1.2 低階函數(shù)集合定義2.1.2(低階函數(shù)集合). O(f(n)=g(n)|$c>0,n0 ,當(dāng)n³ n0 ,0£g(n)£cf(n)稱為比f(n)低階的函數(shù)集合。*如果g(n)ÎO(f(n),稱f(n)是g(n)的上界。*g(

3、n)ÎO(f(n)常記作g(n)=O(f(n)。 例1 例2 證明 。證. 令c=1,n0=1,則當(dāng)時，。2.1.3 高階函數(shù)集合定義2.1.3(高階函數(shù)集合). W(f(n)=g(n)|$c>0,n0 ,當(dāng)n³ n0 ,0£cf(n)£g(n)稱為比f(n)高階的函數(shù)集合。*如果g(n)Î W(f(n),稱f(n)是g(n)的下界。*g(n)ÎW(f(n)常記作g(n)=W(f(n)。 定理2.1.對于任意f(n)和g(n), iff 而且f(n)=W(g(n). 證. 如果, 則 當(dāng)時,. 顯然. 如果且,則由可 知，存在使

4、得，當(dāng)，。由 f(n)=W(g(n)可知，使得當(dāng)， 令,則當(dāng)，。 2.1.4. 嚴(yán)格低階函數(shù)集合定義2.1.4(嚴(yán)格低階函數(shù)集合). for all 稱為嚴(yán)格比g(n)低階的函數(shù)集合。*如果f(n)Îo(g(n),稱g(n)是f(n)的嚴(yán)格上界。*f(n)Îo(g(n)常記作f(n)=o(g(n)。 例1. 證明 證. 對, 欲，必，即。所以，當(dāng)時，對，n³n0。 例2證明證. 當(dāng)c=1>0時，對于任何, 當(dāng)，都不成立命題2.1. 證.由于f(n)=o(g(n), 對任意e>0,存在，當(dāng)時, 0£f(n)<eg(n),即. 于是, .2

5、.1.5 嚴(yán)格高階函數(shù)集合 定義2.1.4(嚴(yán)格高階函數(shù)集合). ， for all 稱為嚴(yán)格比g(n)高階的函數(shù)集合。 命題2.2. f(n)Îw(g(n) iff g(n)Îo(f(n). 證：Þ 對，1/c>0. 由知, 對1/c>0,當(dāng)時,(1/c)g(n)<f(n), 即g(n)<cf(n). 于是, .Ü 對于任意c>0, 1/c>0.由可知, 當(dāng)時, g(n)<(1/c)f(n)，即cg(n)<f(n). 于是，。 例1證明n2/2=w(n). 證. 對"c>0,cn<n

6、2/2, 只需n>2c.令n0=2c+1, 則當(dāng)n³n0, cn<n2/2. 例2. 證明n2/2=w(n2). 證. 若n2/2=w(n2)，則對于c=1/2, 存在n0, 當(dāng)時, cn2<n2/2，即c<1/2，矛盾. 命題2.3. 證：對",由于,必存在n0 ,使得當(dāng)n³n0時, f(n)>cg(n),即當(dāng)n³n0時,f(n)/g(n)>c. 于是, .2.1.6 函數(shù)階的性質(zhì) A傳遞性：（a）（b）（c）（d）（e） . B 自反性：（a） ，（b） ，（c） . C 對稱性 . D 反對稱性： *并非所有函數(shù)

7、都是可比的，即對于函數(shù)和，可能. 例如, 和.2.2 標(biāo)準(zhǔn)符號和通用函數(shù)2.2.1 Flour和ceiling定義2.2.1(Flours和ceiling). 表示小于或等于x的最大整數(shù). 表示大于等于x的最小整數(shù). 命題2.2.1 命題2.2.2 對于任意函數(shù)n, 證. 若,則，. 于是 若 n=2k+1, 則. 命題2.2.3 設(shè)n、a、b是任意整數(shù)，則 (1) 。 (2) 證. (1) 若,則。 若，0<，則 = (2) 類似于(1)的證法。2.2.2 多項式 命題2.2.4 ,其中 證. 由于，所以。 定義2.2.2 如果如果 ，則城是多項式界限的。2.3 和2.3.1 求和公式

8、的性質(zhì) 1 線性和命題2.4.5 命題2.4.6 證. 對n用數(shù)學(xué)歸納法證明。 當(dāng)時，顯然成立。假設(shè)時成立。 令，則 。 2. 級數(shù) 命題2.4.7 命題2.4.8 命題2.4.9 n 命題2.4.10 . 命題2.4.11 命題2.4.12 命題2.4.13 3 和的界限 ·數(shù)學(xué)歸納法證明 例1. 證明 證 證明對于c³2/3, 存在一個n0 ,當(dāng)時. 當(dāng)n=0時, =c3n. 設(shè)n£m時成立. 令,則 . 例2. 錯誤證明： 證. 時,. *錯在O(n)的常數(shù)c隨n的增長而變化，不是常數(shù)。 *要證明需要證明: 對某個c>0, . ·直接求和的界

9、限例1. 例2. ´. 例3. 設(shè)對于所有,，求的上界. 解：, , 于是, . 例4. 求 的界 解. 使用例3的方法. . 于是 . 例5. 用分裂和的方法求的下界. 解: . 例6. 求 的上界 解：當(dāng)時, 于是 =O(1). 例7. 求的上界 解： 例8. 如果單調(diào)遞增, 則.f(x) f(x) m-1 m m+1 m+2 nf(x) , , m-1 m m+1 m+2.n-2 n-1 n n+1 例9. 當(dāng)單調(diào)遞減時,. 例10. , .2.4 遞歸方程遞歸方程: 遞歸方程是使用小的輸入值來描述一個函數(shù)的方程或 不等式.遞歸方程例: Merge-sort排序算法的復(fù)雜性方程

10、: T(n)=q(1) if n=1 T(n)=2T(n/2)+q(n) if n>1. T(n)的解是q(nlogn)求解遞歸方程的三個主要方法: ·Substitution方法: Guess first,然后用數(shù)學(xué)歸納法證明. ·Iteration方法: 把方程轉(zhuǎn)化為一個和式,然后用和估計技 術(shù)求解. ·Master方法: 求解型為T(n)=aT(n/b)+f(n)的遞歸方程.2.4.1 Substitution方法一般方法: ·猜解的形式 ·用數(shù)學(xué)歸納法證明猜測的解正確*該方法只能用于解可猜的情況. 1 Make a good gu

11、ess 不幸：無一般的猜測正確解的方法，需要 ·經(jīng)驗 ·機會 ·創(chuàng)造性和靈感 幸運：存在一些啟發(fā)規(guī)則幫助人們?nèi)ゲ聹y ·Guess方法：聯(lián)想類似的已知T(n) 例1. 求解, T(1)=1. 解：展開T(n)若干步,可以猜測T(n)=O(nlogn). 證明T(n)=O(nlogn). 設(shè)時或n=m+1時 . 于是,. *邊界條件的問題: 設(shè)是邊界條件，則不成立 *邊界條件問題的解決 我們只要求對于時,.我們只需看n=2 n=3，或4等，選一個滿足的最小即可。 ,只需,與上界的 不矛盾.例2. 求解. 解: 猜測: 與只相差一個17. 當(dāng)n充分大時的差別并

12、不大，因為 相差小. 我們可以猜. 證明: 用數(shù)學(xué)歸納法證明. ·Guess方法：猜測loose上、下界，然后減少不確定性范圍 例3. 求解. 解: 首先證明 然后逐階地降低上界、提高下界。 W(n)的上一個階是W(nlogn), O(n2)的下一個階是O(nlogn)。 ·細微差別的處理 問題：猜測正確，數(shù)學(xué)歸納法的歸納步似乎證不出來 原因：歸納假設(shè)不能充分證明 解決方法：從guess中減去一個低階項，可能work. 例4. 求解 解： 我們猜 證： 證不出 減去一個低階項，猜，是常數(shù) 證：設(shè)當(dāng)時成立 （只要）。 *c必須充分大，以滿足邊界條件。 ·避免陷阱 例

13、5求解。 解：猜 證：用數(shù)學(xué)歸納法證明。 -錯！ 錯在那里：過早地使用了而陷入了陷阱應(yīng)該在證明 了才可用。從不可能得 到因為對于任何c>0，我們都得不 到. ·變量替換 方法: 經(jīng)變量替換把一個遞歸方程變換為我們熟悉的方程. 例6. 求解 解：令，則, . 令則. 于是, . 顯然,即 由于2m=n, m=lgn, .2.4.2 Iteration方法 ·方法：循環(huán)地展開遞歸方程，把遞歸方程轉(zhuǎn)化為和式， 然后可使用求和技術(shù)解之。 例1. 令 ·方法的關(guān)鍵： 達到邊界條件時，展開需要的循環(huán)次數(shù). 由循環(huán)遞歸過程而得到和式. ·注意： 在循環(huán)中間可能猜

14、出解，此時應(yīng)停止循環(huán). floor和ceiling使問題復(fù)雜化，我們可以假設(shè)方程定義在 一個量的冪，如則可以省略.2.4.3 Master method目的：求解型方程, 是常數(shù)， 是正函數(shù) 方法：記住三種情況，則不用筆紙即可求解上述方程.1. Master 定理 定理2.4.1 設(shè)是常數(shù)，是一個函數(shù), 是定義在非負(fù)整數(shù)集上的函數(shù). 可以如下求解： . 若,是常數(shù)，則. . 若，則. 若,是常數(shù), 且對于所有充分大的n , c>1是常數(shù), 則.*直觀地：我們用與比較 . 若大，則 . 若大，則 . 若與同階，則.*更進一步：1. 在第一種情況,不僅小于，必須多項式地小 于,即對于一個常數(shù)

15、，2. 在第三種情況,不僅大于，必須多項式地大 于，即對一個常數(shù)，.*注意：這三種情況并沒有cover 所有可能的 情況1與情況2之間有空隙,即小于,但不是多 項式也小于. 情況2與情況3也同樣有間斷空隙. 對于這兩種情況，Master定理也無能為力. 2. Muster定理的使用 例1.求解. 解：, , 例2. 求解. 解：, , 例3. 求解 解： , 對所有n,. 于是, 例4. 求解.解：.大于，但 不是多項式也大于, Master定理不使用于該.2. Muster定理的證明 ·當(dāng)，k是正整數(shù) 引理1：設(shè)a³1, b>1, n=bk, k是正整數(shù)， 則方程

16、的解為: 證明: 由于, =. 于是. 引理2: 設(shè)a³1, b>1, n=bk, k是正整數(shù)， 則(1) if for , 則(2) if , then (3) if for some 0<c<1 and all n³b, then . 證明: (1) (2) 由于, . . (3) g(n)中的所有項皆為正. 由于對于0<c<1和 all n³b, , , , 我們有 于是, 引理3: a³1, b>1, n=bk, k為正整數(shù), 則 的解為: (1) if for some , then (2) if , then (3) if for some , and if for some 0<c<1 and all 充分大的n, then 證明: (1) 由引理1 和引理2: (2) (3) · 當(dāng)n不是b的冪時 思想: 當(dāng)T(n)單調(diào)遞增（單調(diào)遞減類似） · · 求的上界、的下界 可得到T(n)的界限。 · 求的下界類似于求的上 界，所以我們只求的上界 · 方法仍然是循環(huán)展開 · 需要處理序列： n 定義： 引理4. , , , , ，。 證：由可證。 引