Divide-and-Conquer算法的設(shè)計(jì)
設(shè)計(jì)過程分為三個階段:
Divide:整個問題劃分為多個子問題
Conquer:求解各子問題(遞歸調(diào)用正設(shè)計(jì)的算法)
Merge:合并子問題的解,形成原始問題的解
下面是幾道小題使用分治算法求解的思路雏胃。
1黑白點(diǎn)對
題目：
給定平面上有n個白點(diǎn)和n個黑點(diǎn)牡直，任意三點(diǎn)不共線询微，試實(shí)際一個分治算法將每個白點(diǎn)與一個黑點(diǎn)相連，是所有連線互不相交弄抬。
思路：
將所有2n個點(diǎn)點(diǎn)按照x有小到大排序簇搅，以一條垂直于x軸的線將這些點(diǎn)分為大小均為n的左右兩部分臭墨，左右兩部分遞歸的進(jìn)行黑白點(diǎn)對的匹配枉疼，由于每部分分到的黑點(diǎn)數(shù)與白點(diǎn)數(shù)不一定相等，最終返回的每部分都是互不相交的黑白點(diǎn)對連線以及一些單獨(dú)的黑點(diǎn)魄咕，或者是互不相交的黑白點(diǎn)對連線以及一些單獨(dú)的白點(diǎn)衩椒。
在合并時(shí)，若兩部分剩余的點(diǎn)都是黑色或都是白色，則合并完成毛萌。
若一部分剩余的是黑點(diǎn)梢什，另一部分剩余的是白點(diǎn)，則將這些點(diǎn)匹配連線朝聋。每次新連接一條線時(shí)，若并不與其他線相交囤躁，則連接下一對冀痕；若與其他k對相交，可以通過k-1次交換使其不再交叉（由于不存在任意三點(diǎn)共線狸演，所以必然可以通過有限次交換使其互不相交）言蛇，連接下一對。直到單獨(dú)的黑點(diǎn)或者白點(diǎn)全部連接完畢宵距。
算法設(shè)計(jì)：
Divide：按照橫坐標(biāo)腊尚，將所有點(diǎn)分為等量的左右兩部分。
Conquer：遞歸的將左右兩部分進(jìn)行黑白點(diǎn)對的匹配满哪。當(dāng)某部分中只有一個點(diǎn)或兩個同色的點(diǎn)時(shí)婿斥，直接返回；有兩個不同色的點(diǎn)時(shí)哨鸭，將他們匹配民宿。
Merge：左右兩部分中若有某部分黑白點(diǎn)完全匹配了，直接合并像鸡，返回活鹰；左右兩部分沒有匹配的單獨(dú)點(diǎn)同色，直接合并只估，返回志群；將左右兩部分沒有匹配的點(diǎn)異色，依次匹配蛔钙，若存在交叉锌云，則可以通過與交叉線段有限次交換使其互不相交，當(dāng)所有某側(cè)單獨(dú)的點(diǎn)都完成匹配夸楣，返回宾抓。
時(shí)間復(fù)雜度分析：
設(shè)該算法的時(shí)間復(fù)雜度為T(2n),合并時(shí)，左右兩側(cè)單獨(dú)的點(diǎn)最多進(jìn)行n次連線豫喧，每次連線時(shí)最多與與其相交的n-1條線段進(jìn)行交換石洗，時(shí)間復(fù)雜度為O(n^2)。
T(n)=2T(n/2)+O(n^2).
逐步遞推得到時(shí)間復(fù)雜度T(n)=O(n^2).
2求最大連續(xù)子數(shù)組
題目：
給定一個數(shù)組A[1:n]紧显，數(shù)組元素由實(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è)計(jì)一個分治算法枷畏，求A[1:n]的和最大連續(xù)子數(shù)組
思路：
采用二分的方法將數(shù)組從中間分為左右兩個子數(shù)組别厘，則最大子數(shù)組必然出現(xiàn)在以下三種情況之一：
1)完全位于左邊的數(shù)組中。
2)完全位于右邊的數(shù)組中拥诡。
3)跨越中點(diǎn)触趴，包含左右數(shù)組中靠近中點(diǎn)的部分。
遞歸將左右子數(shù)組再分別分成兩個數(shù)組渴肉，直到子數(shù)組中只含有一個元素冗懦，退出每層遞歸前，返回上面三種情況中的最大值仇祭。
算法設(shè)計(jì)：
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，那么跨越中點(diǎn)的最大連續(xù)子數(shù)組的和為MaxLeftBorderSum+MaxRightBorderSum寂屏。返回MaxLeftSum贰谣，MaxRightSum，MaxLeftBorderSum+MaxRightBorderSum這三者的最大值迁霎。
時(shí)間復(fù)雜度分析：
設(shè)該算法的時(shí)間復(fù)雜度為T(n),則：
T(n)=2T(n/2)+O(n)吱抚，且T(1)=1.
逐步遞推得到時(shí)間復(fù)雜度T(n)=O(nlogn).
3英文字母編碼
題目：
將26個英文字母進(jìn)行編碼，‘A’編碼為‘1’考廉，‘B’編碼為‘2’秘豹，……，‘Z’編碼為‘26’昌粤。那么給定一個數(shù)字序列可以對其進(jìn)行解碼既绕，但解碼不唯一。比如給定數(shù)字序列“234”涮坐，可以解碼為“2-3-4”凄贩，對應(yīng)“BCD”；也可以解碼為“23-4”袱讹，對應(yīng)“WD”疲扎。設(shè)計(jì)一個分治算法，對于給定的數(shù)字序列LIST，求出給數(shù)字序列有幾種解碼方式椒丧。
思路：
編碼為1~26壹甥，所以數(shù)字有以下幾種情況：
數(shù)字0必須與它前面的1或2一起編碼，只有一種編碼情況壶熏；數(shù)字1可單獨(dú)編碼句柠，也可與其后面的數(shù)字一起編碼，通常有兩種情況棒假，但當(dāng)后面跟著10或20時(shí)俄占，只能編碼為A；數(shù)字2可單獨(dú)編碼淆衷，也可與其后面的數(shù)字0~6一起編碼，但當(dāng)后面跟著7渤弛、8祝拯、9、10她肯、20時(shí)佳头，只能編碼為B；數(shù)字3~9前沒有1或2時(shí)只有一種編碼情況晴氨。
可以遞歸的將序列LIST二分康嘉，直到每個子序列中只有一個數(shù)字，此時(shí)子序列的解碼方式為1籽前，合并時(shí)考慮合并處兩個數(shù)字是否有更多的解碼方式亭珍。
算法設(shè)計(jì)：
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返回。
時(shí)間復(fù)雜度分析：
設(shè)該算法的時(shí)間復(fù)雜度為T(n),則：
T(n)=2T(n/2)+O(n)，且T(1)=1.
逐步遞推得到時(shí)間復(fù)雜度T(n)=O(nlogn).
4求逆序數(shù)
題目：
設(shè)A[1:n]是由不同實(shí)數(shù)組成的數(shù)組嚣州，如果iA[j]鲫售，則稱實(shí)數(shù)對(A[i],A[j])是該數(shù)組的一個反序。如该肴，若A=[3,5,2,4]情竹，則該數(shù)組存在3個反序(3,2)、(5,2)和(5,4)匀哄。設(shè)計(jì)一個分治算法秦效，求逆序數(shù)。
思路：
類似于歸并排序算法涎嚼。先將數(shù)組從中間分成兩個部分阱州，然后分別遞歸左半部分和右半部分，再合并排好序的左右兩個部分法梯，從而統(tǒng)計(jì)逆序?qū)?shù)苔货。
對于兩個排好序的數(shù)組AL和AR，初始時(shí)分別設(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è)計(jì)：
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í)得到這兩個數(shù)組間的逆序數(shù)sum3。A的逆序數(shù)為sum1+sum2+sum3尤莺。
時(shí)間復(fù)雜度分析：
每次都要將序列的的n個元素合并旅敷，時(shí)間復(fù)雜度為O(n)。
設(shè)該算法的時(shí)間復(fù)雜度為T(n),則：
T(n)=2T(n/2)+O(n)颤霎，且T(1)=1.
逐步遞推得到時(shí)間復(fù)雜度T(n)=O(nlogn).
5友誼點(diǎn)對
題目：
給定平面上n個點(diǎn)構(gòu)成的集合S={p1,p2,……,pn}媳谁。如果存在便平行于坐標(biāo)軸的矩形僅包含S中的兩個點(diǎn)pi和pj(1<=i<j<=n)涂滴，則稱pi和pj為友誼點(diǎn)對。試設(shè)計(jì)一個分治算法統(tǒng)計(jì)S中友誼點(diǎn)對的個數(shù)晴音。
算法設(shè)計(jì)：
預(yù)處理：將點(diǎn)集S中的所有點(diǎn)按照x有小到大排序柔纵。
Divide：將點(diǎn)集S用一條垂直于x軸的直線l：x=m劃分為兩個大小相等的子集SL和SR。
Conquer：遞歸的求解SL和SR中友誼點(diǎn)對數(shù)锤躁。若點(diǎn)集中點(diǎn)的數(shù)量為1搁料，返回友誼點(diǎn)對數(shù)0；若點(diǎn)集中點(diǎn)的數(shù)量為2系羞，這兩個點(diǎn)一定為友誼點(diǎn)對郭计，返回友誼點(diǎn)對數(shù)1。
Merge：S的友誼點(diǎn)對數(shù)=SL的友誼點(diǎn)對數(shù)+SR的友誼點(diǎn)對數(shù)+兩點(diǎn)分別位于SL和SR的友誼點(diǎn)對數(shù)椒振。兩點(diǎn)分別位于SL和SR的友誼點(diǎn)對數(shù)的求法如下：
1)p0(x0,y0)為SL中最右點(diǎn)昭伸，以y=y0為界將SR分為上下兩部分討論。對于上半部分找出x最小的點(diǎn)A和y最小的點(diǎn)B澎迎，能與p0構(gòu)成友誼點(diǎn)對的必然出現(xiàn)在以A庐杨、B為頂點(diǎn)的矩形區(qū)域中。
2)依次遍歷橫坐標(biāo)在區(qū)間(xA,xB)中的點(diǎn)嗡善。能與p0構(gòu)成友誼點(diǎn)對的，必然是橫坐標(biāo)依次增大同時(shí)縱坐標(biāo)依次減小的（若橫坐標(biāo)增大的同時(shí)縱坐標(biāo)也增大学歧，后一個點(diǎn)與p0構(gòu)成的矩形中會包含前一個點(diǎn)）罩引。下半部分同理。
3)p1為SL中次右點(diǎn)枝笨，若y1>y0袁铐，則只需考慮y>y0的區(qū)域；反之横浑，只需考慮y<y0的區(qū)域剔桨。對于pk，只需考慮SL中縱坐標(biāo)與其相鄰的兩個點(diǎn)pi徙融、pj的縱坐標(biāo)所夾區(qū)域(yi,yj)洒缀。對于SL中的每個點(diǎn)重復(fù)上述兩步，直到完全遍歷欺冀。
時(shí)間復(fù)雜度分析：
設(shè)該算法的時(shí)間復(fù)雜度為T(n),則：
T(n)=2T(n/2)+f(n)树绩，且f(n)<=O(n^2).
所以T(n)=O(n^2).
