問題如題目，不過數組是無序數組，數組中元素個數假設為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 閱讀(4591)
評論(5) 編輯 收藏 引用 所屬分類:
算法基礎