算法設計和分析分治法

1、關于算法設計與分析分治法第一張，PPT共六十二頁，創(chuàng)作于2022年6月2subproblem 2 of size n/2subproblem 1 of size n/2a solution to subproblem 2a problem of size na solution to subproblem 1a solution tothe original problem分治法的基本思想第二張，PPT共六十二頁，創(chuàng)作于2022年6月3分治法的基本思想 將規(guī)模為N的問題分解為k個規(guī)模較小的子問題,使這些子問題相互獨立可分別求解,再將k個子問題的解合并成原問題的解.如子問題的規(guī)模仍很大,則反復分

2、解直到問題小到可直接求解為止。 在分治法中,子問題的解法通常與原問題相同,自然導致遞歸過程。第三張，PPT共六十二頁，創(chuàng)作于2022年6月4一個簡單的例子：N個數字求和，如何用分治法解決？是不是分治法一定比蠻力法高效呢？串行計算并行計算通過分治法解決大問題的時間等于所有解決小問題的時間？ T(n)=aT(n/b)+f(n)劃分為規(guī)模為n/b的小問題a個小問題解決大問題的消耗的時間合并小問題消耗的時間第四張，PPT共六十二頁，創(chuàng)作于2022年6月5T(n)=aT(n/b)+f(n)遞推式的解法直接使用公式寫出分治法解決n個數字相加問題的效率類型，設每次分為2個子問題第五張，PPT共六十二頁，創(chuàng)作

3、于2022年6月6本章解決的問題：排序查找大整數乘法矩陣乘法最近對凸包二叉樹遍歷第六張，PPT共六十二頁，創(chuàng)作于2022年6月74.1 合并排序 問題： 將n個元素排成非遞減順序。思考如何使用分治法將大問題分成小問題？第七張，PPT共六十二頁，創(chuàng)作于2022年6月8思想83297154123456788329238914577154832938291745832971547154分合第八張，PPT共六十二頁，創(chuàng)作于2022年6月9算法思路： 若n為1,算法終止;否則,將n個待排元素分割成k(k=2)個大致相等子集合A、B,對每一個子集合分別遞歸排序,再將排好序的子集歸并為一個集合。第九張，PP

4、T共六十二頁，創(chuàng)作于2022年6月10合并排序的遞歸算法算法 MergeSort(A0.n-1 ) / 輸入：未排序序列A0.n-1 / 輸出：已排序序列A0.n-1 if n 1 copy A0.n/2-1 to B0.n/2-1 copy An/2.n-1 to C0.n/2-1 MergeSort( B ) MergeSort( C ) Merge( B,C,A ) 當前n規(guī)模的問題，分成2個子問題以同樣的方式解決子問題用歸并排序，形成最終的有序數組第十張，PPT共六十二頁，創(chuàng)作于2022年6月11Merge(B,C,A)是將有序數組B、C合并為有序數組A的算法。稱為歸并排序歸并排序示例

5、：1 3 4 9 13 34 672 5 61234569 13 34 67B數組C數組第十一張，PPT共六十二頁，創(chuàng)作于2022年6月12前提：數組B及數組C已經有序。 比較數組B的第一個記錄與數組C的第一個記錄將KEY值小者輸出至數組A，再從相應數組讀進一個記錄，替代已被輸出的記錄，再繼續(xù)比較。結束：直至有一個數組的記錄已被窮盡，然后再將未窮盡的數組上的所有記錄拷貝到輸出數組A上。第十二張，PPT共六十二頁，創(chuàng)作于2022年6月13Merge(B0.p-1,C0.q-1,A0.p+q-1) i=0,j=0,k=0; while ip and j 1 copy A0.n/2-1 to B0.

