随笔-103  评论-224  文章-30  trackbacks-0
   这个问题,解法比较多,假设序列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 春秋十二月 阅读(2080) 评论(0)  编辑 收藏 引用 所属分类: Algorithm

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理