問題如題目，不過數(shù)組是無序數(shù)組，數(shù)組中元素個數(shù)假設為n
下面介紹第一種最樸素的做法：
設定兩個變量，first和second，然后依次遍歷數(shù)組；如果當前遍歷元素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)復雜度高的還不太容易，所以我們這里就著重分析比較次數(shù)，上面算法可以看出在n>2時，比較次數(shù)跟給定數(shù)組當前狀況有關，比如，如果當前數(shù)組已經遞增有序，則算法只需要比較n - 1次；但是如果當前數(shù)組已經遞減有序，則算法需要比較2n - 3次，所以我們可以知道上面算法的最壞情況比較次數(shù)為2n - 3，最好情況比較次數(shù)為n - 1；我們這里假設數(shù)組中的數(shù)的大小符合均勻隨機分布，則當前a[i]比first大的概率為0.5，當前a[i]比first小的概率也為0.5，所以總的期望比較次數(shù)=1 + 0.5(n - 2) + 0.5 * 2 * (n - 2) = 1.5n - 2；所以總結如下：
算法的最壞情況比較次數(shù)為2n - 3，
算法的最好情況比較次數(shù)為n - 1，
算法的期望比較次數(shù)為1.5n - 2；
那么能不能改進算法讓使得在最壞情況下也比較1.5n + c次呢？c為一小常數(shù)。答案是肯定的。
上面算法中，在掃描數(shù)組的時候每次取一個元素和first以及second比較，那么我們能不能每次取兩個元素a[i]和a[i + 1]呢？這兩個元素先確定大小關系，假設為tmpfirst以及tmpsecond，這只需一次比較，然后再通過類似歸并排序的歸并步驟確定first、second和tmpfirst、tmpsecond兩個有序子數(shù)組合并后的newfirst和newsecond，這只需要確定的2次比較，綜上可知每次取兩個元素的話總的比較次數(shù)為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 }
上面算法需要區(qū)分n為偶數(shù)和奇數(shù)的情況，通過分析代碼我們可以得出如下結論：
若n為偶數(shù)，則總的比較次數(shù) = 1 + 1.5 * (n - 2) = 1.5n - 2；
若n為奇數(shù)，則總的比較次數(shù) = 1 + 1.5 * (n - 3) + 1 = 1.5n - 2.5或總的比較次數(shù) = 1 + 1.5 * (n - 3) + 2 = 1.5n - 1.5
可以知道，上面算法確實可以將總的比較次數(shù)限定在1.5n + c的范圍，且c比較小。
那么現(xiàn)在又有問題了，能不能通過每次取多于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 }
算法是很漂亮，同樣來分析一下比較次數(shù)吧：
根據(jù)遞歸，可以很容易寫出如下遞推式：T(n) = 2T(n/2) + 2，其中2T(n/2)是子問題需要的比較次數(shù)，2是兩個子問題歸并需要的次數(shù)。根據(jù)《算法導論》主定理，我們可以知道T(n)是O(n)的，哈哈！我們至少沒有寫出一個比O(n)高階的算法！但是還沒有辦法確定n前面的系數(shù)到底有多大，我們下面就簡單遞推一下：
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的得出，所以我們可以看出，雖然采用了分治的方法，但是比較次數(shù)并沒有降低，其實仔細思考的話會發(fā)現(xiàn)分治和上面的每次取兩個元素比較的思想是等同的。
上面僅僅是針對取數(shù)組中第二大數(shù)來分析的，如果要取數(shù)組中第k大數(shù)的話就不適用了，具體可以參見《算法導論》中位數(shù)與順序統(tǒng)計章節(jié)，里面的介紹很精彩。
posted on 2012-09-05 14:43
myjfm 閱讀(4652)
評論(5) 編輯 收藏 引用 所屬分類:
算法基礎