6、n/2-1 copy An/2.n-1 to C0.n/2-1 MergeSort( B ) MergeSort( C ) Merge( B,C,A ) 基本操作？似乎較難判斷。寫出總體工作量表達式。設n=2k, 總工作量表示為：C(n)=(1次除法)+2Ccopy(n/2)+2C(n/2)+Cmerge(n)C(1)=0第十四張，PPT共六十二頁，創(chuàng)作于2022年6月15 簡寫為 C(n)=2C(n/2)+Cmerge(n)+kn基本操作比較？拷貝？(比較的次數不會大于拷貝的次數)是否和其他因素相關？最壞情況如何？歸并排序的效率Cmerge(n)=n,C (n)=2C(n/2)+sn解得 C

7、(n)=nlog2n-n+1(nlog2n)C(n)=(1次除法)+2Ccopy(n/2)+2C(n/2)+Cmerge(n)第十五張，PPT共六十二頁，創(chuàng)作于2022年6月16合并排序結論最壞情況(nlog2n)優(yōu)點：合并排序在最壞情況下的鍵值比較次數十分接近于任何基于比較的排序算法在理論上能夠達到的最少次數合并排序精確解Cworst(n)=nlog2n-n+1理論最小值nlog2n-1.44n向上取整缺點：需要線性的額外空間，體現在何處？雖然合并也可做到“在位”，但導致算法過于復雜。第十六張，PPT共六十二頁，創(chuàng)作于2022年6月174.2 快速排序算法思路: 對于輸入A0. n-1，按以

8、下三個步驟進行排序：(1)分區(qū):取A中的一個元素為支點(pivot) 將A0.n-1劃分成3段: A0.s-1, As , As+1.n-1, 使得 A0.s-1中任一元素As, As+1.n-1中任一元素 As; 下標s 在劃分過程中確定。(2)遞歸求解:遞歸調用快速排序法分別對A0.s-1和As+1.n-1排序。(3)合并:合并A0.s-1, As, As+1.n-1為A0.n-1第十七張，PPT共六十二頁，創(chuàng)作于2022年6月1849 38 65 97 13 27 一趟排序后27 38 13 4976 97 65分別快排132738 657697第十八張，PPT共六十二頁，創(chuàng)作于2022

9、年6月19快速排序算法 QuickSort(Al.r) / 使用快速排序法對序列或者子序列排序 / 輸入：子序列Al.r或者序列本身A0.n-1 / 輸出：非遞減序列A if l r s Partition( Al.r ) QuickSort( Al.s-1 ) QuickSort( As+1.r ) /s是中軸元素/基準點，是數組分區(qū)位置的標志中軸元素如何選？選好中軸后如何掃描數組形成分區(qū)？找到分裂點s，分區(qū)按同樣的方法處理子區(qū)間第十九張，PPT共六十二頁，創(chuàng)作于2022年6月20分區(qū)的例子（雙向掃描）初始數組 A0.n-1=5, 3, 1, 9, 8, 2, 4, 7, 取元素A0=5作為

10、分裂點, 紅色表示i上的元素，藍色表示j上的元素 位置i 0 1 2 3 4 5 6 7 5 3 1 9 8 2 4 7 i，j上的元素和分裂點比較并移動 對于i遇到比分裂點大或等于時停止 對于j遇到比分裂點小或等于時停止 5 3 1 9 8 2 4 7 停止后，ij 交換分裂點和Aj i=j Ai= Aj=分裂點上的值 5 3 1 4 8 2 9 7 交換后，i加1，j減1 5 3 1 4 8 2 9 7 繼續(xù)前面的比較和移動 5 3 1 4 2 8 9 7 5 3 1 4 2 8 9 7 ij 交換分裂點和Aj 2 3 1 4 5 8 9 7 一次分區(qū)完成 第二十張，PPT共六十二頁，創(chuàng)作

