分治法第k小元素poj.ppt

第六章 分 治,6.1 引言,分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。 战略 算法设计技术 划分治理组合,将要求解的较大规模的问题分割成k个更小规模的子问题。,6.1.1算法总体思想,n,T(n/2),T(n/2),T(n/2),T(n/2),T(n),=,对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。,直到问题规模足够小，很容易求出其解为止。,可将规模为n的问题分解为多少个规模为n/2的子问题？为什么不一定是两个？,将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。,n,T(n),=,棋盘覆盖问题,n=8,问题一：在一个整数组A1.n中，同时寻找最大值和最小值,6.1.2一个简单例子,方法一：顺序扫描法 S1: min=A1;max=A1; S2: 扫描数组，对i从2到n做： S2a: 如果Aimax，则max=Ai; S3: 返回x,y的值 比较次数：2n-2,方法二：分治法 基本思想： （1）划分：将数组分割成两半 （2）治理：在每一半中找到最大值和最小值。 （3）合并：返回两个最大值中的最大值和两个最小值中的最小值。,算法6.1 Minmax(int low,int high) if high-low=1 then if AlowAhigh then return(Alow,Ahigh) else return(Ahigh,Alow) end if else mid=(low+high)/2 (x1,y1)=minmax(low,mid) (x2,y2)=minmax(mid+1,high) x=minx1,x2; y=max(y1,y2) return(x,y) endif,讨论（1）,请将以上算法改写为C程序 注意： （1）以上算法要求函数同时返回两个值，显然是不符合C语言语法的，请给出你的解决方案 （2）C中函数参数的传递是传值传递,Minmax(int A,int low,int high,int *x,int *y) if ( high-low=1) if (AlowAhigh)*x= Alow;*y=Ahigh; else *x=Ahigh;*y=Alow); else mid=(low+high)/2; minmax(A,low,mid, ,时间复杂度分析： 1 若n=2 C(n)= 2C(n/2)+2 若n2 求解递推式得： C(n)=3n/2-2,6.2 二分搜索,问题：在一个有序序列中搜索给定值x，若找到，返回x所在位置，否则返回查找失败标志-1。,二分搜索过程,mid,mid,查找成功！,因Amid22，丢弃Amid及其左边所有元素,mid,mid,算法6.2 二分搜索的非递归算法 int BinarySearch(int a, int n, int x ) int low=0;high=n-1; while (high = low) /待搜区间非空 int mid = (low+ high )/2; if (x = amid) return mid; /查找成功 if (x amid) high = mid-1; else low = mid+1; return -1; /查找失败，返回-1 ,算法6.3 二分搜索的递归算法 int BSearch(int a, int n, int x,int low,int high ) if(lowhigh)return -1 /待搜区间为空 else int mid = (low+ high )/2; if (x = amid) return mid; /查找成功 if (x amid) return BSearch(a,n,x,low,mid-1); else return BSearch(a,n,x,mid+1,high); ,二分搜索算法分析,时间复杂度分析： 1 若n=1 C(n)= C( )+1 若n 2 求解递推式得：,6.3 合并排序,原问题：对A1.n排序 用分治策略分析： （1）划分：将A1.n分为A1.n/2 An/2+1.n两部分； （2）治理： 分别对A1.n/2 和An/2+1.n排序 （3）组合：将两个有序子序列合并为一个有序序列,算法6.4：合并排序算法 MergeSort(int A,int n) Msort(A,1,n); MSort(int A,int low,int high) if(lowhigh) /若区间有两个或两个以上元素 mid=(low+high)/2; /计算划分点 Msort(A,low,mid); /治理左半个区间 Msort(A,mid+1,high); /治理右半个区间 Merge(A,low,mid,high); /组合步骤 ,合并排序算法分析,时间复杂度分析： 0 若n=1 C(n)= 2C( )+n-1 若n2 求解递推式得： C(n)=nlogn-n+1,6.4 分治范式,（1）划分步骤 （2）治理步骤 （3）组合步骤,分治法的适用条件,分治法所能解决的问题一般具有以下几个特征： 该问题的规模缩小到一定的程度就可以容易地解决； 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质 利用该问题分解出的子问题的解可以合并为该问题的解； 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。,因为问题的计算复杂性一般是随着问题规模的增加而增加，因此大部分问题满足这个特征。,这条特征是应用分治法的前提，它也是大多数问题可以满足的，此特征反映了递归思想的应用,能否利用分治法完全取决于问题是否具有这条特征，如果具备了前两条特征，而不具备第三条特征，则可以考虑贪心算法或动态规划。,这条特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然也可用分治法，但一般用动态规划较好。,divide-and-conquer(P) if ( | P | = n0) adhoc(P); /解决小规模的问题 divide P into smaller subinstances P1,P2,.,Pk；/分解问题 for (i=1,i=k,i+) yi=divide-and-conquer(Pi); /递归的解各子问题 return merge(y1,.,yk); /将各子问题的解合并为原问题的解 ,分治法的基本步骤,人们从大量实践中发现，在用分治法设计算法时，最好使子问题的规模大致相同。即将一个问题分成大小相等的k个子问题的处理方法是行之有效的。这种使子问题规模大致相等的做法是出自一种平衡(balancing)子问题的思想，它几乎总是比子问题规模不等的做法要好。,分治法的复杂性分析,（1）划分步骤 将规模为n的问题分成k个规模为nm的子问题 （2）治理步骤 解k个规模为nm的子问题 （3）组合步骤 将k个子问题的解合并为原问题的解 设分解阀值n0=1，且adhoc解规模为1的问题耗费1个单位时间。组合步骤需用f(n)个单位时间。 用T(n)表示该分治法解规模为n的问题所需的计算时间，则有：,通过迭代法求得方程的解：,6.5 寻找中项和第k小元素,问题：在序列A1.n中寻找第k小的元素 当k=1,求序列中的最小值； 当k=n,求序列中的最大值。简单！(n) 其他情况下,如n=100,k=40 ? 方法一： 对A1.n排序，A40即所求。 时间复杂度为:(nlogn) 寻找一个O(n)的算法！,启发一：受快速排序的启发，先对序列进行划分，如对如下序列找第4小的元素 13，4，6，19，16，8，5，3，17，21 以第一个元素为基准，把比13小的移到它的左边，比13大的移到它的右边 4，6 ， 8，5，3，1 3，19，16，17 ，21 比13小的有5个元素，那么第4小的元素一定在13的左边，此时，可以丢弃13及13右边的元素。,算法6.5 区间划分算法 partition(int a,int low,int high) /以alow为基准元素，对alow.high进行划分 int i=low,j=high; temp=alow; /取第一个对象为进行调整的标准对象 while(ij) while(ij return(i),方法一： （1）以元素mm为基准，将A1.n拆分为三组： 并返回基准元素的下标j （2）若j=k, 则Aj即第k小的元素； 若jk,丢弃Aj.n，在A1.j-1中寻找第k小的元素； 若jk,丢弃A1.j ，在Aj+1.n中寻找第k-j小的元素；,启发二：如果能在每一个划分步骤后，问题的规模以一个常数因子被减小，则原问题 可在O(n)时间内解决。 假设算法丢弃1/3并对剩余的2/3部分递归，假定在每次调用中，算法对每个元素耗费的时间不超过常数c，则算法所需的全部时间为： cn+(2/3)cn +(2/3)2cn+. +(2/3)jcn+. = = 3cn,分析方法一： （1）在最坏情况下，算法需要O(n2)计算时间 （2）若改进算法一，在划分时随机选取一个元素作为基准元素，算法可以在O(n)平均时间内找出n个输入元素中的第k小元素。但在最坏情况下，算法仍需要O(n2)计算时间。我们要找一个字最坏情况下只需O(n)时间的算法。 （3）问题的关键是基准元素的选取,关键问题：如何选择基准元素？ 方法一：以区间左端元素为基准元素 方法二：随即选取基准元素 在最坏情况下，效果极不理想，不能保证问题的规模以一个常数因子被减小,中项的概念 序列A1.n的中项是序列中第 小的元素 若能找到序列的中项，一中项为基准可将序列分成大致相等的两部分，这是最理想的！然而寻找中项是和原问题一样难 降低难度：找一个接近中项的元素作为基准元素！,思路： （1）把n个元素划分成n/5组，每组5个元素； （2）找到每组元素的中项，共有n/5个 （3）若（2）中所得元素已较少可直接确定中项做基准元素；否则，递归调用自身，寻找（2）中得到的n/5个元素的基准元素,例：在A中找第13小的元素，A中元素：8,33,17,51,57,49,35,11,25,37,14,3,2,13,52,12,6,29,32,54, 5,16,22,23,7，9,34,18,53, 解：（1）分成6组： （8,33,17,51,57）,（49,35,11,25,37）, (14,3,2,13,52）,（12,6,29,32,54）, （5,16,22,23,7）, (9,34,18,53,58) (2)对每组升序排序 （8, 17, 33,51,57）,（11,25, 35,37,49）, (2, 3,13,14,52）,（6, 12,29,32,54）, （5,7,16,22,23）, (9, 18, 34,53,58),(3)取每一组的中项元素形成中项集： M=33,35,13,29,16,34 M中元素已较少，可用直接排序法取中项mm=29 （4）以29为基准，将A分成3部分 A1=8,17,11,25,14,3,2,13,12,6,5,16,22,23,7 A2=29 j=16 A3=33,51,57,49,35,37,52,32,54 因1316,A2和A3中元素可以丢弃，第13小的元素一定在A1中，重复上述过程。,设A=A1, （1）把元素分为3组： （8,17,11,25,14）,（3,2,13,12,6）,（5,16,22,23,7） （2）每组排序后找到新的中项集14，6，16， （3）再取其中项14做为新的mm, （4）将A划分为三个序列 A1=8,11,3,2,13,12,6,5,7 A2=14 j=10 A3=17,25,16,22,23 因为1310,丢弃A1 和A2，在A3中找第13-10大的元素，算法返回22,算法6.6线性时间选择算法 Select(int A,int n,int k) /在A中寻找第k小的元素 Slt(A,1,n,k); /在A1.n中寻找第k小的元素 ,Slt(int A,int low,int high,int k) /在Alow.high中寻找第k小的元素 p=high-low+1 If(p44)直接对A排序，返回Ak 令q=p/5,将A分成q组，每组5个元素 将q组中的每一组单独排序，找出各组中 项，得中项集M Mm=Slt(M,1,q,q/2); /mm为中项集的中项,j=patition(A,low,high,mm); /以mm为基准划分Alow.high，j为mm对应下标 if(j=k)return mm /找到第k小的元素 if(jk) Slt(A,low,j-1,k); /丢弃mm及其后元素 else Slt(A,j+1,high,k-j) /丢弃mm及其前元素 ,选择算法的分析,不论那中情况出现，都至少丢弃 个元素 剩余元素个数不多于,Slt(int A,int low,int high,int k) /在Alow.high中寻找第k小的元素 S1:p=high-low+1 S2: If(p44)直接对A排序，返回Ak 令q=p/5,将A分成q组，每组5个元素 S3: