分治算法举例

1 设X0：n-1和Y0：n-1为两个数组，每个数组中含有n个已排序好的数。试设计一个O(logn)时间的分治算法，找出X和Y的2n个数的中位数，并证明算法的时间复杂性为O(logn)。注：个数为奇数，则处于最中间位置的数；个数为偶数，则中间两个数据的平均数。解：利用二分查找思想：对于两个等长的数组，如果数组长度为奇数，令mid为数组的最中间元素的位置，则有Xmid，Ymid分别为两个数组的中位数，则存在以下情况：（1）如果XmidYmid，则两个数组合并后的中位数应该在X0 : mid和Ymid : n-1中查找；（3）如果Xmid=Ymid，则两个数组合并后的中位数就是Xmid或者Ymid另外考虑特殊情况：如果两个数组的长度为1，则无需比较大小，合并后数组的中位数即为两个数组元素的平均值。如果数组的长度为偶数，令mid为数组的中间两个元素的较小元素的位置，此时数组X的中位数为x=(Xmid+Xmid+1)/2.0，数组Y的中位数为y=(Ymid+Ymid+1)/2.0 (这里考虑到中位数不一定为整数)。则存在以下情况：（1）如果xy，则两个数组合并后的中位数应该在X0 : mid和Ymid+1 : n-1中查找；（3）如果x=y，则两个数组合并后的中位数就是x或者y.考虑特殊情况：如果两个数组的长度为2，则如果其中一个数组A的元素刚好处于合并后的数组的中间位置，则最终的中位数为这个数组A的数组元素的平均数。否则，则回到数组长度为偶数的一般情况。具体如下：double Search_Median(int *A,int l1,int r1,int *B,int l2,int r2,int n)/*如果两个数组的长度为，则中位数为所有元素的平均数，其中A,B为要查中位数的数组，l1,r1,l2,r2分别为两个数组每次查询的起始位置和终点位置n为两个数组每次查询时的范围（重新查询的数组长度）*/if (n=1) /数组长度为1的情况return (Al1+Bl2)/2.0;if (n=2) /数组长度为2的情况if (Al1Bl1&Ar1Br2)return (Al1+Ar1)/2.0;else if (Al1Br2)return (Bl2+Br2)/2.0;else;/这里使用mid1,mid2分别来记录两个数组每次变化后的中间位置int mid1=(r1+l1)/2;int mid2=(r2+l2)/2;/如果数组的长度为偶数，对数组进行查询if(n%2=0)/这里考虑到偶数数组的中位数是中间两个数的平均数double x=(Amid1+Amid1+1)/2.0;double y=(Bmid2+Bmid2+1)/2.0;if (xy)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);/如果数组长度为奇数，对数组查询if(n%2=1)if (Amid1=Bmid2)return Amid1;else if (Amid1Bmid2)return Search_Median(A,mid1,r1,B,l2,mid2,n/2+1);elsereturn Search_Median(A,l1,mid1,B,mid2,r2,n/2+1);这样一来，因为采用的是二分查找的思想，数组又是已经排好序的，因此每次查找两个数组的中位数的时间复杂度为O(1)，比较的代价为O(1)，而查找过程总得需要重复logn次，因此算法的时间复杂度为O(logn)。2 有一实数序列a1,a2,aN, 若 iaj, 则(ai , aj)构成了一个逆序对，请使用分治方法求整个序列中逆序对个数，并分析算法的时间复杂性。例如：序列（4, 3, 2）逆序对有（4, 3），（4, 2），（3, 2）共3个解：数据输入：a数组，n（元素个数）采用归并排序思想：将序列看成一个数组假设f(i , j)为i到j的逆序对个数，取一个分割点k，假设s(i , j , k)表示以k为分割点，第一个元素在i到k中，第二个元素在k+1到j中形成的逆序对数。那么可以形成一个递归式：f(i , j)=f(i , k) + f(k+1 , j) + s(i , j , k).采用归并排序算法进行递归求解，如果对于A数组的i到k和k+1到j 两个部分皆为有序的情况，那么对于当ajai时，必然有ajai.k,即aj和从i到k号元素都形成逆序对，此时只要将s(i,j,k)加上k-i+1（i到k之间的元素个数）就可以了，此过程类似于归并排序的合并过程。则可以据此得到相应算法。首先设置一个计数器记录逆序对个数，每次归并分成分割与合并两部分，在合并部分中过程中添加计数过程，具体如下：static int count=0; /定义一个计数器，记录逆序对个数void merge(int a,int p,int q,int r)/合并过程，其中a为原数组，p为数组的起始位置，q为分割位置，r为元素个数int n1=q-p+1;int n2=r-q; /定义两个新数组存放数组a中的元素int * l=new intn1+1; int * rl=new intn2+1; for(int i=0;in1;i+) li=ap+i-1; for(int j=0;jn2;j+) rlj=aq+j; ln1=65535; /将新数组的最后一个位置设为无限大作为哨兵rln2=65535; int i=0; int j=0; /合并两个数组到原数组for(int k=p-1;kr;k+) if(li=rlj) ak=li;i+; else ak=rlj; j+; count+=(q-i+1-p);/存在逆序对，将逆序对数进行记录 void mergeSort(int a,int p,int r) /分割过程，r为元素个数if(pr) int q=(p+r)