分治算法举例.docx
《分治算法举例.docx》由会员分享,可在线阅读,更多相关《分治算法举例.docx(4页珍藏版)》请在冰点文库上搜索。
1设X[0:
n-1]和Y[0:
n-1]为两个数组,每个数组中含有n个已排序好的数。
试设计一个O(logn)时间的分治算法,找出X和Y的2n个数的中位数,并证明算法的时间复杂性为O(logn)。
注:
个数为奇数,则处于最中间位置的数;
个数为偶数,则中间两个数据的平均数。
解:
利用二分查找思想:
对于两个等长的数组,
如果数组长度为奇数,令mid为数组的最中间元素的位置,则有X[mid],Y[mid]分别为两个数组的中位数,则存在以下情况:
(1)如果X[mid]n-1]和Y[0:
mid]中查找;
(2)如果X[mid]>Y[mid],则两个数组合并后的中位数应该在X[0:
mid]和Y[mid:
n-1]中查找;
(3)如果X[mid]=Y[mid],则两个数组合并后的中位数就是X[mid]或者Y[mid]
另外考虑特殊情况:
如果两个数组的长度为1,则无需比较大小,合并后数组的中位数即为两个数组元素的平均值。
如果数组的长度为偶数,令mid为数组的中间两个元素的较小元素的位置,此时数组X的中位数为x=(X[mid]+X[mid+1])/2.0,数组Y的中位数为y=(Y[mid]+Y[mid+1])/2.0(这里考虑到中位数不一定为整数)。
则存在以下情况:
(1)如果xn-1]和Y[0:
mid]中查找;
(2)如果x>y,则两个数组合并后的中位数应该在X[0:
mid]和Y[mid+1:
n-1]中查找;
(3)如果x=y,则两个数组合并后的中位数就是x或者y.
考虑特殊情况:
如果两个数组的长度为2,则如果其中一个数组A的元素刚好处于合并后的数组的中间位置,则最终的中位数为这个数组A的数组元素的平均数。
否则,则回到数组长度为偶数的一般情况。
具体如下:
doubleSearch_Median(int*A,intl1,intr1,int*B,intl2,intr2,intn){
/*如果两个数组的长度为,则中位数为所有元素的平均数,其中
A,B为要查中位数的数组,
l1,r1,l2,r2分别为两个数组每次查询的起始位置和终点位置
n为两个数组每次查询时的范围(重新查询的数组长度)
*/
if(n==1){
//数组长度为1的情况
return(A[l1]+B[l2])/2.0;
}
if(n==2){
//数组长度为2的情况
if(A[l1]>B[l1]&&A[r1]
return(A[l1]+A[r1])/2.0;
elseif(A[l1]B[r2])
return(B[l2]+B[r2])/2.0;
else;
}
//这里使用mid1,mid2分别来记录两个数组每次变化后的中间位置
intmid1=(r1+l1)/2;
intmid2=(r2+l2)/2;
//如果数组的长度为偶数,对数组进行查询
if(n%2==0){
//这里考虑到偶数数组的中位数是中间两个数的平均数
doublex=(A[mid1]+A[mid1+1])/2.0;
doubley=(B[mid2]+B[mid2+1])/2.0;
if(x returnSearch_Median(A,mid1+1,r1,B,l2,mid2,n/2);
}
elseif(x==y)
returnx;
else
returnSearch_Median(A,l1,mid1,B,mid2+1,r2,n/2);
}
//如果数组长度为奇数,对数组查询
if(n%2==1){
if(A[mid1]==B[mid2])
returnA[mid1];
elseif(A[mid1]
returnSearch_Median(A,mid1,r1,B,l2,mid2,n/2+1);
else
returnSearch_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两个部分皆为有序的情况,那么对于当a[j]则可以据此得到相应算法。
首先设置一个计数器记录逆序对个数,每次归并分成分割与合并两部分,在合并部分中过程中添加计数过程,具体如下:
staticintcount=0;//定义一个计数器,记录逆序对个数
voidmerge(inta[],intp,intq,intr){
//合并过程,其中a[]为原数组,p为数组的起始位置,q为分割位置,r为元素个数
intn1=q-p+1;
intn2=r-q;
//定义两个新数组存放数组a中的元素
int*l=newint[n1+1];
int*rl=newint[n2+1];
for(inti=0;i l[i]=a[p+i-1];
for(intj=0;j rl[j]=a[q+j];
l[n1]=65535;//将新数组的最后一个位置设为无限大作为哨兵
rl[n2]=65535;
inti=0;
intj=0;
//合并两个数组到原数组
for(intk=p-1;k if(l[i]<=rl[j]){
a[k]=l[i];
i++;
}
else{
a[k]=rl[j];
j++;
count+=(q-i+1-p);//存在逆序对,将逆序对数进行记录
}
}
}
voidmergeSort(inta[],intp,intr){
//分割过程,r为元素个数
if(p {
intq=(p+r)/2;
mergeSort(a,p,q);
mergeSort(a,q+1,r);
merge(a,p,q,r);
}
}
时间复杂度分析:
因为记录的过程是随着归并排序的过程处理的,仅仅在合并到原数组的过程中添加一条语句,用于记录。
因此算法的时间复杂度为O(nlogn)。