遞歸式;中位數(shù)和順序統(tǒng)計(jì)

1、遞歸式;中位數(shù)和順序統(tǒng)計(jì)報(bào)告人：陳健琦2015-04-05漸進(jìn)記號(hào)漸進(jìn)記號(hào)遞歸式遞歸式中位數(shù)和順序統(tǒng)計(jì)量中位數(shù)和順序統(tǒng)計(jì)量1.1.代換法代換法2.2.遞歸樹法遞歸樹法3.3.主方法主方法大綱大綱1漸近記號(hào)漸近記號(hào)漸近確界記號(hào)漸近確界記號(hào) f(n) (g(n),用用符號(hào)符號(hào)f(n) = (g(n)來表示來表示 (g(n)= f(n)|存在存在正常數(shù)正常數(shù)c1,c2和和n0使得對(duì)所有使得對(duì)所有n n0有：有： 0 c1g(n) f(n) c2g(n) g(n)是是f(n)的漸的漸近確界近確界2f(n)的最高階的最高階等于等于g(n)的最高階的最高階 (g(n)是函數(shù)是函數(shù)的集合的集合例子：例子：a

2、n2+bn+c= (n2) n3 = (n3 )為什么漸近確界是一個(gè)函數(shù)的集合？為什么漸近確界是一個(gè)函數(shù)的集合？ 對(duì)于不同的輸入，計(jì)算時(shí)間對(duì)于不同的輸入，計(jì)算時(shí)間f(n)也不盡相也不盡相同，所以算法的計(jì)算時(shí)間是一個(gè)函數(shù)的集合同，所以算法的計(jì)算時(shí)間是一個(gè)函數(shù)的集合注意注意忽略系忽略系數(shù)和低數(shù)和低階項(xiàng)階項(xiàng)例子：例子：證明證明: : 對(duì)于對(duì)于c1NoImage證：證： (g(n)= f(n): 存在存在正常數(shù)正常數(shù)c1,c2和和n0使得對(duì)所有使得對(duì)所有n n0有：有：0 c1g(n) f(n) c2g(n) 3根據(jù)根據(jù)n0取取c1例子：例子：證明證明: : 對(duì)于對(duì)于c c2 2可取多組值可取多組值取

3、任意一組都取任意一組都可滿足可滿足 定義；定義；證畢證畢. . (g(n)= f(n): 存在存在正常數(shù)正常數(shù)c1,c2和和n0使得對(duì)所有使得對(duì)所有n n0有：有：0 c1g(n) f(n) c2g(n) 4漸近上界記號(hào)漸近上界記號(hào)O 給出了一個(gè)函數(shù)的上下界；當(dāng)只有給出了一個(gè)函數(shù)的上下界；當(dāng)只有漸近上界漸近上界時(shí)使用時(shí)使用O記號(hào)記號(hào)O(g(n) = f(n) | 存在存在正常數(shù)正常數(shù)c和和n0使得對(duì)所有使得對(duì)所有n n0有：有： 0 f(n) cg(n) 5例子：例子：an2+bn+c= O(n2) an+b=O(n2)f(n)的最高階的最高階小于等于小于等于g(n)的最高階的最高階漸近下界記

4、號(hào)漸近下界記號(hào)(g(n) = f(n) | 存在存在正常數(shù)正常數(shù)c和和n0使得對(duì)所有使得對(duì)所有n n0有：有： 0 cg(n) f(n) 6例子：例子： an2+bn+c= (n2) an3+bn+c= (n2)f(n)的最高階的最高階大于等于大于等于g(n)的最高階的最高階7漸近記號(hào)的總結(jié)漸近記號(hào)的總結(jié)漸近確界記號(hào)漸近確界記號(hào) f(n) = (g(n) f(n)的最高階的最高階等于等于g(n)的最高階的最高階漸近上界記號(hào)漸近上界記號(hào)O f(n) = O(g(n)f(n)的最高階的最高階小于等于小于等于g(n)的最高階的最高階漸近下界記號(hào)漸近下界記號(hào) f (n) = (g(n) f(n)的最高

5、階的最高階大于等于大于等于g(n)的最高階的最高階漸進(jìn)記號(hào)漸進(jìn)記號(hào)遞歸式遞歸式中位數(shù)和順序統(tǒng)計(jì)量中位數(shù)和順序統(tǒng)計(jì)量1.1.代換法代換法2.2.遞歸樹法遞歸樹法3.3.主方法主方法大綱大綱8遞歸式遞歸式 當(dāng)一個(gè)算法包含對(duì)自身的遞歸調(diào)用時(shí)，當(dāng)一個(gè)算法包含對(duì)自身的遞歸調(diào)用時(shí)，其運(yùn)行時(shí)間通常用其運(yùn)行時(shí)間通常用遞歸式遞歸式來表示來表示Merge-SortMerge-Sort過程中的最壞運(yùn)行時(shí)間如下：過程中的最壞運(yùn)行時(shí)間如下：解為：解為：T(n) = (nlgn)9求解遞歸式的方法求解遞歸式的方法1.1.代換法代換法2.2.遞歸樹法遞歸樹法3.3.主方法主方法10求解遞歸式的方法求解遞歸式的方法1.1.代

6、換法代換法2.2.遞歸樹法遞歸樹法3.3.主方法主方法代換法代換法在代換過程中忽略的問題：在代換過程中忽略的問題：1 1）常常假設(shè)函數(shù)自變量為整數(shù)，忽略上（下）取整常常假設(shè)函數(shù)自變量為整數(shù)，忽略上（下）取整例子：例子：T(n) = T( n/2 )+ T( n/2 ) + (n)通常將上式遞歸式看做為：通常將上式遞歸式看做為： T(n) = 2T(n/2)+ (n)適用于：解的形式很容易猜的情形適用于：解的形式很容易猜的情形11代換法代換法在代換過程中忽略的問題：在代換過程中忽略的問題：2 2）邊界細(xì)節(jié)）邊界細(xì)節(jié) 對(duì)于足夠小的對(duì)于足夠小的n來說，表示算法運(yùn)行的時(shí)間的遞歸式來說，表示算法運(yùn)行的時(shí)

7、間的遞歸式一般為一般為T(n) = (1)。例子：例子：通常將上式遞歸式看做為：通常將上式遞歸式看做為： T (n) = 2T (n/2)+ (n)12T (n) = (1) n = 1 T ( n/2 )+ T ( n/2 ) + (n) n 1 代換法的步驟代換法的步驟：1）猜測(cè)解的形式）猜測(cè)解的形式2）用數(shù)學(xué)歸納法找出使解真正有效的）用數(shù)學(xué)歸納法找出使解真正有效的常數(shù)常數(shù)確定確定T (n) = 2T ( n/2 )+ n的解的解O(g(n) = f (n) | 存在存在正常數(shù)正常數(shù)c和和n0使使得對(duì)所有得對(duì)所有n n0有：有：0 f(n) cg(n) 例子：例子：猜其解為：猜其解為： T

8、 (n) = O(nlgn)即證：即證： T (n) cnlgn , c 0證：證：假設(shè)上述不等式對(duì)于假設(shè)上述不等式對(duì)于 n/2 成立。成立。代入不等式得：代入不等式得： 13第第2，3步目的是步目的是找有效的常數(shù)找有效的常數(shù)cT ( n/2 ) c( n/2 )lg( n/2 )解為：解為：T(n) = (nlgn)小貼士：小貼士：對(duì)遞歸式進(jìn)行替換：對(duì)遞歸式進(jìn)行替換：T (n) 2c n/2 lg( n/2 ) + n 2c (n/2) lg (n/2) + n= cnlg(n/2) + n= cnlgn cnlg2 + n= cnlgn cn + n（只要（只要c 1即可）即可）猜其解為：

9、猜其解為： T (n) = O(nlgn)證：證：假設(shè)上述不等式對(duì)于假設(shè)上述不等式對(duì)于 n/2 成立。成立。確定確定T (n) = 2T ( n/2 )+ n的解的解例子：例子：目標(biāo)：目標(biāo)：T (n) cnlgn , c 014T ( n/2 ) c( n/2 )lg( n/2 )對(duì)于邊界：對(duì)于邊界： 只要找到常數(shù)只要找到常數(shù)n0,使得當(dāng)使得當(dāng)n n0， T (n) cnlgn 即可。即可。 假設(shè)假設(shè)T(1) = 1是唯一的邊界條件是唯一的邊界條件 當(dāng)當(dāng)n = 1時(shí)時(shí), T (1) clg1 = 0， 而而T (1) = 1；矛盾；矛盾 當(dāng)當(dāng)n = 2時(shí)時(shí)，T (2) 2clg2 又又 T (

10、2) = 2 T (1) + 2 = 4 2c 4 c 2 對(duì)遞歸式進(jìn)行替換對(duì)遞歸式進(jìn)行替換猜其解為：猜其解為： T (n) = O(nlgn)證：證：假設(shè)上述不等式對(duì)于假設(shè)上述不等式對(duì)于 n/2 成立。成立。確定確定T (n) = 2T ( n/2 )+ n的解的解例子：例子：15 T (n) = O(nlgn)怎樣才會(huì)有一個(gè)好的猜測(cè)？怎樣才會(huì)有一個(gè)好的猜測(cè)？1.經(jīng)驗(yàn)經(jīng)驗(yàn)2.構(gòu)建遞歸樹，會(huì)有一個(gè)好的猜測(cè)構(gòu)建遞歸樹，會(huì)有一個(gè)好的猜測(cè)3.與已知的遞歸式類似，可猜測(cè)此遞歸式有類似的解與已知的遞歸式類似，可猜測(cè)此遞歸式有類似的解例例1：確定：確定T (n) = 2T ( n/2 + 17)+ n的解

11、的解 與與T (n) = 2T ( n/2 )+ n類似，類似，可直接猜測(cè)其解為：可直接猜測(cè)其解為：O(nlgn)16解為：解為：T(n) = (nlgn)小貼士：小貼士：例例2：確定：確定T (n) = 2T ( n )+ lgn的解的解 設(shè)設(shè)m = lgn,即即n = 2m T (2m) = 2T (2m/2)+ lg2m 再設(shè)再設(shè) S(m) = T (2m),得：得： S(m) = 2 S(m/2) + m猜測(cè)其解為：猜測(cè)其解為：O(mlgm) T (n) = T (2m) = S(m) m = lgn O(mlgm) = O(lgnlglgn) T (n) = O(lgnlglgn)1

12、7代入上式得：代入上式得：忽略下取整忽略下取整則可得遞歸式：則可得遞歸式： T (n) = 2T (n1/2)+ lgn解：解：T (2m) = S(m) = O(mlgm) 解為：解為：T(n) = (nlgn)小貼士：小貼士：求解遞歸式的方法求解遞歸式的方法1.1.代換法代換法2.2.遞歸樹法遞歸樹法3.3.主方法主方法18求解遞歸式的方法求解遞歸式的方法1.1.代換法代換法2.2.遞歸樹法遞歸樹法3.3.主方法主方法遞歸樹法遞歸樹法使用遞歸樹使用遞歸樹原因原因： 遞歸樹的方法適合產(chǎn)生好的猜測(cè)。遞歸樹的方法適合產(chǎn)生好的猜測(cè)。使用遞歸樹的使用遞歸樹的作用作用： 所有層次的總代價(jià)是一個(gè)好的猜測(cè)

13、所有層次的總代價(jià)是一個(gè)好的猜測(cè)使用遞歸樹的使用遞歸樹的思路思路：1 1）先構(gòu)建遞歸樹，計(jì)算出總代價(jià)）先構(gòu)建遞歸樹，計(jì)算出總代價(jià) 2 2）然后用代換法進(jìn)行加以驗(yàn)證。）然后用代換法進(jìn)行加以驗(yàn)證。19例子例子：求解：求解T (n) = 3T ( n/4 )+ (n2) 的上界的上界1.建立遞歸建立遞歸式式： T (n) = 3T (n/4)+ cn2 2.建立建立T (n) = 3T (n/4)+ cn2 的遞歸的遞歸樹樹(c0 ,不妨假設(shè)不妨假設(shè)n是是4的冪的冪)1 1）建立遞歸樹過程：）建立遞歸樹過程：T(n)cn2T(n/4) T(n/4) T(n/4)(b)cn2T(n/16)c(n/4)2

14、c(n/4)2c(n/4)2T(n/16)T(n/16) T(n/16)(a)(c)20深度和每層結(jié)點(diǎn)的個(gè)數(shù)：深度和每層結(jié)點(diǎn)的個(gè)數(shù)：深度深度每層的每層的結(jié)點(diǎn)數(shù)結(jié)點(diǎn)數(shù)0 01 12 24n3 30 03 31 1 3 32 23 3 4nT (n) = 3T (n/4)+ cn2 的遞歸樹如下所示：的遞歸樹如下所示：令令a = nx,則則abn = (nx)bn = nb(nx) = nba21= n43 abn = nba第第0層代價(jià)層代價(jià)第第1層代價(jià)層代價(jià)第第2層代價(jià)層代價(jià)第第4n層代價(jià)層代價(jià)遞歸樹每層的代價(jià)：遞歸樹每層的代價(jià)：22遞歸樹的總代價(jià)：遞歸樹的總代價(jià)：無窮遞減等比數(shù)無窮遞減等比數(shù)

15、列的求和公式列的求和公式= = 首項(xiàng)首項(xiàng)/(1-/(1-公比公比) )猜測(cè)猜測(cè)T (n) = 3T ( n/4 )+ cn2 的解為的解為O(n2)總代價(jià)總代價(jià)232 2）用代換法進(jìn)行驗(yàn)證）用代換法進(jìn)行驗(yàn)證證：當(dāng)常數(shù)證：當(dāng)常數(shù)d 0時(shí)，時(shí)，T(n) dn2成立成立 T (n) = 3T ( n/4 )+ (n2) 由定義得：由定義得： T(n) 3d( n/4 ) 2+ cn2 3d(n/4)2 + cn2 = (3/16)dn2 + cn2 dn2 O(g(n) = f (n) | 存在存在正常數(shù)正常數(shù)c和和n0使得對(duì)使得對(duì)所有所有n n0有：有：0 f(n) cg(n) 只有只有d (16

16、/13)c，最后一步總成立。，最后一步總成立。系數(shù)：系數(shù)：24例子例子：求解：求解T (n) = 3T ( n/4 )+ (n2) 的上界的上界猜測(cè)猜測(cè)T (n) = 3T ( n/4 )+ cn2 的解為的解為O(n2)所以所以T (n) = 3T ( n/4 )+ cn2 的的解為解為O(n2)求解遞歸式的方法求解遞歸式的方法1.1.代換法代換法2.2.遞歸樹法遞歸樹法3.3.主方法主方法25求解遞歸式的方法求解遞歸式的方法1.1.代換法代換法2.2.遞歸樹法遞歸樹法3.3.主方法主方法主方法主方法主方法可以求如下遞歸式的解：主方法可以求如下遞歸式的解：T(n) = a T(n/b) +

17、f(n)漸進(jìn)的正函數(shù)漸進(jìn)的正函數(shù)a1b b1 1n/b代替代替 n/b 或或 n/b 26主定理：主定理：T(n) = a T(n/b) + f(n)條件：條件：a1 ,b1, f(n)漸進(jìn)的正函漸進(jìn)的正函數(shù)數(shù),n/b指的是指的是 n/b 或或 n/b T(n)可能有以下的三種漸近界：可能有以下的三種漸近界：1）若）若f(n) = O(n(logba)-) ，則，則T (n)= (nlogba)2）若）若f(n) = (nlogba) ，則，則T (n)= (nlogbalgn)3）若）若f(n) = (n(logba)+) ，當(dāng)，當(dāng)c1, n足夠大時(shí)，足夠大時(shí)， 有有a f(n/b) c f

18、(n),則則T (n)= (f(n)都是將都是將f(n)與與 nlogba進(jìn)行比較進(jìn)行比較f(n) nlogba 直覺上的大小直覺上的大小不僅大于（小于）而且不僅大于（小于）而且多項(xiàng)式的大于（小于）多項(xiàng)式的大于（小于） 0的常數(shù)的常數(shù)f(x)多項(xiàng)式的大于多項(xiàng)式的大于g(x) : : 存在實(shí)數(shù)存在實(shí)數(shù) 0, f(x) 比比 g(x) 多一個(gè)因子多一個(gè)因子n 27例例1 1：主方法應(yīng)用：主方法應(yīng)用：T(n) = 9 T(n/3) + n由題可得：由題可得：a = 9 , b = 3 , f(n) = n 則則nlogba = nlog39 = (n2) f(n) = n = O(n(log39)-

19、1) = 1 T (n) = (n2) 1）若）若f(n) = O(n(logba)-) ，則，則T (n)= (nlogba)2）若）若f(n) = (nlogba) ，則，則T (n)= (nlogbalgn)3）若）若f(n) = (n(logba)+) ，當(dāng)，當(dāng)c1，n足夠大時(shí)足夠大時(shí),有有a f(n/b) c f(n),則則T (n)= (f(n)T(n) = a T(n/b) + f(n)28符合第一種符合第一種例例2：T(n) = T(2n/3) + 1主方法應(yīng)用：主方法應(yīng)用：由題可得：由題可得：a = 1 , b = 3/2 , f(n) = 1 則則nlogba = nlog

20、3/21 = (1)T (n) = (lgn) 1）若）若f(n) = O(n(logba)-) ，則，則T (n)= (nlogba)2）若）若f(n) = (nlogba) ，則，則T (n)= (nlogbalgn)3）若）若f(n) = (n(logba)+) ，當(dāng)，當(dāng)c1，n足夠大時(shí)足夠大時(shí),有有a f(n/b) c f(n),則則T (n)= (f(n)T(n) = a T(n/b) + f(n)29 f(n) = nlogba = 0 符合第二種符合第二種例例3：主方法應(yīng)用：主方法應(yīng)用：T(n) = 3T(n/4) + nlgn由題可得：由題可得： a = 3 , b = 4 ,

21、 f(n) = nlgn 則則nlogba = nlog43 = n0.793 f(n) = nlgn = (nlog43+) = 0.2071）若）若f(n) = O(n(logba)-) ，則，則T (n)= (nlogba)2）若）若f(n) = (nlogba) ，則，則T (n)= (nlogbalgn)3）若）若f(n) = (n(logba)+) ，當(dāng)，當(dāng)c1， n足夠大時(shí)足夠大時(shí),有有a f(n/b) c f(n),則則T (n)= (f(n)T(n) = a T(n/b) + f(n)30符合第三種符合第三種滿足第滿足第3條，判斷不等式是否成立條，判斷不等式是否成立又又 a

22、f(n/b) = 3 f(n/4) = 3 (n/4)lg(n/4) = (3/4)n lgn - (3/4) nlg4 (3/4) nlgn = (3/4) f(n) c f(n) = c nlgn 可取可取c = 3/4，則，則T (n)= (f(n) = (nlgn )例例3：T(n) = 3T(n/4) + nlgn3）若）若f(n) = (nlogba+) ，當(dāng)，當(dāng)c n滿足第三條滿足第三條nlgn 漸近的大于漸近的大于 n不是多項(xiàng)式大于不是多項(xiàng)式大于(nlgn)/n = lgn 漸近小于漸近小于n 介于情況介于情況2)與與3)之間，之間，1）若）若f(n) = O(nlogba-)

23、 ，則，則T (n)= (nlogba)2）若）若f(n) = (nlogba) ，則，則T (n)= (nlogbalgn)3）若）若f(n) = (nlogba+) ，當(dāng)，當(dāng)c1，n足夠大時(shí)足夠大時(shí),有有a f(n/b) c f(n),則則T (n)= (f(n)T(n) = a T(n/b) + f(n)32f(n) nlogba 求解遞歸式的方法求解遞歸式的方法1.1.代換法代換法2.2.遞歸樹法遞歸樹法3.3.主方法主方法解的形式很容易猜的情形解的形式很容易猜的情形遞歸樹的總代價(jià)是一個(gè)好遞歸樹的總代價(jià)是一個(gè)好的猜測(cè)的猜測(cè)很容易確定許多遞歸式的解，很容易確定許多遞歸式的解，但是不能覆蓋

24、所有的情況但是不能覆蓋所有的情況遞歸式總結(jié)遞歸式總結(jié)33漸進(jìn)記號(hào)漸進(jìn)記號(hào)遞歸式遞歸式中位數(shù)和順序統(tǒng)計(jì)量中位數(shù)和順序統(tǒng)計(jì)量1.1.代換法代換法2.2.遞歸樹法遞歸樹法3.3.主方法主方法大綱大綱34中位數(shù)和順序統(tǒng)計(jì)量中位數(shù)和順序統(tǒng)計(jì)量中位數(shù)和順序統(tǒng)計(jì)量定義中位數(shù)和順序統(tǒng)計(jì)量定義中位數(shù)：中位數(shù)： 中位數(shù)是有序集合中的中間元素中位數(shù)是有序集合中的中間元素順序統(tǒng)計(jì)量順序統(tǒng)計(jì)量： 第第i i個(gè)順序統(tǒng)計(jì)量個(gè)順序統(tǒng)計(jì)量 = = 該集合中的第該集合中的第i i小的元素。小的元素。 最小值最小值是該集合中的第是該集合中的第1 1個(gè)順序統(tǒng)計(jì)量，個(gè)順序統(tǒng)計(jì)量， 最大值最大值是該集合中的第是該集合中的第n n個(gè)順序統(tǒng)

25、計(jì)量。個(gè)順序統(tǒng)計(jì)量。35同時(shí)得到最大和最小值同時(shí)得到最大和最小值 獨(dú)立的找出最大值和最小值，分別需要獨(dú)立的找出最大值和最小值，分別需要n-1次比較，次比較，總共需要總共需要2n-2次比較。次比較。同時(shí)得到最大和最小值，最多需要同時(shí)得到最大和最小值，最多需要3 n/2 次比較。次比較。個(gè)數(shù)為偶數(shù)：成對(duì)比較個(gè)數(shù)為偶數(shù)：成對(duì)比較個(gè)數(shù)為奇數(shù)：將第一個(gè)數(shù)設(shè)為最大和最小值，成對(duì)比較個(gè)數(shù)為奇數(shù)：將第一個(gè)數(shù)設(shè)為最大和最小值，成對(duì)比較36例例1 1：1 16 68 85 59 91111集合的個(gè)數(shù)為集合的個(gè)數(shù)為偶數(shù)偶數(shù)MAX = 6 MIN = 1 個(gè)數(shù)為偶數(shù)：成對(duì)比較個(gè)數(shù)為偶數(shù)：成對(duì)比較個(gè)數(shù)為奇數(shù)：將第一個(gè)數(shù)

26、設(shè)為最大和最小值，成對(duì)比較個(gè)數(shù)為奇數(shù)：將第一個(gè)數(shù)設(shè)為最大和最小值，成對(duì)比較MAX = 8 MAX = 11 先進(jìn)行一次比較，后做先進(jìn)行一次比較，后做了了3(n-2)/2次比較，總共次比較，總共做了做了(3n/2)-2次比較次比較37例例2 2：1 14 48 85 59 910101212集合的個(gè)數(shù)為集合的個(gè)數(shù)為奇數(shù)奇數(shù)MAX = 1 MIN = 1 個(gè)數(shù)為偶數(shù)：成對(duì)比較個(gè)數(shù)為偶數(shù)：成對(duì)比較個(gè)數(shù)為奇數(shù)：將第一個(gè)數(shù)設(shè)為最大和最小值，成對(duì)比較個(gè)數(shù)為奇數(shù)：將第一個(gè)數(shù)設(shè)為最大和最小值，成對(duì)比較MAX = 8 MAX = 9 MAX = 12 38總共做了總共做了3 n/2 次比較次比較主元待排序列左子

27、序列 右子序列key一次劃分key快速排序快速排序算法描述算法描述38287413564主元主元2 28 87 78 81 17 73 35 56 6一次調(diào)整42 28 81 17 73 35 56 648 8例：例：39求順序統(tǒng)計(jì)量求順序統(tǒng)計(jì)量例：選第例：選第6 6個(gè)順序統(tǒng)計(jì)量個(gè)順序統(tǒng)計(jì)量2 2主元主元一次劃分一次劃分8 87 71 13 35 56 64 42 21 13 34 47 75 56 68 81 2 3 4 5 6 7 81 2 3 4 5 6 7 84 64 68 65 6 7 8一次劃分一次劃分6 65 56 67 75 6 7 6 6第第6個(gè)順序統(tǒng)計(jì)量個(gè)順序統(tǒng)計(jì)量第第4個(gè)順序統(tǒng)計(jì)量個(gè)順序統(tǒng)計(jì)量4