应用7：线性时间选择(续)
设所有元素互不相同。在这种情况下， 找出的基准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。
T
(n)
C2
n
T
(n
C1 / 5)
T
(3n
/
4)
n 75 n 75
根据定理有：
f (n)
பைடு நூலகம்
c2n 1 1
3
20c2n
(n)
54
因此，T(n)=O(n)。
补充：定理
• 定理：令b, d和c1,c2是大于0的常数，则如下递归
方程
• 的解是：
f
(n
)
b f (floor
(c1n))
f
n 1 (floor(c2n))
for ( int i = 0; i<=(r-p-4)/5; i++ ) 将a[p+5*i]至a[p+5*i+4]的第3小元素 与a[p+i]交换位置;
//找中位数的中位数，r-p-4即上面所说的n-5 Type x = Select(a, p, p+(r-p-4)/5, (r-p-4)/10); 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); }
复杂度分析
• 设对n个元素的数组调用Select需要T(n)时 间，那么找中位数的中位数x至多用了T(n/5) 时间。
• 我们已经证明：按照算法所选的基准x进行 划分所得到的两个子数组分别至多有3n/4个 元素。所以无论对哪一个子数组调用Select 都至多用了T(3n/4)的时间。
• 因此，
复杂度分析（续）
• (12) 因为k=4,而第一、第二个子数组的 元素个数为4，所以33即为所求取的第18 个小元素。
应用7：线性时间选择(续)
Type Select(Type a[], int p, int r, int k) {
if (r-p<75) { 用某个简单排序算法对数组a[p:r]排序; return a[p+k-1]; };
应用7：线性时间选择
应用7：线性时间选择
问题：给定线性序集中n个元素和一个整数k，1≤k≤n，要求 找出这n个元素中第k小的元素
第1种算法 template<class Type> Type RandomizedSelect(Type a[],int p,int r,int k) {
if (p==r) return a[p]; int i=RandomizedPartition(a,p,r), j=i-p+1; if (k<=j) return RandomizedSelect(a,p,i,k); else return RandomizedSelect(a,i+1,r,k-j); }
例子（续）
• (9) 因为k=4，第一个子数组的元素个数大于k， 所以放弃后面两个子数组，以k=4对第一个子 数组递归调用本算法；
• (10) 将这个子数组分成5个元素的一组： {31,33,35,37,32}，取其中值元素为33；
• (11) 根据33，把第一个子数组划分成 {31,32,29},{33},{35,37,41};
– P={8,4,11, 3,13,6,19,16,5,7,23,22} – Q={25} – R={31,60,33,51,57,49,35,43,37,52,32,54,41,46,29}
例子（续）
• (5) 由于|P|=13,|Q|=1,k=18，所以放弃P,Q， 使k=18-13-1=4，对R递归地执行本算法；
• (6) 将R划分成3(floor(18/5))组：
{31,60,33,51,57},{49,35,43,37,52},{32,54,41,46, 29} • (7) 求取这3组元素的中值元素分别为：{51,43,41}， 这个集合的中值元素是43; • (8) 根据43将R划分成3组：
– {31, 33, 35,37,32, 41, 29},{43},{60, 51,57, 49, 52,54, 46}
• (1) 把前面25个元素分为5(=floor(29/5))组； (8,31,60,33,17),(4,51,57,49,35),(11,43,37,3,13),(52,6,19,25 ,32),(54,16,5,41,7).
• (2) 提取每一组的中值元素，构成集合{31,49,13,25,16}； • (3) 递归地使用算法求取该集合的中值，得到m=25； • (4) 根据m=25, 把29个元素划分为3个子数组：
应用7：线性时间选择(续)
将n个输入元素划分成n/5个组，每组5 个元素，只可能有一个组不是5个元素。用 任意一种排序算法，将每组中的元素排好 序，并取出每组的中位数，共n/5个。
递归调用select来找出这n/5个元素的 中位数。如果n/5是偶数，就找它的2个 中位数中较大的一个。以这个元素作为划 分基准。
bn
n2
f
(n)
(n log (n)
n)
c1 c2 1 c1 c2 1
• 特别地，当c1+c2<1时，有
f (n) bn O(n) 1 c1 c2
郑宗汉.算法设计与分析.清华大学出版社.2005.pp.91.
返回
应用7：线性时间选择(续)
上述算法将每一组的大小定为5，并选 取75作为是否作递归调用的分界点。 这2点保证了T(n)的递归式中2个自 变量之和n/5+3n/4=19n/20=εn， 0<ε<1。这是使T(n)=O(n)的关键之 处。当然，除了5和75之外，还有其 他选择。
应用7：线性时间选择(续)
在最坏情况下，算法randomizedSelect 需要O(n2)计算时间。
但可以证明，算法randomizedSelect可 以在O(n)平均时间内找出n个输入元素中 的第k小元素。
第2种算法：例子
• 按递增顺序，找出下面29个元素的第18个元素： 8,31,60,33,17,4,51,57,49,35,11,43,37,3,13,52,6,19,25,32,5 4,16,5,41,7,23,22,46,29.
应用7：线性时间选择(续)
如果能在线性时间内找到一个划分基准，使 得按这个基准所划分出的2个子数组的长度 都至少为原数组长度的ε倍(0<ε<1是某个正 常数)，那么就可以在最坏情况下用O(n)时 间完成选择任务。
应用7：线性时间选择(续)
例如，若ε=9/10，算法递归调用所产生 的子数组的长度至少缩短1/10。所以， 在最坏情况下，算法所需的计算时间 T(n)满足递归式T(n)≤T(9n/10)+O(n) 。 由此可得T(n)=O(n)。