算法設(shè)計(jì)與分析 課件 第三章 分治法

計(jì)算機(jī)算法設(shè)計(jì)與分析第三章

分治法學(xué)習(xí)目標(biāo)掌握分治法的基本思想掌握分治法的特點(diǎn)和基本框架掌握分治法解決實(shí)際問題3.1分治法基本思想孫子兵法兵勢(shì)篇曰：凡治眾如治寡，分?jǐn)?shù)是也。其大致意思就是管理大規(guī)模部隊(duì)和管理小股部隊(duì)是一樣的，分開治理就是了。這就是分治法在軍事上的運(yùn)用。分治法的基本思想就是將一個(gè)較難以解決的規(guī)模大的問題，分割成多個(gè)相似的規(guī)模較小的子問題，先求出小規(guī)模子問題的解，然后將各小規(guī)模子問題的解組合起來就是規(guī)模大的問題的解。其中的一個(gè)關(guān)鍵點(diǎn)是分割的子問題一定要相似，這樣就可以采取同樣的方法來求解，從而將問題簡(jiǎn)化。例3.1

二分查找問題。在一個(gè)升序的含n個(gè)元素的數(shù)組a[]中查找x，輸出x在數(shù)組a中的下標(biāo)位置，若沒查到返回-1。分析：可以考慮使用分治思想來解決，具體做法是設(shè)計(jì)三個(gè)變量left，mid和right將整個(gè)數(shù)組分成3個(gè)部分a[left,mid-1],a[mid],a[mid+1,right]。如果a[mid]>x，則使用相同的辦法在較小范圍[left,mid-1]中查找；如果a[mid]=x，則已查找到，返回mid即可；如果a[mid]<x，則使用相同的辦法在較小范圍[mid+1,right]中查找。以上過程都沒查找到的話，則數(shù)組中不存在x，返回-1。3.1分治法基本思想例3.2

二分歸并排序。將含有n個(gè)元素的數(shù)組a[]按關(guān)鍵字大小升序排列。以數(shù)組a[8]={8,4,5,7,1,3,6,2}為例來分析。3.1分治法基本思想3.2分治法的特點(diǎn)和基本框架當(dāng)采用分治法時(shí)，一般原問題都需要具備以下幾個(gè)特征：（1）難度遞降：即原問題的解決難度，隨著數(shù)據(jù)的規(guī)模的縮小而降低，當(dāng)降低到一定程度時(shí)，問題很容易解決。（2）問題可分：原問題可以分解為若干個(gè)規(guī)模較小的同類型問題，即該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。這是應(yīng)用分治法的前提。（3）解可合并：利用所有子問題的解，可合并出原問題的解。這個(gè)特征很關(guān)鍵，能否利用分治法完全取決于這個(gè)特征。（4）相互獨(dú)立：各個(gè)子問題之間相互獨(dú)立，某個(gè)子問題的求解不會(huì)影響到另一個(gè)子問題。如果子問題之間不獨(dú)立，則分治法需要重復(fù)地解決公共的子問題，造成效率低下的結(jié)果。設(shè)P是要求解的問題，|P|為問題P的輸入規(guī)模，現(xiàn)將分治法求解問題的基本框架描述如下：Divide-and-Conquer(P)：if|P|≤cthenS(P)

