Divide-and-Conquer算法的設(shè)計
設(shè)計過程分為三個階段:
Divide:整個問題劃分為多個子問題
Conquer:求解各子問題(遞歸調(diào)用正設(shè)計的算法)
Merge:合并子問題的解,形成原始問題的解
下面是幾道小題使用分治算法求解的思路。
1黑白點對
題目：
給定平面上有n個白點和n個黑點，任意三點不共線，試實際一個分治算法將每個白點與一個黑點相連，是所有連線互不相交。
思路：
將所有2n個點點按照x有小到大排序，以一條垂直于x軸的線將這些點分為大小均為n的左右兩部分，左右兩部分遞歸的進行黑白點對的匹配，由于每部分分到的黑點數(shù)與白點數(shù)不一定相等，最終返回的每部分都是互不相交的黑白點對連線以及一些單獨的黑點，或者是互不相交的黑白點對連線以及一些單獨的白點。
在合并時，若兩部分剩余的點都是黑色或都是白色，則合并完成。
若一部分剩余的是黑點，另一部分剩余的是白點，則將這些點匹配連線。每次新連接一條線時，若并不與其他線相交，則連接下一對；若與其他k對相交，可以通過k-1次交換使其不再交叉（由于不存在任意三點共線，所以必然可以通過有限次交換使其互不相交），連接下一對。直到單獨的黑點或者白點全部連接完畢。
算法設(shè)計：
Divide：按照橫坐標(biāo)，將所有點分為等量的左右兩部分。
Conquer：遞歸的將左右兩部分進行黑白點對的匹配。當(dāng)某部分中只有一個點或兩個同色的點時，直接返回；有兩個不同色的點時，將他們匹配。
Merge：左右兩部分中若有某部分黑白點完全匹配了，直接合并，返回；左右兩部分沒有匹配的單獨點同色，直接合并，返回；將左右兩部分沒有匹配的點異色，依次匹配，若存在交叉，則可以通過與交叉線段有限次交換使其互不相交，當(dāng)所有某側(cè)單獨的點都完成匹配，返回。
時間復(fù)雜度分析：
設(shè)該算法的時間復(fù)雜度為T(2n),合并時，左右兩側(cè)單獨的點最多進行n次連線，每次連線時最多與與其相交的n-1條線段進行交換，時間復(fù)雜度為O(n^2)。
T(n)=2T(n/2)+O(n^2).
逐步遞推得到時間復(fù)雜度T(n)=O(n^2).
2求最大連續(xù)子數(shù)組
題目：
給定一個數(shù)組A[1:n]，數(shù)組元素由實數(shù)構(gòu)成，求A的連續(xù)子數(shù)組，使得此子數(shù)組的和最大。如：A={-2,-5,6,-2,-3,1,5,-6}，結(jié)果為{6,-2,-3,1,5}，和為7。設(shè)計一個分治算法，求A[1:n]的和最大連續(xù)子數(shù)組
思路：
采用二分的方法將數(shù)組從中間分為左右兩個子數(shù)組，則最大子數(shù)組必然出現(xiàn)在以下三種情況之一：
1)完全位于左邊的數(shù)組中。
2)完全位于右邊的數(shù)組中。
3)跨越中點，包含左右數(shù)組中靠近中點的部分。
遞歸將左右子數(shù)組再分別分成兩個數(shù)組，直到子數(shù)組中只含有一個元素，退出每層遞歸前，返回上面三種情況中的最大值。
算法設(shè)計：
Divide：將數(shù)組A劃分為左右兩個子數(shù)組AL和AR。
Conquer：遞歸的求解AL和AR的最大連續(xù)子數(shù)組。若數(shù)組中只有一個數(shù)字，最大連續(xù)子數(shù)組為這個數(shù)字本身。
Merge：AL和AR的最大連續(xù)子數(shù)組的和分別為MaxLeftSum，MaxRightSum。設(shè)從AL最右端開始的連續(xù)子序列的最大和為MaxLeftBorderSum，從AR最左端開始的連續(xù)子序列的最大和為MaxRightBorderSum，那么跨越中點的最大連續(xù)子數(shù)組的和為MaxLeftBorderSum+MaxRightBorderSum。返回MaxLeftSum，MaxRightSum，MaxLeftBorderSum+MaxRightBorderSum這三者的最大值。
時間復(fù)雜度分析：
設(shè)該算法的時間復(fù)雜度為T(n),則：
T(n)=2T(n/2)+O(n)，且T(1)=1.
逐步遞推得到時間復(fù)雜度T(n)=O(nlogn).
3英文字母編碼
題目：
將26個英文字母進行編碼，‘A’編碼為‘1’，‘B’編碼為‘2’，……，‘Z’編碼為‘26’。那么給定一個數(shù)字序列可以對其進行解碼，但解碼不唯一。比如給定數(shù)字序列“234”，可以解碼為“2-3-4”，對應(yīng)“BCD”；也可以解碼為“23-4”，對應(yīng)“WD”。設(shè)計一個分治算法，對于給定的數(shù)字序列LIST，求出給數(shù)字序列有幾種解碼方式。
思路：
編碼為1~26，所以數(shù)字有以下幾種情況：
數(shù)字0必須與它前面的1或2一起編碼，只有一種編碼情況；數(shù)字1可單獨編碼，也可與其后面的數(shù)字一起編碼，通常有兩種情況，但當(dāng)后面跟著10或20時，只能編碼為A；數(shù)字2可單獨編碼，也可與其后面的數(shù)字0~6一起編碼，但當(dāng)后面跟著7、8、9、10、20時，只能編碼為B；數(shù)字3~9前沒有1或2時只有一種編碼情況。
可以遞歸的將序列LIST二分，直到每個子序列中只有一個數(shù)字，此時子序列的解碼方式為1，合并時考慮合并處兩個數(shù)字是否有更多的解碼方式。
算法設(shè)計：
Divide：將序列LIST劃分為左右兩個子序列LISTL和LISTR。
Conquer：遞歸的求解LISTL和LISTR的解碼方式。若序列中只有一個數(shù)字，返回解碼方式為1。
Merge：將LISTL和LISTR的解碼方式數(shù)相乘，得到res。再考慮合并處的兩個數(shù)字，即LISTL的最右數(shù)字n1與LISTR的最左數(shù)字n2，若n1等于1，n2不為0，則將res乘以2；若n1等于2，n2為1~6，則將res乘以2；其余情況res不變。將得到的res返回。
時間復(fù)雜度分析：
設(shè)該算法的時間復(fù)雜度為T(n),則：
T(n)=2T(n/2)+O(n)，且T(1)=1.
逐步遞推得到時間復(fù)雜度T(n)=O(nlogn).
4求逆序數(shù)
題目：
設(shè)A[1:n]是由不同實數(shù)組成的數(shù)組，如果iA[j]，則稱實數(shù)對(A[i],A[j])是該數(shù)組的一個反序。如，若A=[3,5,2,4]，則該數(shù)組存在3個反序(3,2)、(5,2)和(5,4)。設(shè)計一個分治算法，求逆序數(shù)。
思路：
類似于歸并排序算法。先將數(shù)組從中間分成兩個部分，然后分別遞歸左半部分和右半部分，再合并排好序的左右兩個部分，從而統(tǒng)計逆序?qū)?shù)。
對于兩個排好序的數(shù)組AL和AR，初始時分別設(shè)置指針p1、p2在數(shù)組最左端，比較AL[p1]與AR[p2]的大小：如果AL[p1]>AR[p2]，那么顯然AL中AL[p1]及其后面的所有元素都能與AR[p2]構(gòu)成逆序?qū)?，記錄這個數(shù)并將p2右移；否則將p1右移，當(dāng)完成兩個數(shù)組的遍歷后就得到了這兩個數(shù)組間的逆序數(shù)。
算法設(shè)計：
Divide：將數(shù)組A劃分為左右兩個子數(shù)組AL和AR。
Conquer：遞歸的求解AL和AR的逆序數(shù)。若數(shù)組中只有一個數(shù)字，則返回逆序數(shù)為0。
Merge：AL和AR的逆序數(shù)分別為sum1、sum2。AL和AR在之前的合并中已經(jīng)按從小到大的順序排好序了，所以我們可以在一次對這兩個數(shù)組的遍歷中，將它們以歸并排序的方法合并為A時，同時得到這兩個數(shù)組間的逆序數(shù)sum3。A的逆序數(shù)為sum1+sum2+sum3。
時間復(fù)雜度分析：
每次都要將序列的的n個元素合并，時間復(fù)雜度為O(n)。
設(shè)該算法的時間復(fù)雜度為T(n),則：
T(n)=2T(n/2)+O(n)，且T(1)=1.
逐步遞推得到時間復(fù)雜度T(n)=O(nlogn).
5友誼點對
題目：
給定平面上n個點構(gòu)成的集合S={p1,p2,……,pn}。如果存在便平行于坐標(biāo)軸的矩形僅包含S中的兩個點pi和pj(1<=i<j<=n)，則稱pi和pj為友誼點對。試設(shè)計一個分治算法統(tǒng)計S中友誼點對的個數(shù)。
算法設(shè)計：
預(yù)處理：將點集S中的所有點按照x有小到大排序。
Divide：將點集S用一條垂直于x軸的直線l：x=m劃分為兩個大小相等的子集SL和SR。
Conquer：遞歸的求解SL和SR中友誼點對數(shù)。若點集中點的數(shù)量為1，返回友誼點對數(shù)0；若點集中點的數(shù)量為2，這兩個點一定為友誼點對，返回友誼點對數(shù)1。
Merge：S的友誼點對數(shù)=SL的友誼點對數(shù)+SR的友誼點對數(shù)+兩點分別位于SL和SR的友誼點對數(shù)。兩點分別位于SL和SR的友誼點對數(shù)的求法如下：
1)p0(x0,y0)為SL中最右點，以y=y0為界將SR分為上下兩部分討論。對于上半部分找出x最小的點A和y最小的點B，能與p0構(gòu)成友誼點對的必然出現(xiàn)在以A、B為頂點的矩形區(qū)域中。
2)依次遍歷橫坐標(biāo)在區(qū)間(xA,xB)中的點。能與p0構(gòu)成友誼點對的，必然是橫坐標(biāo)依次增大同時縱坐標(biāo)依次減小的（若橫坐標(biāo)增大的同時縱坐標(biāo)也增大，后一個點與p0構(gòu)成的矩形中會包含前一個點）。下半部分同理。
3)p1為SL中次右點，若y1>y0，則只需考慮y>y0的區(qū)域；反之，只需考慮y<y0的區(qū)域。對于pk，只需考慮SL中縱坐標(biāo)與其相鄰的兩個點pi、pj的縱坐標(biāo)所夾區(qū)域(yi,yj)。對于SL中的每個點重復(fù)上述兩步，直到完全遍歷。
時間復(fù)雜度分析：
設(shè)該算法的時間復(fù)雜度為T(n),則：
T(n)=2T(n/2)+f(n)，且f(n)<=O(n^2).
所以T(n)=O(n^2).
