算法课件第2章递归与分治.pptVIP

* 给定线性序集中n个元素和一个整数k，1≤k≤n，要求在最坏情况下，用O(n)时间找出这n个元素中第k小的元素 线性时间选择 实例：n=25 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 2， 3， 13，14，52， 5 ， 7 ， 16，22，23， 6， 12， 29，32，54，8， 17， 33，51，57， 11，25，35，37, 49 排序 13, 16, 29, 33, 35 划分为n/5组 * 线性时间选择 5，16，22，23，7 ，8，17，11，25，14，3，2，13，12，6，29，52， 37， 51，57，49，35，33，32，54 以29作为划分点，重新划分数组 与ｋ值做比较 13, 16, 29, 33, 35 实例：找出中位数（改进的选择算法, k=13） * 将n个输入元素划分成?n/5?个组，每组5个元素，只可能有一个组不是5个元素。用任意一种排序算法，将每组中的元素排好序，并取出每组的中位数，共?n/5?个。 递归调用select来找出这?n/5?个元素的中位数。如果?n/5?是偶数，就找它的2个中位数中较大的一个。以这个元素作为划分基准。 线性时间选择 * 将n个输入元素划分成?n/5?个组，每组5个元素，只可能有一个组不是5个元素。用任意一种排序算法，将每组中的元素排好序，并取出每组的中位数，共?n/5?个。 递归调用select来找出这?n/5?个元素的中位数。如果?n/5?是偶数，就找它的2个中位数中较大的一个。以这个元素作为划分基准。 线性时间选择 设所有元素互不相同。在这种情况下，找出的基准x至少比3(n-5)/10个元素大，因为在每一组中有2个元素小于本组的中位数，而n/5个中位数中又有(n-5)/10个小于基准x。同理，基准x也至少比3(n-5)/10个元素小。而当n≥75时，3(n-5)/10≥n/4所以按此基准划分所得的2个子数组的长度都至少缩短1/4。 * Type Select (Type a[], int p, int r, int k) { if (r-p75) { 用某个简单排序算法对数组a[p:r]排序; return a[p+k-1]; }; int g = (r-p-4)/5; // 组数 for ( int i = 0; i=g; i++ ) 将a[p+5*i]至a[p+5g]的第3小元素 与a[p+i]交换位置; //找中位数的中位数 Type x = Select(a, p, p+g, g/2); int i=Partition(a,p,r, x), j=i-p+1; if (k=j) return Select(a,p,i,k); else return Select(a,i+1,r,k-j); } * Type Select (Type a[], int p, int r, int k) { if (r-p75) { 用某个简单排序算法对数组a[p:r]排序; return a[p+k-1]; }; int g = (r-p-4)/5; // 组数 for ( int i = 0; i=g; i++ ) 将a[p+5*i]至a[p+5g]的第3小元素 与a[p+i]交换位置; //找中位数的中位数 Type x = Select(a, p, p+g, g/2); int i=Partition(a,p,r, x), j=i-p+1; if (k=j) return Select(a,p,i,k); else return Select(a,i+1,r,k-j); } 复杂度分析 T(n)=O(n) * Type Select (Type a[], int p, int r, int k) { if (r-p75) { 用某个简单排序算法对数组a[p:r]排序; return a[p+k-1]; }; int g = (r-p-4)/5; // 组数 for ( int i = 0; i=g; i++ ) 将a[p