类型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、f 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)