算法設(shè)計與分析分治法

關(guān)于算法設(shè)計與分析分治法2subproblem2ofsizen/2subproblem1ofsizen/2asolutiontosubproblem2aproblemofsizenasolutiontosubproblem1asolutiontotheoriginalproblem分治法的基本思想第2頁,共62頁，2024年2月25日，星期天3分治法的基本思想

將規(guī)模為N的問題分解為k個規(guī)模較小的子問題,使這些子問題相互獨立可分別求解,再將k個子問題的解合并成原問題的解.如子問題的規(guī)模仍很大,則反復分解直到問題小到可直接求解為止。在分治法中,子問題的解法通常與原問題相同,自然導致遞歸過程。第3頁,共62頁，2024年2月25日，星期天4一個簡單的例子：N個數(shù)字求和，如何用分治法解決？是不是分治法一定比蠻力法高效呢？串行計算并行計算通過分治法解決大問題的時間等于所有解決小問題的時間？T(n)=aT(n/b)+f(n)劃分為規(guī)模為n/b的小問題a個小問題解決大問題的消耗的時間合并小問題消耗的時間第4頁,共62頁，2024年2月25日，星期天5T(n)=aT(n/b)+f(n)遞推式的解法直接使用公式寫出分治法解決n個數(shù)字相加問題的效率類型，設(shè)每次分為2個子問題第5頁,共62頁，2024年2月25日，星期天6本章解決的問題：排序查找大整數(shù)乘法矩陣乘法最近對凸包二叉樹遍歷第6頁,共62頁，2024年2月25日，星期天74.1合并排序

問題：

將n個元素排成非遞減順序。思考如何使用分治法將大問題分成小問題？第7頁,共62頁，2024年2月25日，星期天8思想83297154123456788329238914577154832938291745832971547154分合第8頁,共62頁，2024年2月25日，星期天9算法思路：

若n為1,算法終止;否則,將n個待排元素分割成k(k=2)個大致相等子集合A、B,對每一個子集合分別遞歸排序,再將排好序的子集歸并為一個集合。第9頁,共62頁，2024年2月25日，星期天10合并排序的遞歸算法算法MergeSort(A[0..n-1])//輸入：未排序序列A[0..n-1]//輸出：已排序序列A[0..n-1]ifn>1copyA[0..n/2-1]toB[0..n/2-1]copyA[n/2..n-1]toC[0..n/2-1]MergeSort(B)MergeSort(C)

Merge(B,C,A)

當前n規(guī)模的問題，分成2個子問題以同樣的方式解決子問題用歸并排序，形成最終的有序數(shù)組第10頁,共62頁，2024年2月25日，星期天11Merge(B,C,A)是將有序數(shù)組B、C合并為有序數(shù)組A的算法。稱為歸并排序歸并排序示例：13491334672561234569133467B數(shù)組C數(shù)組第11頁,共62頁，2024年2月25日，星期天12前提：數(shù)組B及數(shù)組C已經(jīng)有序。

比較數(shù)組B的第一個記錄與數(shù)組C的第一個記錄將KEY值小者輸出至數(shù)組A，再從相應數(shù)組讀進一個記錄，替代已被輸出的記錄，再繼續(xù)比較。結(jié)束：直至有一個數(shù)組的記錄已被窮盡，然后再將未窮盡的數(shù)組上的所有記錄拷貝到輸出數(shù)組A上。第12頁,共62頁，2024年2月25日，星期天13Merge(B[0..p-1],C[0..q-1],A[0..p+q-1])i=0,j=0,k=0;whilei<pandj<qdoifB[i]≤C[j]A[k]=B[i],i=i+1elseA[k]=C[j],j=j+1k=k+1ifi=pcopyC[j..q-1]toA[k..p+q-1]elsecopyB[i..p-1]toA[0..p+q-1]定義各數(shù)組的指針B，C數(shù)組都沒處理完比較，輸出小的值到A；且輸出值的數(shù)組指針后移若因為B數(shù)組結(jié)束，跳出循環(huán)將C數(shù)組剩下的全部放入A數(shù)組第13頁,共62頁，2024年2月25日，星期天14合并排序的效率分析ifn>1copyA[0..n/2-1]toB[0..n/2-1]copyA[n/2..n-1]toC[0..n/2-1]MergeSort(B)MergeSort(C)

