元素选择问题总结

http://chenkegarfield.blog.163.com/blog/static/62330008200910249526638/

元素选择问题

注：中位数：中间大小的数 ；上取整用|  |表示，下取整用[ ]表示

1．选最大
输入：n个不等的数
输出：max

算法1    Findmax
1. max←L[1]
2. for i←2 to lenth[L]
        do if max              then max←L[i]
3. return max
算法最坏情况下的时间复杂性为O(n)

结论：在n 个数的数组中找最大的数, 并以比较
作为基本运算的算法类中的任何算法最坏情
况下至少要做n－1 次比较.

证: 因为MAX是唯一的, 其它的n－1个数必
须在比较后被淘汰. 一次比较至多淘汰一个数,
所以至少需要n－1 次比较.
结论: findmax 算法是最优算法.

2．找最大和最小
通常算法：顺序比较
复杂性：W(n)=2n-3

算法2  FindMaxMin
1．将n个元素两两一组分成[n/2]组
2．每组比较，得到[n/2]个较小和[n/2]个较大
3．在[n/2]个 (n为奇数，是[n/2]+1)较小中找最小min
4．在[n/2]个(n为奇数，是[n/2]+1)较大中找最大max
复杂性：行2 比较[n/2]次，行3-4比较至多2*|n/2|-2次，
W(n)=[n/2]+2|n/2|-2=n+|n/2|-2 =|3n/2|-2

3．找第二大

通常算法：顺序比较
1．顺序比较找到最大max;
2．从剩下的n-1个数中找最大，即第二大second
复杂性：W(n)=n-1+n-2=2n-3

算法3：锦标赛方法 改进的方法，最优
1．k←n
2．将k个元素两两一组，分成k/2组
3．每组的2个数比较，找到较大的数
4．将被淘汰的较小的数在淘汰它的数所指向的链表中做记录
5．if k为奇数then k←k/2 +1
6．    else k←k/2
7．if k>1 then goto 2
8．max←最大数
9．second←max的链表中的最大
复杂性：
W(n)=n-1+log n-1= n+log n-2

4．一般性选择问题
输入：数组L, L的长度n, 正整数k, 1≤ k≤ n.
输出：第k小的数
通常算法
1．排序
2．找第k小的数
时间复杂性：O(nlogn)

算法4  Select(S,k)  改进的算法
1．将S划分成5个一组， 共nM=[n/5]个组
2．每组找中位数，nM个中位数放到集合M
3．m*←Select(M,|M|/2) 将S中的数划分成A,B,C,D四个集合
4．把A和D中的每个元素与m*比较，小的构成S1, 大的构成S2
5．S1←S1∪C; S2←S2∪B
6．if k =|S1|+1 then 输出m*
7．else if k≤|S1|
8． then Select(S1,k)
9. else Select(S2,k-|S1|-1)

复杂性估计 更详细的请参考王晓东的《计算机算法设计与分析》（第2版） 电子工业出版社 P24-26

复杂性：W(n)=O(n)
行2： O(n)
行3： W(n/5)
行4： O(n)
行8-9:  O(n)

5.一道综合应用题
给定n个不同数的集合S和正整数i, i
算法A：调用i 次找最大算法findmax , 每调用一次从S中删除一个最大的数。
算法B：对S 排序，并输出S 中最大的i 个数。

问：（1）分析A,B 两个算法在最坏情况下的时间复杂性。
      （2）试设计一个最坏情况下时间复杂性的阶更低的算法。要求用文字说明算法的设计思想；简要给出算法的伪码描述（可以调用学过的算法，对于使用的变量或过程要给与说明，不要求写程序）；分析算法最坏情况下的时间复杂性。

解：
（1）算法A: i*n=O（n3/2）(3/2次方）
         算法B:n*logn

（2）关于算法5的说明：
设k 表示第i 大元素在排好序数组的下标，元素记为x;
用选择算法确定这个元素x，
用x 划分数组S, 将比x 大的放到后边；
排序S 中从k 到n 的元素，倒序输出。

算法5
输入: 集合S
输出：S 中最大的i 个数
1. k←n-i+1;
2. x←Select(S, n, k);
3. 用x划分S，将S 中比x 大的元素放到数组的k +1到n的位置；
4. 排序S[k..n]
5. 倒序输出
复杂度：O(n)+O(i*logi)