用任意一种排序算法,将每组中的元素排好序,并取出每组的中位数,共个。
递归调用select来找出这个元素的中位数。如果是偶数,就找它的2个中位数中较大的一个。以这个元素作为划分基准。...)
(2)提取每一组的中值元素,构成集合{31,49,13,25,16};
(3)递归地使用算法求取该集合的中值,得到m=25:
(4)根据m=25,把29个元素划分为3个子数组:
P = {8,17,4,11,3,13,6,19,16,5,7,23,22...(备注:就是说明递归子问题规模是下降的,划分后的两个子数组分别至多有3n/4个元素)
上述算法将每一组的大小定为5,并选取75作为是否作递归调用的分界点。...递归树
5、扩展
分组为什么5个元素一组?3个一组或7个一组行不行?...分析:递归调用
1、求x的工作量与中位数集合的规模有关,其值=n/t有关,t为每组元素数,t越大,其规模越小
2、规约后子问题大小与分组元素数t有关,t越大,子问题规模大。