分治法之选择问题(1)

1、1. 问题描述 在n个元素的表a1:n中确定第k小元素，1kn。2. 设计思路 利用Partition过程。在第一次划分后划分元素v测定在aj的位置上，则有j-1个元素小于或等于aj，且有n-j个元素大于或等于aj。此时， 若k=j，则aj即是第k小元素；否则， 若kj，则a1:n中的第k小元素将出现在aj+1:n， 是aj+1:n中的第k-j小元素。选择问题选择问题利用利用Partition实现的选择算法实现的选择算法public static void Select(int n,int k) /在数组a1,an中找第k小元素s并把它放在位置k，假设1kn。 /将剩下的元素按如下方式排列，使

2、ak=t，对于1mk，有amt；对于kmn，有amt。an+1=+ int m,r,j; m=1;r=n+1;an+1=10000; while(true) /每当进入这一循环时，1mkrn+1 j=r; /将剩余元素的最大下标加1后给j j=Partition(m,j); /返回j，它使得aj是第j小的值 if(kj) r=j; /j是新的上界 else if(k=j) return; else m=j+1; /j+1是新的下界 利用利用Partition实现的选择算法实现的选择算法实例分析实例分析算法算法复杂度复杂度分析分析假设假设 a中的元素互异； 随机选取划分元素，且选择am:p-1中

3、任一元素作为划分元素的概率相同。分析分析n 在Select中每次调用Partition(m,j)，所需的元素比较次是 j-m+1。n 在执行一次Partition后，或者找到第k小元素，或者将在缩小的子集(am,k-1或ak+1,j)中继续查找。缩小的子集的元素数将至少比上一次划分的元素数少1。最坏情况最坏情况时间时间 Select的最坏情况时间是的最坏情况时间是O( ) Select的平均情况时间是的平均情况时间是O(n) 最坏情况下的特例：最坏情况下的特例： 输入a恰好使对Partition的第i次调用选用的划分 元素是第i小元素，而k=n。 此时，（区间下界）m随着Partition的每

4、一次调用而仅增加1，j保持不变。 Partition最终需要调用n次。则n次调用的时间总量是：)() ) 1(21nin2n最坏情况时间是最坏情况时间是O(n)的选择算法的选择算法基本思想：精心挑选划分元素v方法：二次取中间值目的：使v比一部分元素小比另一部分元素大使用二次取中规则的选择算法的说明性描述使用二次取中规则的选择算法的说明性描述public static int Select2(int a,int k,int n) /在集合a中找第k小元素 若nr，则采用插入法直接对a分类并返回第k小元素。 把a分成大小为r的个子集合，忽略剩余的元素。 设 是上面 个子集合的中间值的集合。 用Pa

5、rtition划分a，v作为划分元素。 假设v在位置j。 case k=j: return(v); kj: 设S是a1:j-1中元素的集合 return(Select2(S,k,j-1) else:设R是aj+1:n中元素的集合 return(Select2(R,k-j,n-j)rnmmmM/21,rn/2(,/2 ,/)vSelectMn rn rSelect2的的待解决问题待解决问题算法中需要解决的两个问题 1) 如何确定子集合的中间值 当r较小时，采用InsertionSort(a,i,j)直接对每组的r个元素分类，在分类好的序列中，中间元素即为当前r个元素中的中间位置下标对应的元素。

6、2) 如何保存 个子集合的中间值 注：各组找到的中间元素值将调整到数组a的前部，连续保存，从而可用递归调用的方式对这些中间值进行排序并找出中间值的中间值。rn/Select2的实现的实现public static int Sel(int m,int p,int k)/返回一个i，使得i属于m,p，且ai是am:p中第k小元素，r是一个全程变量，其取值为一个大于1的整数。 int i,j,n,temp; if(p-m+1=r) InsertionSort(m,p); return(m+k-1);/返回第k小元素的位置 while(true) n=p-m+1; /元素数 for(i=1;ik) p

7、=j-1; else k=k-(j-m+1); m=j+1; 斯特拉森矩阵乘法斯特拉森矩阵乘法设矩阵A和B是两个nn矩阵，讨论矩阵加法的时间复杂度和矩阵乘法的时间复杂度。矩阵加法：( )矩阵乘法：( )1( , )( , ) ( , )1,k nC i jA i k B k ji jn 分治法解决矩阵乘法（降低计算复杂度）分治法解决矩阵乘法（降低计算复杂度）2n3n观察：矩阵乘法的花费比矩阵加法大 。假设：假设：n=2k其中：111211121112212221222122AABBCCAABBCC1111111221121112122221211122212221122222CA BA BCA BA BCA BA BCA BA B技巧：增加加法减少乘法斯特拉森矩阵乘法斯特拉森矩阵乘法令：令：则：则：112211222122111112222221111112222111111212222122()()()()()()()()()()PAABBQAABRABBSABBTAABUAABBVAABB11122122CPSTVCPTCQSCPRQU7个乘法和个乘法和10个加个加（减）法（减）法 8个加（减）法个加（减）法 斯特拉森斯特拉森矩阵乘法的思想矩阵乘法的思想斯特拉森时间复杂度斯特拉森时间复杂度22( )7 ( /2)2bnT nT nann2212logloglog4