分治算法舉例(共4頁(yè))

1、精選優(yōu)質(zhì)文檔-傾情為你奉上1 設(shè)X0：n-1和Y0：n-1為兩個(gè)數(shù)組，每個(gè)數(shù)組中含有n個(gè)已排序好的數(shù)。試設(shè)計(jì)一個(gè)O(logn)時(shí)間的分治算法，找出X和Y的2n個(gè)數(shù)的中位數(shù)，并證明算法的時(shí)間復(fù)雜性為O(logn)。注：個(gè)數(shù)為奇數(shù)，則處于最中間位置的數(shù)；個(gè)數(shù)為偶數(shù)，則中間兩個(gè)數(shù)據(jù)的平均數(shù)。解：利用二分查找思想：對(duì)于兩個(gè)等長(zhǎng)的數(shù)組，如果數(shù)組長(zhǎng)度為奇數(shù)，令mid為數(shù)組的最中間元素的位置，則有Xmid，Ymid分別為兩個(gè)數(shù)組的中位數(shù)，則存在以下情況：（1）如果Xmid<Ymid，則兩個(gè)數(shù)組合并后的中位數(shù)應(yīng)該在Xmid : n-1和Y0 : mid中查找；（2）如果Xmid>Ymid，則兩個(gè)數(shù)

2、組合并后的中位數(shù)應(yīng)該在X0 : mid和Ymid : n-1中查找；（3）如果Xmid=Ymid，則兩個(gè)數(shù)組合并后的中位數(shù)就是Xmid或者Ymid另外考慮特殊情況：如果兩個(gè)數(shù)組的長(zhǎng)度為1，則無(wú)需比較大小，合并后數(shù)組的中位數(shù)即為兩個(gè)數(shù)組元素的平均值。如果數(shù)組的長(zhǎng)度為偶數(shù)，令mid為數(shù)組的中間兩個(gè)元素的較小元素的位置，此時(shí)數(shù)組X的中位數(shù)為x=(Xmid+Xmid+1)/2.0，數(shù)組Y的中位數(shù)為y=(Ymid+Ymid+1)/2.0 (這里考慮到中位數(shù)不一定為整數(shù))。則存在以下情況：（1）如果x<y，則兩個(gè)數(shù)組合并后的中位數(shù)應(yīng)該在Xmid+1 : n-1和Y0 : mid中查找；（2）如果x&

3、gt;y，則兩個(gè)數(shù)組合并后的中位數(shù)應(yīng)該在X0 : mid和Ymid+1 : n-1中查找；（3）如果x=y，則兩個(gè)數(shù)組合并后的中位數(shù)就是x或者y.考慮特殊情況：如果兩個(gè)數(shù)組的長(zhǎng)度為2，則如果其中一個(gè)數(shù)組A的元素剛好處于合并后的數(shù)組的中間位置，則最終的中位數(shù)為這個(gè)數(shù)組A的數(shù)組元素的平均數(shù)。否則，則回到數(shù)組長(zhǎng)度為偶數(shù)的一般情況。具體如下：double Search_Median(int *A,int l1,int r1,int *B,int l2,int r2,int n)/*如果兩個(gè)數(shù)組的長(zhǎng)度為，則中位數(shù)為所有元素的平均數(shù)，其中A,B為要查中位數(shù)的數(shù)組，l1,r1,l2,r2分別為兩個(gè)數(shù)組每次查

4、詢(xún)的起始位置和終點(diǎn)位置n為兩個(gè)數(shù)組每次查詢(xún)時(shí)的范圍（重新查詢(xún)的數(shù)組長(zhǎng)度）*/if (n=1) /數(shù)組長(zhǎng)度為1的情況return (Al1+Bl2)/2.0;if (n=2) /數(shù)組長(zhǎng)度為2的情況if (Al1>Bl1&&Ar1<Br2)return (Al1+Ar1)/2.0;else if (Al1<Bl1&&Ar1>Br2)return (Bl2+Br2)/2.0;else;/這里使用mid1,mid2分別來(lái)記錄兩個(gè)數(shù)組每次變化后的中間位置int mid1=(r1+l1)/2;int mid2=(r2+l2)/2;/如果數(shù)組的長(zhǎng)度為偶