Merge(B,C,A)

基本操作？？似乎較難判斷。寫出總體工作量表達式。設(shè)n=2k,總工作量表示為：C(n)=(1次除法)+2Ccopy(n/2)+2C(n/2)+Cmerge(n)C(1)=0第14頁,共62頁，2024年2月25日，星期天15

簡寫為C(n)=2C(n/2)+Cmerge(n)+kn基本操作比較？拷貝？(比較的次數(shù)不會大于拷貝的次數(shù))是否和其他因素相關(guān)？最壞情況如何？歸并排序的效率Cmerge(n)=n,C

(n)=2C(n/2)+sn解得C(n)=nlog2n-n+1∈Θ(nlog2n)C(n)=(1次除法)+2Ccopy(n/2)+2C(n/2)+Cmerge(n)第15頁,共62頁，2024年2月25日，星期天16合并排序結(jié)論最壞情況Θ(nlog2n)優(yōu)點：合并排序在最壞情況下的鍵值比較次數(shù)十分接近于任何基于比較的排序算法在理論上能夠達到的最少次數(shù)合并排序精確解Cworst(n)=nlog2n-n+1理論最小值nlog2n-1.44n向上取整缺點：需要線性的額外空間，體現(xiàn)在何處？雖然合并也可做到“在位”，但導致算法過于復雜。第16頁,共62頁，2024年2月25日，星期天174.2快速排序算法思路:對于輸入A[0..n-1]，按以下三個步驟進行排序：(1)分區(qū):取A中的一個元素為支點(pivot)將A[0..n-1]劃分成3段:A[0..s-1],A[s],A[s+1..n-1],使得

A[0..s-1]中任一元素

A[s],A[s+1..n-1]中任一元素

A[s];下標s在劃分過程中確定。(2)遞歸求解:遞歸調(diào)用快速排序法分別對A[0..s-1]和A[s+1..n-1]排序。(3)合并:合并A[0..s-1],A[s],A[s+1..n-1]為A[0..n-1]第17頁,共62頁，2024年2月25日，星期天18493865971327一趟排序后{273813}49{769765}分別快排{13}27{38}{65}76{97}第18頁,共62頁，2024年2月25日，星期天19快速排序算法QuickSort(A[l..r])//使用快速排序法對序列或者子序列排序//輸入：子序列A[l..r]或者序列本身A[0..n-1]//輸出：非遞減序列Aifl<r

s←Partition(A[l..r]) QuickSort(A[l..s-1]) QuickSort(A[s+1..r])

//s是中軸元素/基準點，是數(shù)組分區(qū)位置的標志中軸元素如何選？選好中軸后如何掃描數(shù)組形成分區(qū)？找到分裂點s，分區(qū)按同樣的方法處理子區(qū)間第19頁,共62頁，2024年2月25日，星期天20分區(qū)的例子（雙向掃描）初始數(shù)組A[0..n-1]=[5,3,1,9,8,2,4,7],

取元素A[0]=5作為分裂點,紅色表示i上的元素，藍色表示j上的元素

位置i01234567

5

3198247i，j上的元素和分裂點比較并移動對于i遇到比分裂點大或等于時停止對于j遇到比分裂點小或等于時停止53198247停止后，i<j交換A[i]和A[j]i>j交換分裂點和A[j]i=jA[i]=A[j]=分裂點上的值53148297交換后，i加1，j減153148

297繼續(xù)前面的比較和移動

53142

897

53142

