離散數(shù)學：第10章 組合分析初步2

1、110.3 遞推方程的求解與應用遞推方程的求解與應用nHanoi 塔問題塔問題n遞推方程的定義遞推方程的定義n二分歸并排序算法的分析二分歸并排序算法的分析n快速排序算法的分析快速排序算法的分析n遞歸樹遞歸樹n分治算法分析的一般公式分治算法分析的一般公式2HanoiHanoi塔問題塔問題Hanoi塔問題：塔問題：從從A柱將這些圓盤移到柱將這些圓盤移到C柱上去柱上去. 如果把一個圓盤從如果把一個圓盤從一個柱子移到另一個柱子稱作一個柱子移到另一個柱子稱作 1 次移動，在移動和放置次移動，在移動和放置時允許使用時允許使用B柱，但不允許大圓盤放到小圓盤的上面柱，但不允許大圓盤放到小圓盤的上面. 問問把所

2、有的圓盤的從把所有的圓盤的從A移到移到C總計需要多少次移動？總計需要多少次移動？3算法設計與分析算法設計與分析算法算法 Hanoi (A,C,n) /*把把n個盤子從個盤子從A移到移到C1. Hanoi (A,B,n-1) 2. move (A,C) /*把把1個盤子從個盤子從A移到移到C3. Hanoi (B,C,n-1) 移動移動n個盤子的總次數(shù)為個盤子的總次數(shù)為T(n) ，得到遞推方程，得到遞推方程 T(n) = 2T(n 1) +1. T(1)=1. 可以求得可以求得 T(n)=2n 11秒鐘移動秒鐘移動1次，次，64個盤子大約需要個盤子大約需要5000億年億年4（等比級數(shù)求和）（等比

3、級數(shù)求和）代入初值代入初值的項替換的項替換被含被含的項替換的項替換被含被含12)(12.22212.22)1(2.122)3(2)3()2(12 1)3(2212)2(2)2()1(1 1)2(2 21)1(2)(3213212322 nnnnnnnTnTnTnTnTnTnTnTnTnTnT5遞推方程的定義遞推方程的定義定義定義10.5 設序列設序列a0, a1, , an, , 簡記為簡記為an, 一一個把個把an與某些個與某些個ai（in）聯(lián)系起來的等式叫做關(guān)）聯(lián)系起來的等式叫做關(guān)于序列于序列an的的遞推方程遞推方程. 實例：實例： Fibonacci數(shù)列：數(shù)列： fn=fn-1+fn-2

4、, 初值初值 f0=1, f1=1 階乘數(shù)列階乘數(shù)列an，an=n!：an=nan-1, a1=1 求解方法：迭代法求解方法：迭代法 0)1(2),()(2)(11TnnOiTnnTni6二分歸并排序算法二分歸并排序算法算法算法Mergesort(A,s,t) /*排序數(shù)組排序數(shù)組As.t1. m(t-s)/22. AMergesort(A,s,m) /*排序前半數(shù)組排序前半數(shù)組3. BMergesort(A,s+1,t) /*排序后半數(shù)組排序后半數(shù)組4. Merge(A,B) /*將排好序的將排好序的A,B歸并歸并假設假設n=2k，比較次數(shù)至多為，比較次數(shù)至多為W(n) W(n)=2W(n/

5、2)+n 1歸并兩個歸并兩個n/2大小數(shù)組的比較次數(shù)為大小數(shù)組的比較次數(shù)為n 17實例實例 輸入輸入：5, 1, 7, 8, 2, 4, 6, 3 劃分：劃分：5, 1, 7, 8, 2, 4, 6, 3 遞歸排序前半個數(shù)組遞歸排序前半個數(shù)組: 5, 1, 7, 8 1, 5, 7, 8 遞歸排序后半個數(shù)組遞歸排序后半個數(shù)組: 2 ,4, 6, 3 2, 3, 4, 6 歸并歸并: 1, 5, 7, 8 和和 2, 3, 4, 6 輸出：輸出：1, 2, 3, 4, 5, 6, 7, 8 歸并過程歸并過程157823468求解遞推方程求解遞推方程1log122)12.22(2(1)2.1222

6、22)2(2122212)2(221222)2(21212)2(2 2 12 )2 (2 )(2123323222121 nnnkkWWWWWWnWkkkkkkkkkkkkkkkkkkkkkk9歸納法驗證解歸納法驗證解nn=1代入上述公式得代入上述公式得 W(1)=1 log1 1+1=0， 符合初始條件符合初始條件. n假設對于任何小于假設對于任何小于n的正整數(shù)的正整數(shù)t，W(t)都是正確的，都是正確的，將結(jié)果代入原遞推方程的右邊得將結(jié)果代入原遞推方程的右邊得 2W(n/2)+n 1 =2(2k 1 log2k 1 2k 1+1)+2k 1 =2k(k 1) 2k+2+2k 1=k2k 2k

7、+1 = nlogn n+1=W(n) 10快速排序算法快速排序算法算法算法 Q Quicksort(A,p,r) /*排序數(shù)組排序數(shù)組Ap.r輸入：輸入：數(shù)組數(shù)組Ap.r輸出：排好序的數(shù)組輸出：排好序的數(shù)組A 1. if p r 2. then qPartition(A, p, r) /*以以Ap為準劃分為準劃分A 3. ApAq /*Ap與與Aq交換交換 4. Quicksort(A,p,q-1) /*對子數(shù)組遞歸排序?qū)ψ訑?shù)組遞歸排序 5. Quicksort(A,q+1,r)11Partition(A,p,r) 1. x Ap 2. i p 3. j r+1 4. while true

8、do 5. repeat j j 1 6. until A j x /*左邊第左邊第1個比個比Ap大的大的Ai 9. if i j 10. then A i A j /*交換交換Aj與與Ai 11. else return j 劃分過程劃分過程1227 99 0 8 13 64 86 16 7 10 88 25 9027 25 0 8 13 64 86 16 7 10 88 99 9027 25 0 8 13 10 86 16 7 64 88 99 9027 25 0 8 13 10 7 16 86 64 88 99 9016 25 0 8 13 10 786 64 88 99 902713平

9、均時間復雜度平均時間復雜度nT(n)為對數(shù)組的各種輸入平均做的比較次數(shù)為對數(shù)組的各種輸入平均做的比較次數(shù) 將輸入按照將輸入按照Ap在排好序后的位置分別為在排好序后的位置分別為1, 2, , n進行分類進行分類. 假設每類輸入出現(xiàn)的概率相等假設每類輸入出現(xiàn)的概率相等nAp處位置處位置1，劃分后子問題規(guī)模分別為，劃分后子問題規(guī)模分別為0和和n-1 Ap處位置處位置n，劃分后子問題規(guī)模分別為，劃分后子問題規(guī)模分別為n-1和和0 nn 種輸入的平均復雜度為種輸入的平均復雜度為)()(2)()0()1(.)2()1()1()0(1)(11nOiTnnOTnTnTTnTTnnTni 14遞推方程求解遞推方

10、程求解 0)1(2),()(2)(11TnnOiTnnTni 2122111)()(21)()1()(2)(nininciTnTnccniTnnT為為某某個個常常數(shù)數(shù)差消法化簡差消法化簡)()1(21)()1()(nOnTnTnnnT )()1()1()(nOnTnnnT 15迭代迭代 31.1112)1(31.11111)2(1)1(1)(nncTnncncncnnTcncnnTnnT為為某某個個常常數(shù)數(shù)16用積分近似用積分近似)(log2ln)1ln(ln131.1111212nOnxdxxnnnn )log()(nnOnT .17遞歸樹遞歸樹 0 (1)2 , 1 ) /2 (2 )(W

11、nnnWnWkW(n)W(n/2)W(n/2)n 1n/2-1W(n/4)n 1n/2-1W(n/4).18n-1n/2-1n/2-1n/4-1n/4-1n/4-1n/4-1.1 1 1 1 1 1 1 1 1 1n-1n-2n-4n-2k 11log)12()2.21()2(.)2()1(11 nnnnknknnnkkk19分治算法的常用遞推公式分治算法的常用遞推公式 1)1()()/()(TbnndbnaTnTk其中其中a為子問題個數(shù)，為子問題個數(shù)，n/b為子問題規(guī)模，為子問題規(guī)模，d(n)為分解成為分解成子問題或組合解的代價子問題或組合解的代價方程的解為：方程的解為： banObannObanOnTcnndanOanOnTcndaabb)()log()()(:)(1)(log1)()(:)(loglog20)/()()/(.)/()/()/(.)()/()/()(10221122ikiikkkkkkkbndaandbnadbnabndabnTandbnadbnTanT ankbbnaaloglog Case1 d(n)=c 1)(log1)()(11)(loganOkcaanOaOaacanTkakkkb迭代迭代21Case2 d(n)=cn banObabacababacnabannOcnknbanObabacnnbacnabcnaanTakkkkkkakiikik