分治法之选择问题 (1).ppt

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。 /将剩下的元素按如下方式排列，使ak=t，对于1mk

2、，有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中任一元素作为划分元素的概率相同。 分析 在Select中每

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

4、择算法,基本思想：精心挑选划分元素v 方法：二次取中间值 目的：使v比一部分元素小比另一部分元素大,使用二次取中规则的选择算法的说明性描述,public static int Select2(int a,int k,int n) /在集合a中找第k小元素 若nr，则采用插入法直接对a分类并返回第k小元素。 把a分成大小为r的个子集合，忽略剩余的元素。 设 是上面 个子集合的中间值的集合。 用Partition划分a，v作为划分元素。 假设v在位置j。 case k=j: return(v); kj: 设S是a1:j-1中元素的集合 return(Select2(S,k,j-1) else:设R

5、是aj+1:n中元素的集合 return(Select2(R,k-j,n-j) ,Select2的待解决问题,算法中需要解决的两个问题 1) 如何确定子集合的中间值 当r较小时，采用InsertionSort(a,i,j)直接对每组的r个元素分类，在分类好的序列中，中间元素即为当前r个元素中的中间位置下标对应的元素。 2) 如何保存 个子集合的中间值 注：各组找到的中间元素值将调整到数组a的前部，连续保存，从而可用递归调用的方式对这些中间值进行排序并找出中间值的中间值。,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+1k) p=j-1; else k=k-(j-m+1); m=j+1; ,斯特拉森矩阵乘法,设矩阵A和B是两个nn矩阵，讨论矩阵加法的时间复杂度和矩阵乘法的时间复杂度。 矩阵加法：( ) 矩阵乘法：( ),分治法解决矩阵乘法（降低计算复杂度）,观察：矩阵乘法的花费比矩阵加法大 。,假设：n=2k,其中：,技巧：增加加法减少乘法,斯特拉森矩阵乘法,令：,则：