897i>j交換分裂點和A[j]

2314

5

897

一次分區(qū)完成

第20頁,共62頁，2024年2月25日，星期天21數(shù)組的分區(qū)算法：算法Partition(A[l..r])//輸入：子數(shù)組A[l..r]

//輸出：分裂點/基準點pivot的位置p←A[l]

i←l;j←r+1

repeat

repeat

i←i+1

untilA[i]≥prepeatj←j–1untilA[j]≤pswap(A[i],A[j])untili≥j

swap(A[i],A[j])

swap(A[l],A[j])returnj第21頁,共62頁，2024年2月25日，星期天22快速排序效率分析ifl<r

s←Partition(A[l..r]) QuickSort(A[l..s-1]) QuickSort(A[s+1..r])

基本操作？？似乎較難判斷。寫出總體工作量表達式。C(n)=Cpartition(n)+CQuickSort(s前面)+CQuickSort(s后面)第22頁,共62頁，2024年2月25日，星期天23C(n)=Cpartition(n)+CQuickSort(s前面)+CQuickSort(s后面)上式依賴于s的位置。考慮partition的基本操作：比較一次分區(qū)算法的比較次數(shù)是否和其他因素相關(guān)對于一次長度為n的數(shù)組的分區(qū)算法，如果出現(xiàn)指針交叉，所執(zhí)行的比較是n+1次，為什么？相等，比較次數(shù)為n次第23頁,共62頁，2024年2月25日，星期天24整個算法的最壞情況下：在進行了n+1次比較后建立了分區(qū)，還會對數(shù)組進行排序，繼續(xù)到最后一個子數(shù)組A[n-2..n-1]?？偙容^次數(shù)為：Cworst(n)=(n+1)+n+…+3=(n+2)(n+1)/2-3∈Θ(n2)第24頁,共62頁，2024年2月25日，星期天25最好情況每次分區(qū)執(zhí)行n次并且每次都是等分Cbest(n)=2Cbest(n/2)+n∈Θ(nlog2n)第25頁,共62頁，2024年2月25日，星期天26平均情況分裂點有可能在一次分區(qū)后出現(xiàn)在每個位置設(shè)概率是1/n第26頁,共62頁，2024年2月25日，星期天274.1-4.2結(jié)論合并排序最差Θ(nlog2n)快速排序最優(yōu)Θ(nlog2n)最差Θ(n2)平均Θ(1.38nlog2n)選擇排序 Θ(n2)冒泡排序 Θ(n2)第27頁,共62頁，2024年2月25日，星期天284.3折半查找(有序數(shù)組)位置：0123456789101112值：3,14,27,31,39,42,55,70,74,81,85,93,98K=70↑↑↑迭代1l=0m=6r=12迭代2lm=9r迭代3lr結(jié)果m=(7+8)/2=7第28頁,共62頁，2024年2月25日，星期天29

BinarySearch(A[0..n-1],k)//輸入：已排序大小為n的序列A，待搜索對象k//輸出：如果搜索成功，則返回k的位置，否則返回-1l=0,r=n-1;Whilel≤r mid=(l+r)/2 ifk=A[mid]returnmid elseifk<A[mid]r=m-1 elsel=m+1return-1

折半查找偽代碼第29頁,共62頁，2024年2月25日，星期天30折半查找效率分析：基本操作：比較

最壞情況下，比較次數(shù)C(n)=C(n/2)+1C(1)=1設(shè)n=2k，可解得

C(n)=k+1=log2n+1于是

