正文

算法:元素选择问题总结2006-01-15 16:42:00

【评论】 【打印】 【字体: 】 本文链接:http://blog.pfan.cn/xiangyu/9660.html

分享到:

元素选择问题

注:中位数:中间大小的数 ;上取整用|  |表示,下取整用[ ]表示

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)

 

 

 

 

 

 

 

 

阅读(9362) | 评论(8)


版权声明:编程爱好者网站为此博客服务提供商,如本文牵涉到版权问题,编程爱好者网站不承担相关责任,如有版权问题请直接与本文作者联系解决。谢谢!

评论

loading...
您需要登录后才能评论,请 登录 或者 注册