這個問題，解法比較多，假設序列X大小為N，一種普通的做法是先設定最大值和最小值都為序列中第一個元素值，在一個循環內，每次循環都和當前最大值和最小值來比較更新，這樣就需要2N-2次比較了；再進一步，如果先查找最大值，則需N-1次比較，再查找最小值，則需N-2次比較，總共是2N-3次比較，比上一方法少了1次。這些做法都是每次取1個數來比較，比較次數為O(2N)。接下來，我們把情況擴展到每次取多于1個數，先試試看每次取2個數，即N-2個數的解，對N個數求解。當N=1時，最大值和最小值就是第1個元素值；當N=2時，最大值和最小值就是第1個元素和第2個元素的最大值和最小值；考察X[N-2]和X[N-1]，同時令前N-2個數的解是MAX和MIN，易見，做3次比較便能得出新的最大值和最小值，首先比較X[N-2]和X[N-1]，然后將其中大數同MAX比較，小數同MIN比較，這樣一來，大約需O(3N/2)次比較即可，而不是先前的O(2N)次。那么，是不是每次取3個或4個數能更進一步減少總共的比較次數呢？有趣地是，可以證明，每次取多于2個數來比較時，總共所需次數和取2個元素來比較是一樣的。本文示例的是每次取2個數比較的實現，C++代碼描述如下
1
//動態數組版本1，T須支持operator < 運算
2template<typename T>
3void get_max_min(const T* p, size_t n, T& max, T& min)
4
{
5
assert(n);
6
7 T t_max, t_min, p_min, p_max;
8 p_min = p_max = p[0];
9
10 size_t i;
11 for(i = 1;i < n-1; i+=2)
12
{
13 if (p[i+1] < p[i])
14 t_max = p[i], t_min = p[i+1];
15 else
16 t_max = p[i+1],t_min = p[i];
17
18 if (p_max < t_max)
19 p_max = t_max;
20
21 if (t_min < p_min)
22 p_min = t_min;
23
}
24 if (i == n-1)
25 {
26 if (p_max < p[n-1])
27 p_max = p[n-1];
28 else if (p[n-1] < p_min)
29 p_min = p[n-1];
30 }
31 min = p_min;max = p_max;
32
}
33
34//靜態數組版本2, T須支持operator < 運算
35template<typename T,size_t N>
36void get_max_min(const T (&p)[N],T& max, T& min)
37{
38 get_max_min(p,N,max,min);
39} 對于以上代碼的實現，由前面分析可知，當N為奇數時，總共比較次數為3/2*(N-1)；當N為偶數時，總共比較次數為3N/2-1，時間復雜度為0(3N/2)。
posted on 2011-07-03 18:05
春秋十二月 閱讀(2169)
評論(0) 編輯 收藏 引用 所屬分類:
Algorithm