C(n)∈Θ(log2n)第30頁,共62頁，2024年2月25日，星期天314.3結(jié)論折半查找最差Θ(log2n)順序查找 Θ(n)是一種退化了的分治法第31頁,共62頁，2024年2月25日，星期天324.4二叉樹遍歷及其相關(guān)特性所謂二叉樹的遍歷指的是遵循某一種次序來訪問二叉樹上的所有結(jié)點，使得樹中每一個結(jié)點被訪問了一次且只訪問一次。由于二叉樹是一種非線性結(jié)構(gòu)，樹中的結(jié)點可能有不止一個的直接后繼結(jié)點，所以遍歷以前必須先規(guī)定訪問的次序。第32頁,共62頁，2024年2月25日，星期天33中序遍歷（InorderTraversal）二叉樹的中序遍歷算法比較簡單，使用遞歸的策略。在遍歷以前首先確定遍歷的樹是否為空，如果為空，則直接返回；否則中序遍歷的算法步驟如下：（1）對左子樹L執(zhí)行中序遍歷算法（2）訪問輸出根結(jié)點V的值。（3）對右子樹R執(zhí)行中序遍歷算法。第33頁,共62頁，2024年2月25日，星期天34前序遍歷（PreorderTraversal）有了上面的中序遍歷的過程，前序遍歷也是類似的。在遍歷以前首先確定遍歷的樹是否為空，如果為空，則直接返回；否則前序遍歷的算法步驟如下：（1）訪問輸出根結(jié)點V的值；（2）對左子樹L執(zhí)行前序遍歷算法。（3）對右子樹R執(zhí)行前序遍歷算法。

第34頁,共62頁，2024年2月25日，星期天35前序遍歷執(zhí)行過程圖第35頁,共62頁，2024年2月25日，星期天36二叉樹的構(gòu)造第36頁,共62頁，2024年2月25日，星期天37二叉樹的高度計算算法Height(T)//輸入一棵二叉樹T//輸出二叉樹的高度//二叉樹高度定義：葉子到樹根的最長路徑ifT=φreturn-1elsereturnmax{Height(L),Height(R)}+1例：計算上例中二叉樹的高度

H(T)=1+max{H(2),H(6)}=2+max{H(3),H(4)}=3+H(5)=5第37頁,共62頁，2024年2月25日，星期天384.5大整數(shù)乘法和Strassen矩陣乘法整數(shù)乘法問題:設(shè)A和B為兩個N位的整數(shù)，計算它們的乘積A·B。思考按照通常做法要執(zhí)行一位乘法多少次？如：234×1251170468＋234*****N2次。第38頁,共62頁，2024年2月25日，星期天39分治法如何體現(xiàn)。令N為偶數(shù)，則A和B可表示為其中a1和a2分別為A的前半部和后半部。A＝a1·10N/2+a2(123456=123·106/2+456)B＝bl·10N/2+b2

bl

