遞歸分治和減治第一頁，共二十九頁，編輯于2023年，星期五1.遞歸及其性質遞歸算法是一種自身直接或間接調用自身的算法使用遞歸技術使得算法簡單明了、易于理解、容易編程和驗證。使用遞歸的程序往往很簡單系統(tǒng)對所有的子程序調用一視同仁，并不區(qū)分是不是調用了自身。也就是說，系統(tǒng)并不刻意發(fā)現(xiàn)遞歸成分。這是由子程序調用機制決定的系統(tǒng)用棧實現(xiàn)子程序調用，也就是用棧實現(xiàn)遞歸。對比不使用遞歸，棧結構的操作和維護是額外的時空開銷第二頁，共二十九頁，編輯于2023年，星期五2.分治法的設計原理分治法是把一個問題分解成多個子問題進行處理，然后把子問題的解綜合處理，得到原問題的解劃分所得的子問題與原問題結構上等價如果子問題太大，可以把子問題繼續(xù)劃分，直至劃分得到的子問題能夠直接求解分治法的兩個重要操作是：分解和綜合。其時間復雜度也全部由這二者決定，確切的時間復雜度由二者的對比關系決定第三頁，共二十九頁，編輯于2023年，星期五3.分治法的復雜度推導示例divide_and_conquer(p(n)){if((n<=n0)returnadhoc(p(n));//基礎項else{dividepintop1,p2,...,pk;//分for(i=1;i<=k;i++)//治yi=divide_and_conquer(pi);returnmerge(y1,y2,...,yk);//合}}第四頁，共二十九頁，編輯于2023年，星期五問題的遞歸方程：假定n=km，變換原方程得：第五頁，共二十九頁，編輯于2023年，星期五4.分治法的復雜度性質遞歸方程：x=1時的解：通解：符合該條件的分治是多項式級別的時間復雜度a=c是臨界點，a>c是真正意義上的分治；a<c是減治第六頁，共二十九頁，編輯于2023年，星期五5.快速排序理想的快速排序算法的復雜度遞歸方程如下，因為a=c=2，所以其復雜度為O(nlogn)：快速排序的時間復雜度最好情況下是O(nlogn)，最壞情況下是O(n2)，平均情況是O(nlogn)可以使用輔助技術選取合理的中軸當問題規(guī)模較小的時候，可以采用其他排序手法n用于分，2f(n/2)用于治第七頁，共二十九頁，編輯于2023年，星期五6.平面最接近點對6.1問題描述6.2分治法示意6.3分治法求解最近點對問題復雜度分析第八頁，共二十九頁，編輯于2023年，星期五6.1問題描述給定平面上的n個點的坐標，求出兩兩距離的最小值及其對應的點對兩點間的距離可以用勾股定理求得最直觀的解法是點之間循環(huán)兩兩求距離，記錄其最小值和點對第九頁，共二十九頁，編輯于2023年，星期五6.2分治法示意abcdefghiacbedfihgfgadbhceiacbefihgdadbcefghi這兩個數(shù)組邏輯上產生，沒有物理上產生這兩個數(shù)組物理上產生了第十頁，共二十九頁，編輯于2023年，星期五abcdefghi把問題分解為左右兩部分，左右分別求得解，左右最小值中取較小的一個d，作為中間部分最小值的參考中間部分按照縱坐標序列，每個點只需要比較它上面的7個點即可如果中間部分得到的最小值更小，則取這個值，否則取d。ddd左邊的4個格中不可能超過4個點，右邊也是第十一頁，共二十九頁，編輯于2023年，星期五6.3分治法求解最近點對問題復雜度分析復雜度函數(shù)遞歸方程：用分治法求解平面最近點對問題的時間復雜度是O(nlogn)–因為a=c=2用分治法求解平面最近點對問題的最大空間使用是O(nlogn)–但因為調用左右兩部分有先后之分，因此空間復雜度為O(n)上式中，n用于分，2f(n/2)用于治，7n用于合第十二頁，共二十九頁，編輯于2023年，星期五7.選擇問題7.1解法示例7.2算法中剩余部分序列大小估計7.3分治法求解選擇問題復雜度分析第十三頁，共二十九頁，編輯于2023年，星期五7.1解法示例求21個元素中的第8小元素：51,57,49,35,11,43,37,3,13,52,6,9,25,32,54,16,5,41,7,23,18把前面的20個元素劃分為5組，最后一個元素不處理，得到4組：(51,57,49,35,11),(43,37,3,13,52),(6,9,25,32,54),(16,5,41,7,23)，取各自的中值：49,37,25,16。在這些中值中取中值25（或者37）以25為中心，把原數(shù)組劃分為3部分：小于25的、等于25的、大于25的：(11,3,13,6,9,16,5,7,23,18),(25),(51,57,49,35,43,37,52,32,54,41)原序列中第8小的數(shù)就是小于25的序列中第8小的值第十四頁，共二十九頁，編輯于2023年，星期五舍棄等于25的序列和大于25的序列，僅對小于25的序列(11,3,13,6,9,16,5,7,23,18)進行處理，也就是求這個序列第8小的元素把它分成2組，(11,3,13,6,9),(16,5,7,23,18)它們的中值分別是9和16，取這兩個數(shù)的中值9以9為中心，把小于25的序列分為3部分：(3,6,5,7),(9),(11,13,16,23,18)，求原序列第8小的元素等價于求第三個序列第3小的元素對序列(11,13,16,23,18)排序得到(11,13,16,18,23)，這個序列第3小的元素是16，這就是原問題的解第十五頁，共二十九頁，編輯于2023年，星期五7.2算法中剩余部分序列大小估計遞增遞增舍棄部分：剩余部分：第十六頁，共二十九頁，編輯于2023年，星期五7.3分治法求解選擇問題復雜度分析復雜度函數(shù)的遞歸方程：由于上式中7n/10+n/5小于n，因此，用分治法求解選擇問題的時間復雜度是O(n)算法的空間復雜度估計與時間復雜度估計類似，也是O(n)第十七頁，共二十九頁，編輯于2023年，星期五8.最大子塊和8.1解法示例8.2分治法求最大子塊的復雜度分析第十八頁，共二十九頁，編輯于2023年，星期五8.1解法示例8 -3 -4 6 -8 9 -5 78 -3 -4 6-8 9 -5 7108 -3-4 67-8 9-5 7118967811最大子塊來源有3個：要么在左塊，要么在右塊，要么橫跨左右兩塊第十九頁，共二十九頁，編輯于2023年，星期五8.2分治法求最大子塊的復雜度分析復雜度函數(shù)遞歸方程：用分治法求解最大子塊問題的時間復雜度是O(nlogn)，因為a=c=2用分治法求解最大子塊問題的空間復雜度是O(logn)，額外空間用于調用間的參數(shù)傳遞，是調用的深度?？臻g復雜度不是O(n)，因為遞歸調用有先后之分第二十頁，共二十九頁，編輯于2023年，星期五9.二進制方程9.1問題描述9.2窮舉法求解9.3問題分析9.4遞歸方程9.5該問題對應用分治法的啟示9.6復雜度分析第二十一頁，共二十九頁，編輯于2023年，星期五9.1問題描述a0+a1x1+a2x2+a3x2x1+a4x3+a5x3x1+a6x3x2+a7x3x2x1+...+aNxnxn-1...x1=0給定上述方程（也就是給定了自變量個數(shù)n和各個位置上的系數(shù)ai），求其根向量中1的個數(shù)為k的根的總數(shù)上述的加減乘和相等都是在模2的意義上進行的。n<26例如，對于方程1+1x1+0x2+1x2x1=0，其根向量中1的個數(shù)為1的數(shù)量是1，對應的向量是(1,0)第二十二頁，共二十九頁，編輯于2023年，星期五9.2窮舉法求解a0+a1x1+a2x2+a3x2x1+a4x3+a5x3x1+a6x3x2+a7x3x2x1+...+aNxnxn-1...x1=0N和n之間存在關系：N=2n含有k個1的解共有C(n,k)個，每個需要用O(k)的時間獲得。對每個可能的解，要進行驗證，需要進行乘和加的運算，需要計算N*n次窮舉法解決此問題的復雜度為O(knNC(n,k))第二十三頁，共二十九頁，編輯于2023年，星期五9.3問題分析a0+a1x1+a2x2+a3x2x1+a4x3+a5x3x1+a6x3x2+a7x3x2x1+...+aNxnxn-1...x1

可以改寫成：a0+a1x1+a2x2+a3x2x1+a4x3+a5x3x1+a6x3x2+a7x3x2x1+...+aN/2xn-1...x1+xn(aN/2+1+aN/2+2x1+aN/2+3x2+aN/2+4x2x1+…+aNxn-1...x1)把xn分為2種情況：值是0與值是1當xn的值確定之后，就會構造出規(guī)模更小的方程第二十四頁，共二十九頁，編輯于2023年，星期五9.4遞歸方程a0+a1x1+a2x2+a3x2x1+a4x3+a5x3x1+a6x3x2+a7x3x2x1+...+aN/2xn-1...x1+xn(aN/2+1+aN/2+2x1+aN/2+3x2+aN/2+4x2x1+…+aNxn-1...x1)當xn為0時，原方程化為：a0+a1x1+a2x2+a3x2x1+a4x3+a5x3x1+a6x3x2+a7x3x2x1+...+aN/2xn-1...x1=0當xn為1時，原方程化為：b0+b1x1+b2x2+b3x2x1+b4x3+b5x3x1+b6x3x2+b7x3x2x1+...+bN/2xn-1...x1=0，其中b0=a0+aN/2+1,b1=a1+aN/2+2,……于是原問題的解T(f,n,k)=T(g,n-1,k)+T(h,n-1,k-1)第二十五頁，共二十九頁，編輯于2023年，星期五9.5該問題對應用分治法的啟示注意終止項：該問題的終止項為T(0=0,0,0)和T(1=0,0,0)顯然前者的值為1，后者的值為0要注意觀察可以采用遞歸、分治的條件：大規(guī)模的問題和小規(guī)模的問題同構或類似第二十六頁，共二十九頁，編輯于2023年，星期五9.6復雜度分析復雜度函數(shù)遞歸方程：用分治法求解二進制方程的時間復雜度是O(nlogn)–因為a=c=2用分治法求解二進制方程的最大空間使用是O(logn)–因為兩個新方程所占空間恰好可以被原方程的空間容納上式中，n/2用于分，2f(n/2)用于治第二十七頁，共二十九頁，編輯于2023年，星期五10.減治減治是分治的特殊情況，即：原問題分成若干個子問題后，原問題的解