5、數(shù)，對(duì)數(shù)組進(jìn)行查詢(xún)if(n%2=0)/這里考慮到偶數(shù)數(shù)組的中位數(shù)是中間兩個(gè)數(shù)的平均數(shù)double x=(Amid1+Amid1+1)/2.0;double y=(Bmid2+Bmid2+1)/2.0;if (x<y)return Search_Median(A,mid1+1,r1,B,l2,mid2,n/2);else if(x=y) return x;elsereturn Search_Median(A,l1,mid1,B,mid2+1,r2,n/2);/如果數(shù)組長(zhǎng)度為奇數(shù)，對(duì)數(shù)組查詢(xún)if(n%2=1)if (Amid1=Bmid2)return Amid1;else if (Amid

6、1<Bmid2)return Search_Median(A,mid1,r1,B,l2,mid2,n/2+1);elsereturn Search_Median(A,l1,mid1,B,mid2,r2,n/2+1);這樣一來(lái)，因?yàn)椴捎玫氖嵌植檎业乃枷?，?shù)組又是已經(jīng)排好序的，因此每次查找兩個(gè)數(shù)組的中位數(shù)的時(shí)間復(fù)雜度為O(1)，比較的代價(jià)為O(1)，而查找過(guò)程總得需要重復(fù)logn次，因此算法的時(shí)間復(fù)雜度為O(logn)。2 有一實(shí)數(shù)序列a1,a2,aN, 若 i<j 且ai>aj, 則(ai , aj)構(gòu)成了一個(gè)逆序?qū)?，?qǐng)使用分治方法求整個(gè)序列中逆序?qū)€(gè)數(shù)，并分析算法的時(shí)間復(fù)雜

7、性。例如：序列（4, 3, 2）逆序?qū)τ校?, 3），（4, 2），（3, 2）共3個(gè)解：數(shù)據(jù)輸入：a數(shù)組，n（元素個(gè)數(shù)）采用歸并排序思想：將序列看成一個(gè)數(shù)組假設(shè)f(i , j)為i到j(luò)的逆序?qū)€(gè)數(shù)，取一個(gè)分割點(diǎn)k，假設(shè)s(i , j , k)表示以k為分割點(diǎn)，第一個(gè)元素在i到k中，第二個(gè)元素在k+1到j(luò)中形成的逆序?qū)?shù)。那么可以形成一個(gè)遞歸式：f(i , j)=f(i , k) + f(k+1 , j) + s(i , j , k).采用歸并排序算法進(jìn)行遞歸求解，如果對(duì)于A數(shù)組的i到k和k+1到j(luò) 兩個(gè)部分皆為有序的情況，那么對(duì)于當(dāng)aj<ai時(shí)，必然有aj<ai.k,即aj和從i

8、到k號(hào)元素都形成逆序?qū)?，此時(shí)只要將s(i,j,k)加上k-i+1（i到k之間的元素個(gè)數(shù)）就可以了，此過(guò)程類(lèi)似于歸并排序的合并過(guò)程。則可以據(jù)此得到相應(yīng)算法。首先設(shè)置一個(gè)計(jì)數(shù)器記錄逆序?qū)€(gè)數(shù)，每次歸并分成分割與合并兩部分，在合并部分中過(guò)程中添加計(jì)數(shù)過(guò)程，具體如下：static int count=0; /定義一個(gè)計(jì)數(shù)器，記錄逆序?qū)€(gè)數(shù)void merge(int a,int p,int q,int r)/合并過(guò)程，其中a為原數(shù)組，p為數(shù)組的起始位置，q為分割位置，r為元素個(gè)數(shù)int n1=q-p+1;int n2=r-q; /定義兩個(gè)新數(shù)組存放數(shù)組a中的元素int * l=new intn1+1;

9、 int * rl=new intn2+1; for(int i=0;i<n1;i+) li=ap+i-1; for(int j=0;j<n2;j+) rlj=aq+j; ln1=65535; /將新數(shù)組的最后一個(gè)位置設(shè)為無(wú)限大作為哨兵rln2=65535; int i=0; int j=0; /合并兩個(gè)數(shù)組到原數(shù)組for(int k=p-1;k<r;k+) if(li<=rlj) ak=li;i+; else ak=rlj; j+; count+=(q-i+1-p);/存在逆序?qū)?，將逆序?qū)?shù)進(jìn)行記錄 void mergeSort(int a,int p,int r) /分割過(guò)程，r為元素個(gè)數(shù)if(p<r) int q=(p