和b2則分別為B的前半部和后半部。如果按下述方法得到積(多項式相乘)A·B=(a110n/2+a2)(b110n/2+b2)=a1b110n+(a1b2+a2b1)10n/2+a2b2第39頁,共62頁，2024年2月25日，星期天40A·B=(a110n/2+a2)(b110n/2+b2)=a1b110n+(a1b2+a2b1)10n/2+a2b2估算時間效率是多少(即需要多少次一位乘法)？則要4次N/2位乘法，即N2次一位乘法。因此這種方法沒有改進原來的方法。第40頁,共62頁，2024年2月25日，星期天41改進的乘法A·B=(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位整數(shù)相乘所需的基本操作執(zhí)行次數(shù)，則第41頁,共62頁，2024年2月25日，星期天42有

C(n)=3C(n/2)+k·nC(1)=1其中，k為常數(shù)，KN表示加法、減法所需時間與N成正比。解此遞歸方程，得

C(n)=nlog3+2knlog3-2kn∈O(nlog3)≈O(n1.58)可見，乘法效率有改善。第42頁,共62頁，2024年2月25日，星期天43評價其原理在于乘法操作所需時間比加法多得多，因此減少乘法次數(shù)，雖然代價為增加加法運算，總的效果還是加速了運算.大整數(shù)(500比特或1024比特)的乘法用于加密和認證.第43頁,共62頁，2024年2月25日，星期天442、Strassen矩陣乘法矩陣乘法是線性代數(shù)中最常見的運算之一，它在數(shù)值計算中有廣泛的應用。若A和B是2個n×n的矩陣，則它們的乘積C=A×B同樣是一個n×n的矩陣。A和B的乘積矩陣C中的元素C[i,j]定義為:

若依此定義來計算A和B的乘積矩陣C，則每計算C的一個元素C[i,j]，加法和乘法的次數(shù)是多少？需要做n個乘法和n-1次加法。因此，求出矩陣C的n2個元素所需的計算時間為O(n3)。第44頁,共62頁，2024年2月25日，星期天45Strassen矩陣乘法如何對矩陣乘法采用分治？首先，假設(shè)n=2k。將矩陣A，B和C中每一矩陣都分塊成為4個大小相等的子矩陣，每個子矩陣都是n/2×n/2的方陣。由此可將方程C=A×B重寫為:第45頁,共62頁，2024年2月25日，星期天46Strassen矩陣乘法其中：C11C12C21C22是多少？C11=A11B11+A12B21

C12=A11B12+A12B22

C21=A21B11+A22B21

C22=A21B12+A22B22

第46頁,共62頁，2024年2月25日，星期天47

C11=A11B11+A12B21

C12=A11B12+A12B22

C21=A21B11+A22B21

C22=A21B12+A22B22

依此算法，計算2個n階方陣的乘積轉(zhuǎn)化為計算8個n/2階方陣的乘積和4個n/2階方陣的加法上述分治法的計算時間耗費T(n)如何寫？T(n)=8T(n/2)+cn2

T(1)=1計算T(n)是多少？這個遞歸方程的解仍然屬于O(n3)

第47頁,共62頁，2024年2月25日，星期天48Strassen方法

M1=A11(B12-B22)M2=(A11+A12)B22M3=(A21+A22)B11M4=A22(B21-B11)M5=(A11+A22)(B11+B22)M6=(A12-A22)(B21+B22)M7=(A11-A21)(B11+B12)他的算法只用了7次乘法運算，但增加了加、減法的運算次數(shù)10次。觀察使用了多少次乘法?加減法用了多少次？第48頁,共62頁，2024年2月25日，星期天49于是可得到:

C11=M5+M4-M2+M6C12=M1+M2C21=M3+M4C22=M5+M1-M3-M7引入8次加減法Strassen矩陣乘積分治算法中，用了7次對于n/2階矩陣乘積的遞歸調(diào)用和18次n/2階矩陣的加減運算。由此可知，該算法的所需的計算時間T(n)滿足如下的遞歸方程:

第49頁,共62頁，2024年2月25日，星期天50Strassen矩陣乘法

其解為T(n)∈O(nlog7)≈O(n2.81)。由此可見，Strassen矩陣乘法的計算時間復雜性比普通矩陣乘法有階的改進。T(n)=7T(n/2)+kn2

T(1)=1第50頁,共62頁，2024年2月25日，星期天51結(jié)論大整數(shù)乘法和矩陣乘法分別利用了將乘法轉(zhuǎn)換為多個加法進行替代。對于矩陣乘法可以將矩陣作3×3的劃分，即將矩陣分成九個子矩陣，或作4×4的劃分(即將矩陣分成十六個子矩陣)。相應地要求矩陣的階n是3的整次冪(或4的整次冪)。有人沿這個途徑改善了矩陣乘法的復雜度。第51頁,共62頁，2024年2月25日，星期天524.6分治法解最近點對問題和凸包問題問題:給定平面S上n個點,找其中的一對點,使得在n(n-1)/2個點對中,該點對的距離最小。算法思路:1)n較小時直接求(n=2).2)將S上的n個點分成大致相等的2個子集S1和S23)分別求S1和S2中的最接近點對

4)求一點在S1、另一點在S2中的最近點對

5)從上述三