11、于2022年6月21數組的分區(qū)算法：算法 Partition( Al.r ) / 輸入：子數組Al.r / 輸出：分裂點/基準點pivot的位置 p Ali l; j r+1 repeat repeati i + 1until Ai p repeat j j 1 until Aj p swap( Ai, Aj ) until i j swap( Ai, Aj ) swap( Al, Aj ) return j第二十一張，PPT共六十二頁，創(chuàng)作于2022年6月22快速排序效率分析if l r s Partition( Al.r ) QuickSort( Al.s-1 ) QuickSort( A

12、s+1.r )基本操作？似乎較難判斷。寫出總體工作量表達式。C(n)=Cpartition(n)+CQuickSort(s前面)+ CQuickSort(s后面)第二十二張，PPT共六十二頁，創(chuàng)作于2022年6月23C(n)=Cpartition(n)+CQuickSort(s前面)+ CQuickSort(s后面)上式依賴于s的位置?？紤]partition的基本操作：比較一次分區(qū)算法的比較次數是否和其他因素相關對于一次長度為n的數組的分區(qū)算法，如果出現指針交叉，所執(zhí)行的比較是n+1次，為什么？相等，比較次數為n次第二十三張，PPT共六十二頁，創(chuàng)作于2022年6月24整個算法的最壞情況下： 在

13、進行了n+1次比較后建立了分區(qū)，還會對數組進行排序，繼續(xù)到最后一個子數組An-2.n-1?？偙容^次數為： Cworst(n) =(n+1)+n+3 =(n+2)(n+1)/2-3 (n2)第二十四張，PPT共六十二頁，創(chuàng)作于2022年6月25最好情況每次分區(qū)執(zhí)行n次并且每次都是等分Cbest(n)=2Cbest(n/2)+n (nlog2n)第二十五張，PPT共六十二頁，創(chuàng)作于2022年6月26平均情況分裂點有可能在一次分區(qū)后出現在每個位置設概率是1/n第二十六張，PPT共六十二頁，創(chuàng)作于2022年6月274.1-4.2 結論合并排序最差(nlog2n)快速排序最優(yōu)(nlog2n) 最差(n2

14、) 平均(1.38nlog2n)選擇排序(n2)冒泡排序(n2)第二十七張，PPT共六十二頁，創(chuàng)作于2022年6月284.3 折半查找(有序數組)位置：0 1 2 3 4 5 6 7 8 9 10 11 12值： 3,14,27,31,39,42,55,70,74,81,85,93,98K=70 迭代1 l=0 m=6 r=12迭代2 l m=9 r迭代3 l r結果 m= (7+8)/2=7第二十八張，PPT共六十二頁，創(chuàng)作于2022年6月29 BinarySearch( A0.n-1, k ) / 輸入：已排序大小為n的序列A，待搜索對象k / 輸出：如果搜索成功，則返回k的位置，否則返回

15、-1 l=0,r=n-1; While lr mid= (l+r)/2 if k = Amid return mid else if k Amid r=m-1 else l=m+1 return -1 折半查找偽代碼第二十九張，PPT共六十二頁，創(chuàng)作于2022年6月30折半查找效率分析： 基本操作：比較 最壞情況下，比較次數 C(n)=C( n/2)+1 C(1)=1 設n=2k，可解得 C(n)=k+1=log2n+1于是 C(n)(log2n)第三十張，PPT共六十二頁，創(chuàng)作于2022年6月314.3 結論折半查找 最差(log2n)順序查找 (n)是一種退化了的分治法第三十一張，PPT共

16、六十二頁，創(chuàng)作于2022年6月324.4 二叉樹遍歷及其相關特性 所謂二叉樹的遍歷指的是遵循某一種次序來訪問二叉樹上的所有結點，使得樹中每一個結點被訪問了一次且只訪問一次。 由于二叉樹是一種非線性結構，樹中的結點可能有不止一個的直接后繼結點，所以遍歷以前必須先規(guī)定訪問的次序。 第三十二張，PPT共六十二頁，創(chuàng)作于2022年6月33中序遍歷（Inorder Traversal）二叉樹的中序遍歷算法比較簡單，使用遞歸的策略。在遍歷以前首先確定遍歷的樹是否為空，如果為空，則直接返回；否則中序遍歷的算法步驟如下： （1）對左子樹L執(zhí)行中序遍歷算法 （2）訪問輸出根結點V的值。 （3）對右子樹R執(zhí)行中序

