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

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

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

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

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

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

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

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）猜測解的形式）猜測解的形式2）用數學歸納法找出使解真正有效的）用數學歸納法找出使解真正有效的常數常數確定確定T (n) = 2T ( n/2 )+ n的解的解O(g(n) = f (n) | 存在存在正常數正常數c和和n0使使得對所有得對所有n n0有：有：0 f(n) cg(n) 例子：例子：猜其解為：猜其解為： T

8、 (n) = O(nlgn)即證：即證： T (n) cnlgn , c 0證：證：假設上述不等式對于假設上述不等式對于 n/2 成立。成立。代入不等式得：代入不等式得： 13第第2，3步目的是步目的是找有效的常數找有效的常數cT ( n/2 ) c( n/2 )lg( n/2 )解為：解為：T(n) = (nlgn)小貼士：小貼士：對遞歸式進行替換：對遞歸式進行替換：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)證：證：假設上述不等式對于假設上述不等式對于 n/2 成立。成立。確定確定T (n) = 2T ( n/2 )+ n的解的解例子：例子：目標：目標：T (n) cnlgn , c 014T ( n/2 ) c( n/2 )lg( n/2 )對于邊界：對于邊界： 只要找到常數只要找到常數n0,使得當使得當n n0， T (n) cnlgn 即可。即可。 假設假設T(1) = 1是唯一的邊界條件是唯一的邊界條件 當當n = 1時時, T (1) clg1 = 0， 而而T (1) = 1；矛盾；矛盾 當當n = 2時時，T (2) 2clg2 又又 T (

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

11、的解 與與T (n) = 2T ( n/2 )+ n類似，類似，可直接猜測其解為：可直接猜測其解為：O(nlgn)16解為：解為：T(n) = (nlgn)小貼士：小貼士：例例2：確定：確定T (n) = 2T ( n )+ lgn的解的解 設設m = lgn,即即n = 2m T (2m) = 2T (2m/2)+ lg2m 再設再設 S(m) = T (2m),得：得： S(m) = 2 S(m/2) + m猜測其解為：猜測其解為：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.主方法主方法遞歸樹法遞歸樹法使用遞歸樹使用遞歸樹原因原因： 遞歸樹的方法適合產生好的猜測。遞歸樹的方法適合產生好的猜測。使用遞歸樹的使用遞歸樹的作用作用： 所有層次的總代價是一個好的猜測

13、所有層次的總代價是一個好的猜測使用遞歸樹的使用遞歸樹的思路思路：1 1）先構建遞歸樹，計算出總代價）先構建遞歸樹，計算出總代價 2 2）然后用代換法進行加以驗證。）然后用代換法進行加以驗證。19例子例子：求解：求解T (n) = 3T ( n/4 )+ (n2) 的上界的上界1.建立遞歸建立遞歸式式： T (n) = 3T (n/4)+ cn2 2.建立建立T (n) = 3T (n/4)+ cn2 的遞歸的遞歸樹樹(c0 ,不妨假設不妨假設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深度和每層結點的個數：深度和每層結點的個數：深度深度每層的每層的結點數結點數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層代價層代價第第1層代價層代價第第2層代價層代價第第4n層代價層代價遞歸樹每層的代價：遞歸樹每層的代價：22遞歸樹的總代價：遞歸樹的總代價：無窮遞減等比數無窮遞減等比數

15、列的求和公式列的求和公式= = 首項首項/(1-/(1-公比公比) )猜測猜測T (n) = 3T ( n/4 )+ cn2 的解為的解為O(n2)總代價總代價232 2）用代換法進行驗證）用代換法進行驗證證：當常數證：當常數d 0時，時，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) | 存在存在正常數正常數c和和n0使得對使得對所有所有n n0有：有：0 f(n) cg(n) 只有只有d (16

16、/13)c，最后一步總成立。，最后一步總成立。系數：系數：24例子例子：求解：求解T (n) = 3T ( n/4 )+ (n2) 的上界的上界猜測猜測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)漸進的正函數漸進的正函數a1b b1 1n/b代替代替 n/b 或或 n/b 26主定理：主定理：T(n) = a T(n/b) + f(n)條件：條件：a1 ,b1, f(n)漸進的正函漸進的正函數數,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)+) ，當，當c1, n足夠大時，足夠大時， 有有a f(n/b) c f

18、(n),則則T (n)= (f(n)都是將都是將f(n)與與 nlogba進行比較進行比較f(n) nlogba 直覺上的大小直覺上的大小不僅大于（小于）而且不僅大于（小于）而且多項式的大于（小于）多項式的大于（小于） 0的常數的常數f(x)多項式的大于多項式的大于g(x) : : 存在實數存在實數 0, f(x) 比比 g(x) 多一個因子多一個因子n 27例例1 1：主方法應用：主方法應用：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)+) ，當，當c1，n足夠大時足夠大時,有有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主方法應用：主方法應用：由題可得：由題可得：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)+) ，當，當c1，n足夠大時足夠大時,有有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：主方法應用：主方法應用：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)+) ，當，當c1， n足夠大時足夠大時,有有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+) ，當，當c n滿足第三條滿足第三條nlgn 漸近的大于漸近的大于 n不是多項式大于不是多項式大于(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+) ，當，當c1，n足夠大時足夠大時,有有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.主方法主方法解的形式很容易猜的情形解的形式很容易猜的情形遞歸樹的總代價是一個好遞歸樹的總代價是一個好的猜測的猜測很容易確定許多遞歸式的解，很容易確定許多遞歸式的解，但是不能覆蓋

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

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

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

27、序列 右子序列key一次劃分key快速排序快速排序算法描述算法描述38287413564主元主元2 28 87 78 81 17 73 35 56 6一次調整42 28 81 17 73 35 56 648 8例：例：39求順序統(tǒng)計量求順序統(tǒng)計量例：選第例：選第6 6個順序統(tǒng)計量個順序統(tǒng)計量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個順序統(tǒng)計量個順序統(tǒng)計量第第4個順序統(tǒng)計量個順序統(tǒng)計量4