分治算法举例.docx
- 文档编号:1220531
- 上传时间:2023-04-30
- 格式:DOCX
- 页数:4
- 大小:17.16KB
分治算法举例.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)如果x n-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,若i 例如: 序列(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)。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 分治 算法 举例