17、遍歷算法。 第三十三張，PPT共六十二頁，創(chuàng)作于2022年6月34前序遍歷（Preorder Traversal）有了上面的中序遍歷的過程，前序遍歷也是類似的。在遍歷以前首先確定遍歷的樹是否為空，如果為空，則直接返回；否則前序遍歷的算法步驟如下： （1）訪問輸出根結點V的值； （2）對左子樹L執(zhí)行前序遍歷算法。 （3）對右子樹R執(zhí)行前序遍歷算法。 第三十四張，PPT共六十二頁，創(chuàng)作于2022年6月35前序遍歷執(zhí)行過程圖第三十五張，PPT共六十二頁，創(chuàng)作于2022年6月36二叉樹的構造第三十六張，PPT共六十二頁，創(chuàng)作于2022年6月37二叉樹的高度計算算法 Height(T) /輸入一棵二叉樹

18、T /輸出二叉樹的高度 /二叉樹高度定義：葉子到樹根的最長路徑 if T= return -1 else return maxHeight(L), Height(R)+1例：計算上例中二叉樹的高度 H(T)=1+maxH(2),H(6)=2+maxH(3),H(4) =3+H(5)=5第三十七張，PPT共六十二頁，創(chuàng)作于2022年6月384.5 大整數乘法和Strassen矩陣乘法整數乘法問題: 設A和B為兩個N位的整數，計算它們的乘積A B。思考按照通常做法要執(zhí)行一位乘法多少次？如：234 125 1170 468 234 * * * * *N2次。第三十八張，PPT共六十二頁，創(chuàng)作于202

19、2年6月39分治法如何體現。令N為偶數，則A和B可表示為其中a1和a2分別為A的前半部和后半部。Aa110N/2+a2 (123456=123106/2+456)Bbl10N/2+b2 bl 和b2則分別為B的前半部和后半部。如果按下述方法得到積(多項式相乘) AB=(a110n/2+a2)(b110n/2+b2) =a1b110n+(a1b2+a2b1)10n/2+a2b2第三十九張，PPT共六十二頁，創(chuàng)作于2022年6月40AB=(a110n/2+a2)(b110n/2+b2)=a1b110n+(a1b2+a2b1)10n/2+a2b2估算時間效率是多少(即需要多少次一位乘法)？則要4次N

20、/2位乘法，即N2次一位乘法。因此這種方法沒有改進原來的方法。第四十張，PPT共六十二頁，創(chuàng)作于2022年6月41改進的乘法AB=(a110n/2+a2)(b110n/2+b2) =a1b110n+(a1b2+a2b1)10n/2+a2b2 =a1b110n+(a1+a2)(b1+b2)-a1b1-a2b2)10n/2+a2b2此時需要乘法多少次？ 這種方法需要3次n/2位的乘法及一些加減法。 記C(n)為計算兩個n位整數相乘所需的基本操作執(zhí)行次數，則第四十一張，PPT共六十二頁，創(chuàng)作于2022年6月42有 C(n)=3C(n/2)+kn C(1)=1 其中，k為常數，KN表示加法、減法所需時

21、間與N成正比。 解此遞歸方程，得 C(n)=nlog3+2knlog3-2kn O(nlog3) O(n1.58) 可見，乘法效率有改善。第四十二張，PPT共六十二頁，創(chuàng)作于2022年6月43評價其原理在于乘法操作所需時間比加法多得多，因此減少乘法次數，雖然代價為增加加法運算，總的效果還是加速了運算.大整數(500比特或1024比特)的乘法用于加密和認證.第四十三張，PPT共六十二頁，創(chuàng)作于2022年6月442、 Strassen矩陣乘法矩陣乘法是線性代數中最常見的運算之一，它在數值計算中有廣泛的應用。若A和B是2個nn的矩陣，則它們的乘積C=AB同樣是一個nn的矩陣。A和B的乘積矩陣C中的元

