这个问题，解法比较多，假设序列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
春秋十二月 阅读(2132)
评论(0) 编辑 收藏 引用 所属分类:
Algorithm