问题如题目，不过数组是无序数组，数组中元素个数假设为n
下面介绍第一种最朴素的做法：
设定两个变量，first和second，然后依次遍历数组；如果当前遍历元素a[i]比first大，则second = first， first = a[i]；如果当前遍历元素a[i]比first小，则再比较a[i]与second的大小，如果a[i]比second大，则second = a[i]，否则second值不变。那么上面算法的复杂度是多少呢？我先写出代码再分析复杂度，代码比较简单：
1 int find_second_1(int *a, int n) {
2 assert(a != NULL && n > 1);
3 int first = a[0];
4 int second = a[1];
5 if (first < second) {
6 first = a[1];
7 second = a[0];
8 }
9 for (int i = 2; i < n; ++i) {
10 if (a[i] > first) {
11 second = first;
12 first = a[i];
13 } else {
14 if (a[i] > second) {
15 second = a[i];
16 }
17 }
18 }
19 return second;
20 }
其实这个问题很容易就能写出O(n)复杂度的算法，反而想写出比O(n)复杂度高的还不太容易，所以我们这里就着重分析比较次数，上面算法可以看出在n>2时，比较次数跟给定数组当前状况有关，比如，如果当前数组已经递增有序，则算法只需要比较n - 1次；但是如果当前数组已经递减有序，则算法需要比较2n - 3次，所以我们可以知道上面算法的最坏情况比较次数为2n - 3，最好情况比较次数为n - 1；我们这里假设数组中的数的大小符合均匀随机分布，则当前a[i]比first大的概率为0.5，当前a[i]比first小的概率也为0.5，所以总的期望比较次数=1 + 0.5(n - 2) + 0.5 * 2 * (n - 2) = 1.5n - 2；所以总结如下：
算法的最坏情况比较次数为2n - 3，
算法的最好情况比较次数为n - 1，
算法的期望比较次数为1.5n - 2；
那么能不能改进算法让使得在最坏情况下也比较1.5n + c次呢？c为一小常数。答案是肯定的。
上面算法中，在扫描数组的时候每次取一个元素和first以及second比较，那么我们能不能每次取两个元素a[i]和a[i + 1]呢？这两个元素先确定大小关系，假设为tmpfirst以及tmpsecond，这只需一次比较，然后再通过类似归并排序的归并步骤确定first、second和tmpfirst、tmpsecond两个有序子数组合并后的newfirst和newsecond，这只需要确定的2次比较，综上可知每次取两个元素的话总的比较次数为3次，而原来算法确定两个元素a[i]和a[i + 1]需要2次（最好）或4次（最差）比较。这样就让算法固定在1.5n + c次比较，具体c是多少，我们先写代码看：
1 int find_second_2(int *a, int n) {
2 assert(a != NULL && n > 1);
3 int first = a[0];
4 int second = a[1];
5 if (first < second) {
6 first = a[1];
7 second = a[0];
8 }
9 for (int i = 2; i < n - 1; i += 2) {
10 int tmpfirst = a[i];
11 int tmpsecond = a[i + 1];
12 if (tmpfirst < tmpsecond) {
13 tmpfirst = a[i + 1];
14 tmpsecond = a[i];
15 }
16 if (first > tmpfirst) {
17 if (second < tmpfirst) {
18 second = tmpfirst;
19 }
20 } else {
21 first = tmpfirst;
22 if (first < tmpsecond) {
23 second = tmpsecond;
24 }
25 }
26 }
27 if (n % 2) {
28 if (a[n - 1] < first) {
29 if (a[n - 1] > second) {
30 second = a[n - 1];
31 }
32 } else {
33 second = first;
34 first = a[n - 1];
35 }
36 }
37 return second;
38 }
上面算法需要区分n为偶数和奇数的情况，通过分析代码我们可以得出如下结论：
若n为偶数，则总的比较次数 = 1 + 1.5 * (n - 2) = 1.5n - 2；
若n为奇数，则总的比较次数 = 1 + 1.5 * (n - 3) + 1 = 1.5n - 2.5或总的比较次数 = 1 + 1.5 * (n - 3) + 2 = 1.5n - 1.5
可以知道，上面算法确实可以将总的比较次数限定在1.5n + c的范围，且c比较小。
那么现在又有问题了，能不能通过每次取多于2个元素比如每次取3个元素a[i]、a[i + 1]、a[i + 2]，一次性确定3个元素的大小，比如tmpfirst、tmpsecond、tmpthird，然后再确定first、second以及tmpfirst、tmpsecond、tmpthird这五个元素中前两大的元素，我们可以计算一下，确定a[i]、a[i + 1]、a[i + 2]三个元素的大小关系至少需要三次比较，这样平摊到每个元素需要1次比较，而上面算法确定两个元素大小只需要一次比较，平摊到一个元素只需要0.5次比较，所以每次取多于2个元素的方法行不通。
那么还有没有其他的办法呢？
仔细分析前面的算法，它的核心思想是每确定a[i]和a[i + 1]的大小关系之后就紧接着和first以及second比较来更新first和second，那我们能不能先依次确定(a[1]、a[2])，(a[3]、a[4])，...，(a[n - 1]、a[n])，然后再确定(a[1]、a[2]、a[3]、a[4])，...，(a[n - 3]、a[n - 2]、a[n - 1]、a[n])，这样依次合并，最后确定(a[1]、a[2]、...、a[n])的first和second，这不就是分治的思想嘛…和归并排序一样一样的。代码如下：
1 #define INF -10000000
2
3 struct first_and_second {
4 int first;
5 int second;
6 };
7
8 first_and_second find_second_3(int *a, int start, int end) {
9 assert(a != NULL);
10 first_and_second res;
11 if (start > end) {
12 res.first = res.second = INF;
13 } else if (start == end) {
14 res.first = a[start];
15 res.second = INF;
16 } else if (start == end - 1) {
17 if (a[start] > a[end]) {
18 res.first = a[start];
19 res.second = a[end];
20 } else {
21 res.first = a[end];
22 res.second = a[start];
23 }
24 } else {
25 first_and_second t1 = find_second_3(a, start, ((end - start) >> 1) + start);
26 first_and_second t2 = find_second_3(a, (((end - start) >> 1) + start + 1), end);
27 if (t1.first > t2.first) {
28 res.first = t1.first;
29 if (t2.first > t1.second) {
30 res.second = t2.first;
31 } else {
32 res.second = t1.second;
33 }
34 } else {
35 res.first = t2.first;
36 if (t1.first > t2.second) {
37 res.second = t1.first;
38 } else {
39 res.second = t2.second;
40 }
41 }
42 }
43 return res;
44 }
算法是很漂亮，同样来分析一下比较次数吧：
根据递归，可以很容易写出如下递推式：T(n) = 2T(n/2) + 2，其中2T(n/2)是子问题需要的比较次数，2是两个子问题归并需要的次数。根据《算法导论》主定理，我们可以知道T(n)是O(n)的，哈哈！我们至少没有写出一个比O(n)高阶的算法！但是还没有办法确定n前面的系数到底有多大，我们下面就简单递推一下：
T(n) = 2T(n/2) + 2 = 2(2T(n/4) + 2) + 2 = 2[2(2T(n/8) + 2) + 2] + 2 = ... = 2
[log2n - 1]T(n/ 2
[log2n - 1] ) + 2
1 + 2
2 + ... + 2
[log2n - 1] = (n/2)T(2) + n - 2，又易知T(2)为1，所以T(n) = 1.5n - 2，上面的计算并不是非常严谨 ，但是不会影响判断1.5的得出，所以我们可以看出，虽然采用了分治的方法，但是比较次数并没有降低，其实仔细思考的话会发现分治和上面的每次取两个元素比较的思想是等同的。
上面仅仅是针对取数组中第二大数来分析的，如果要取数组中第k大数的话就不适用了，具体可以参见《算法导论》中位数与顺序统计章节，里面的介绍很精彩。
posted on 2012-09-05 14:43
myjfm 阅读(4428)
评论(5) 编辑 收藏 引用 所属分类:
算法基础