22、素Ci,j定義為:若依此定義來計算A和B的乘積矩陣C，則每計算C的一個元素Ci,j，加法和乘法的次數是多少？需要做n個乘法和n-1次加法。因此，求出矩陣C的n2個元素所需的計算時間為O(n3)。第四十四張，PPT共六十二頁，創(chuàng)作于2022年6月45Strassen矩陣乘法如何對矩陣乘法采用分治？首先，假設n=2k。將矩陣A，B和C中每一矩陣都分塊成為4個大小相等的子矩陣，每個子矩陣都是n/2n/2的方陣。由此可將方程C=AB重寫為:第四十五張，PPT共六十二頁，創(chuàng)作于2022年6月46Strassen矩陣乘法其中： C11 C12 C21 C22 是多少？ C11=A11B11+A12B21

23、C12=A11B12+A12B22 C21=A21B11+A22B21 C22=A21B12+A22B22 第四十六張，PPT共六十二頁，創(chuàng)作于2022年6月47 C11=A11B11+A12B21 C12=A11B12+A12B22 C21=A21B11+A22B21 C22=A21B12+A22B22依此算法，計算2個n階方陣的乘積轉化為計算8個n/2階方陣的乘積和4個n/2階方陣的加法上述分治法的計算時間耗費T(n)如何寫？T(n)=8T(n/2)+cn2 T(1)=1計算T(n)是多少？這個遞歸方程的解仍然屬于O(n3) 第四十七張，PPT共六十二頁，創(chuàng)作于2022年6月48Stras

24、sen方法 M1=A11(B12-B22) M2=(A11+A12)B22 M3=(A21+A22)B11 M4=A22(B21-B11) M5=(A11+A22)(B11+B22) M6=(A12-A22)(B21+B22) M7=(A11-A21)(B11+B12)他的算法只用了7次乘法運算，但增加了加、減法的運算次數10次。觀察使用了多少次乘法?加減法用了多少次？第四十八張，PPT共六十二頁，創(chuàng)作于2022年6月49 于是可得到: C11=M5+M4-M2+M6 C12=M1+M2 C21=M3+M4 C22=M5+M1-M3-M7 引入8次加減法Strassen矩陣乘積分治算法中，用了

25、7次對于n/2階矩陣乘積的遞歸調用和18次n/2階矩陣的加減運算。由此可知，該算法的所需的計算時間T(n)滿足如下的遞歸方程: 第四十九張，PPT共六十二頁，創(chuàng)作于2022年6月50Strassen矩陣乘法其解為T(n)O(nlog7)O(n2.81)。由此可見，Strassen矩陣乘法的計算時間復雜性比普通矩陣乘法有階的改進。 T(n)=7T(n/2)+kn2 T(1)=1第五十張，PPT共六十二頁，創(chuàng)作于2022年6月51結論大整數乘法和矩陣乘法分別利用了將乘法轉換為多個加法進行替代。對于矩陣乘法可以將矩陣作3 3的劃分，即將矩陣分成九個子矩陣，或作 4 4的劃分(即將矩陣分成十六個子矩陣

26、)。相應地要求矩陣的階n是3的整次冪(或4的整次冪)。有人沿這個途徑改善了矩陣乘法的復雜度。第五十一張，PPT共六十二頁，創(chuàng)作于2022年6月524.6 分治法解最近點對問題和凸包問題問題: 給定平面S上n個點,找其中的一對點,使得在n(n-1)/2個點對中, 該點對的距離最小。算法思路: 1) n較小時直接求(n=2). 2) 將S上的n個點分成大致相等的2個子集S1和S2 3) 分別求S1和S2中的最接近點對 4) 求一點在S1、另一點在S2中的最近點對 5) 從上述三對點中找距離最近的一對.第五十二張，PPT共六十二頁，創(chuàng)作于2022年6月53 2) 將S上的n個點分成大致相等的2個子集S1和S2如何分？將點按照x軸升序排序畫一條垂直線x=c第五十三張，PPT共六十二頁，創(chuàng)作于2022年6月543) 遞歸求S1和