算法设计与分析第5讲 寻找第K元.ppt

《算法设计与分析第5讲 寻找第K元.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、寻找第K元1问题描述给定一个数组A[n],寻找大小排在第k的元素。自然的想法：对A排序，returnA[k];时间复杂性O(nlogn)能不能更低？2随机分治方法RS(A,p,q,i)ifp=qreturnA[p];r=Rand_Partion(A,p,q)/*随机主元r，划分A为两部分，A[p…r-1]

2、k);3复杂性分析最差情况：T(n)=T(n-1)+θ(n)=θ(n2)分割比较好情况T(n)=T(n/2)+θ(n)=θ(n)4最差情况下线性时间算法Select(i,n)//找到好的划分主元1将数组划分为５个一组，共[n/5]组，查找每一组的中间值，t=θ(1)*[n/5]=θ(n)2将这[n/5]个中间值视为一个数组，找到其中间元x。t=T(n/5)3以x为主元划分，令k＝rank(x);ifi=kthenreturnx;ifi

3、k,n-k);5黄色的点是[n/5]的中间点，故比他小的有[n/10]个；而每个比它小的点，实际上可以代表３个点，故比黄色点小的应该有3n/10,可以确定不少于n/4.比黄色点大的也算这个数目。因此最坏的划分不会坏与1/4:3/4T(n)<=T(n/5)+T(3n/4)+θ(n)用代换法，假设T(n)

4、——以ap为基准元素将ap：r划分成3段ap：q-1、aq和aq+1：r，使得ap：q-1中任何元素小于aq，aq+1：r中任何元素大于aq；下标q在划分过程中确定；递归求解——通过递归调用快速排序算法分别对ap：q-1和aq+1：r进行排序；合并——由于对ap：q-1和aq+1：r的排序是就地进行的，所以在ap：q-1和aq+1：r都已排好序后不需要执行任何计算ap：r就已排好序。快速算法描述：templatevoidQuickSort(Typea[],intp,intr

5、){if(pintPartition(Typea[],intp,intr){inti=p,j=r+1;Typex=a[p];//将x的元素交换到右边区域For(j=p+1;j

6、wap(a[i],a[j]);}}Swap(a[p],a[i];returni;}{6,7,4,2,5,8}↑i↑j{6,7,4,2,5,8}↑i↑j{6,4,7,2,5,8}↑i↑j{6,4,2,7,5,8}↑i↑j{6,4,257,8}↑i↑j{5,4,267,8}Xpi<=xj>xT(n)=θ(n)8复杂性分析及随机化的快速排序算法算法复杂性分析：最坏时间复杂度：输入已经是有序的，此时每次划分都成为0:n-1,故T(n)=T(n-1)+θ(n),故T(n)=θ(n2)幸运时间复杂度：每次都

7、能1/2对1/2，T(n)=２T(n/2)+θ(n),θ(nlogn)如果每次划分1:9?用递归树分析，T(n)=θ(nlg10/9n),如果幸运和不幸运交叉？L(n)=2U(n/2)+θ(n),U(n)=L(n-1)+θ(n),L(n)=2L(n/2-1)+θ(n),L(n)=θ(nlogn)9随机化的快速排序算法算法描述：templateintRandomizedPartition(Typea[],intp,intr){inti=Random(p,r);Swap(a[

8、i],a[p]);returnPartition(a,p,r);}随机化选取主元，就跟输入无关，运行时间独立，不需要假设输入的分布。而最差情况取决于随机数产生器。10随机选主元的复杂性定义指示器随机变量E(Xk)=0*Pr(Xk=0)+1*Pr(Xk=1)=1/nT(n)=T(0)+T(n-1)+θ(n),如果x0=1T(n)=T(1)+T(n-2)+θ(n),如果x1=1T(n)=T(n-1)+T(0)+θ(n),如果xn-1=111随机选主元的复杂性如果对比较小的n12