//當(dāng)問題規(guī)模較小時(shí)，很容易求出解endifdividePintoP1,P2,...,Pk//將原問題分割為規(guī)模小的子問題fori=1tokdoxi=Divide-and-Conquer(Pi)//遞歸求解每個(gè)子問題endforreturnMerge(x1,x2,...,xk)//將子問題的解合并成原問題的解3.2分治法的特點(diǎn)和基本框架3.3分治法的時(shí)間復(fù)雜度分析分治法的實(shí)現(xiàn)一般都是采用遞歸算法。分析分治法的時(shí)間復(fù)雜度需要使用其遞推公式來推導(dǎo)。分治法中通常的遞推方程有以下兩種類型：第一類是歸約后子問題規(guī)模比原問題規(guī)模呈常數(shù)級(jí)減少。遞推方程為如Hanoi塔問題使用分治法，將n個(gè)圓盤的問移動(dòng)題歸約為兩個(gè)n-1圓盤移動(dòng)子問題，也就是歸約后的子問題規(guī)模只比原問題規(guī)模少1。遞推方程為解得：第二類是歸約后子問題規(guī)模比原問題規(guī)模呈倍數(shù)減少。該算法的時(shí)間復(fù)雜度可以通過以下遞推公式求出：根據(jù)1.4.4節(jié)介紹的MasterTheorem主定理結(jié)論可知：3.3分治法的時(shí)間復(fù)雜度分析3.4.1分治法的典型實(shí)例——快速排序快速排序是數(shù)據(jù)結(jié)構(gòu)中經(jīng)典且高效的一種排序算法，它在實(shí)踐中應(yīng)用非常廣泛。設(shè)待排的數(shù)組為A，快速排序的基本思想為：用數(shù)組的首元素作為標(biāo)準(zhǔn)將A劃分為前、后兩部分，前部分元素都比首元素小，后部分元素都比首元素大，這兩部分就構(gòu)成兩個(gè)新的子問題。算法接著分別對(duì)這兩部分遞歸地進(jìn)行排序，各子問題排序完成后自然整個(gè)數(shù)組也就排序完成。算法的關(guān)鍵在于怎樣劃分?jǐn)?shù)組A而將其歸約成兩個(gè)相同結(jié)構(gòu)的子問題。3.4.1分治法的典型實(shí)例——快速排序快速排序算法Quicksort(A,p,r) //p和r分別為數(shù)組A的首元素和尾元素的下標(biāo)輸入：數(shù)組A[p..r],1≤p≤r≤n輸出：從A[p]到A[r]按照升序排好序的數(shù)組Aifp<rthenq←Partition(A,p,r) //劃分?jǐn)?shù)組，找到首元素A[p]在排好序后的位置qA[p]?A[q] //交換A[p]，A[q]中元素的值Quicksort(A,p,q-1) //對(duì)前部分繼續(xù)遞歸地用快速排序算法Quicksort(A,q+1,r) //對(duì)后部分繼續(xù)遞歸地用快速排序算法endif其算法中的Partition函數(shù)是劃分的過程函數(shù)，它實(shí)現(xiàn)的就是以A[p..r]的首元素A[p]作為標(biāo)準(zhǔn)，輸出q表示A[p]應(yīng)該處在的正確位置，即排好序后A[p]應(yīng)該放在數(shù)組下標(biāo)為q的位置。過程如下：（1）先從后向前掃描數(shù)組A，找到第一個(gè)不大于A[p]的元素A[j]（2）從前向后掃描A找到第一個(gè)大于A[p]的元素A[i]（3）當(dāng)i＜j時(shí)，交換A[i]與A[j]。這時(shí)A[j]后面的元素都大于A[p]，A[i]前面的元素都小于或等于A[p]。（4）接著對(duì)數(shù)組A從i到j(luò)之間的部分繼續(xù)上面的掃描過程，直到i和j相遇，當(dāng)i>j時(shí)，j就代表了A在排好序的數(shù)組中的正確位置q。此刻在q位置之前的元素都不大于A[p]，在q位置后面的元素都大于A[p]。3.4.1分治法的典型實(shí)例——快速排序3.4.1分治法的典型實(shí)例——快速排序劃分算法Partition(A,p,r)輸入：數(shù)組A[p..r],1≤p≤r≤n輸出：數(shù)組首元素A[p]在排好序的數(shù)組中的位置x←A[p]i←pj←r+1whiletruedorepeatj←j-1untilA[j]≤x//從后往前找到不大于x的元素repeati←i+1untilA[i]>x//從前往后找到大于x的元素ifi<jthenA[i]?A[j]//交換A[i]，A[j]中元素的值elsereturnj //i，j相遇，返回相遇的位置即為數(shù)組首元素A[p]的正確位置endifendwhile舉例說明一趟劃分的過程數(shù)組A[6]={64，57，86，42，12，53}，第一趟劃分以64為標(biāo)準(zhǔn)，p=1i=2j=5交換A[2]和A[5]的值，繼續(xù)循環(huán)。j=4i=5i<j不成立，一趟劃分結(jié)束，返回值為4。在Quicksort中q=4,交換A[p]，A[q]中元素的值，就得到一次劃分后的結(jié)果。在一趟快速排序結(jié)束后，繼續(xù)對(duì)兩個(gè)子數(shù)組{12,57,53,42}和{86}實(shí)施相同的操作。3.4.1分治法的典型實(shí)例——快速排序第1次循環(huán)645786421253第2次循環(huán)645753421286劃分后1257534264863.4.2分治法的典型實(shí)例——大整數(shù)乘法1.問題描述采用分治法設(shè)計(jì)一個(gè)有效的算法，計(jì)算兩個(gè)n位大整數(shù)的乘法。（n=2k,k=1,2,3....）。2.問題分析根據(jù)分治法的思想，可以將兩個(gè)大的整數(shù)乘法分而治之。將大整數(shù)按位數(shù)的一半分成兩個(gè)小整數(shù)，轉(zhuǎn)換成稍簡(jiǎn)單的小整數(shù)乘法，再進(jìn)行合并。上述的過程可以重復(fù)進(jìn)行，直到得到最簡(jiǎn)單的兩個(gè)1位數(shù)的乘法，從而解決上述問題。

3.4.2分治法的典型實(shí)例——大整數(shù)乘法3.4.2分治法的典型實(shí)例——大整數(shù)乘法3.算法設(shè)計(jì)BigIntMul(X,Y,n)輸入：大整數(shù)X，Y和位數(shù)n輸出：X與Y的乘積結(jié)果sx←sign(X),sy←sign(Y) //取X，Y的符號(hào)s←sx*sy //求出X×Y的符號(hào)ifs=0thenreturn0endifX←|X|,Y←|Y|ifn=1thenreturns*X*YendifA←X的左邊n/2位, B←X的右邊n/2位C←Y的左邊n/2位, D←Y的右邊n/2位m1←BigIntMul(A,C，n/2), m2←BigIntMul((A-B),(D-C)，n/2)m3←BigIntMul(B,D，n/2)S←m1*10^n+(m1+m2+m3)*10^(n/2)+m3returnS舉例:以計(jì)算3141×5247為例來說明。將3141分拆成31和41，5247分拆成52和47。然后計(jì)算31×52，-10×-5，41×47。當(dāng)出現(xiàn)兩個(gè)數(shù)位數(shù)不等時(shí)，可以將位數(shù)小的高位補(bǔ)0再進(jìn)行計(jì)算。如：-10×-5=10×05=(1×10+0)×(0×10+5)=1×0×100+(1×5+1×0+0×5)×10+0×5=0+50+0=50其他兩個(gè)個(gè)同理算出：31×52=1612，41×47=1927。帶入原來的算式得：3141×5247=16120000+(50+1612+1927)×100+1927=16480827。3.4.2分治法的典型實(shí)例——大整數(shù)乘法4.算法效率分析根據(jù)上述的計(jì)算過程得到遞推方程。改進(jìn)前：根據(jù)主定理理論可得：改進(jìn)后：根據(jù)主定理可得：

，有較大的改進(jìn)。3.4.3分治法的典型實(shí)例——平面內(nèi)最近點(diǎn)問題

3.4.3分治法的典型實(shí)例——平面內(nèi)最近點(diǎn)問題

2.問題分析如果采用蠻力法，就需要遍歷平面上任意兩個(gè)點(diǎn)之間的距離，然后比較得出最小的值。很顯然其時(shí)間復(fù)雜度是O(n2)。那有沒有更快的方法呢？考慮分治法，如圖3.2所示，用一條垂直的直線l將整個(gè)平面中的點(diǎn)分為左半平面PL和右半平面PR兩部分，使得兩部分的點(diǎn)數(shù)近似相等。

3.4.3分治法的典型實(shí)例——平面內(nèi)最近點(diǎn)問題將平面的點(diǎn)集一分為二PLPRP直線l

3.4.3分治法的典型實(shí)例——平面內(nèi)最近點(diǎn)問題

3.4.4分治法的典型實(shí)例——選擇第k小問題

大小S3S4S1S2中位數(shù)組M

3.4.3分治法的典型實(shí)例——平面內(nèi)最近點(diǎn)問題平面上最臨近點(diǎn)對(duì)算法MinDistance(P,X,Y)輸入：n()個(gè)點(diǎn)集合P，X,Y分別表示n個(gè)點(diǎn)的x,y坐標(biāo)的值輸出：最近的兩個(gè)點(diǎn)以及距離ifn≤

3then直接計(jì)算n個(gè)點(diǎn)之間的最短距離endifSort(n,X,Y) //把所有的點(diǎn)按照橫坐標(biāo)X排序

l←mid(X) //用一條豎直的線L將所有的點(diǎn)分成兩等份MinDistance(PL,XL,YL)d1←PL中最短距離MinDistance(PR,XR,YR)d2←PR中最短距離d←min(d1,d2)while(PL中的點(diǎn)andXL≥l-d)dowhile(PR中的點(diǎn)andXR≤l+d)doifdistance(XL,YL,XR,YR)<dthen存儲(chǔ)點(diǎn)對(duì)(XL,YL),(XR,YR)d←distance(XL,YL,XR,YR)endifendwhileendwhile該算法是遞歸算法，且里面有排序，為了提高效率，可以把排序操作放到遞歸算法的外面。另外在直線l兩邊距離不超過d的