Chinaunix首页 | 论坛 | 博客
  • 博客访问: 560078
  • 博文数量: 61
  • 博客积分: 2438
  • 博客等级: 大尉
  • 技术积分: 871
  • 用 户 组: 普通用户
  • 注册时间: 2010-07-28 08:04
文章分类
文章存档

2013年(1)

2012年(8)

2011年(15)

2010年(37)

分类: LINUX

2010-09-04 17:31:30

    这两天在学习算法,看到了时间复杂度和空间复杂独的问题,就看到了一个问题:有一组向量,我们用数组表示,怎样能够求出这个数组中连续的一组数,并且要求最大?
   
    在思考这个问题的时候,我开始的想法是:用上三个循环嵌套,这样可能会是许多初学者的首选方法:
/*
 *function: divide and conquer algrithm
 */

#include

#define  N  10

int max(int sum, int maxsofer)
{
    return (sum > maxsofer ? sum : maxsofer);
}

int main(int argc, char *argv[])
{
    int   data[N] = {22, -21, 76, -90, 78, 90, -87, 43, -10, 100};
    int   i, j, k;
    int   maxsofer = 0;
    int   sum = 0;

    for(i  = 0; i < N; i++){
        for(j = i; j < N; j++){
            sum = 0;
            for(k = i; k <= j; k++)
                sum += data[k];
            maxsofer = max(sum, maxsofer);
        }
    }

    /*Output*/
    printf("%d\n", maxsofer);

    return 0;
}
这样写,对于那个N比较小的情况下是比较适用的,但是,如果有兴趣的话,可以在自己的机子上把N改为10000或者更大的试试,根据粗略估算,应该是1000的话会超过20分钟。。。
    当然有更好的办法,现在就一起讨论一下“分治”(partition)算法。
    分治算法的基本思想是:将一个比较大的问题分解成几个小问题,例如,上面的那段代码的时间复杂度是N^3级。如果把数组分成两段,照着上面的代码再写后,时间复杂度会降低很多的。。。
    而且,分治算法就是根据这种思想总结出来的:先分别求出那两小数组的最大连续段,然后就在解决中间的问题,我们将其分为C1, C2, C3, 而C3就是C1 C2中C1左段最大向量和C2右段最大向量就是C3,根据这个思想,在加上递归,就是这个算法的核心思想.
    下面是我根据书上的伪代码写的一段代码:

/*
 *function: divide and conquer algorithm
 * time complexity of the problem solving
 */


#include <stdio.h>

#define N 10

int maxnum(int *, int, int);
int max(int, int);
int max_3(int, int, int);

int max_3(int a, int b, int c)
{
    return ((a > b ? a : b) > c ? (a > b ? a : b) : c);
}

int max(int data1, int data2)
{
    return (data1 > data2 ? data1 : data2);
}

int maxnum(int data[], int low, int high)
{
    int mid, num, i;
    int rmax, lmax;

    if( low > high ) //if no element is returned to 0

        return 0;
    if( low == high ) //there is only one element

        return max(0, data[0]);
    mid = (low + high) / 2;
    /*find max crossing to right*/
    rmax = num = 0;
    for(i = mid + 1; i <= high; i++){
        num += data[i];
        rmax = max(rmax, num);
    }
    /*find max crossing to left*/
    lmax = num = 0;
    for(i = mid; i >= low; i--){
        num += data[i];
        lmax = max(lmax, num);
    }

    return max_3( lmax + rmax, maxnum(data, low, mid), maxnum(data, mid + 1, high) );
}

int main(int argc, char *argv[])
{
    int data[N] = {31, -41, 59, 26, -53, 58, 97, -93, -23, 84};
    int low = 0, high = N - 1;
    int max;

    max = maxnum(data, low, high);
    /*Output*/
    printf("%d\n", max);

    return 0;
}


希望能和大家一起分享,一起学习。。。
open free share
阅读(4441) | 评论(1) | 转发(0) |
给主人留下些什么吧!~~

chinaunix网友2010-09-07 09:01:11

Download More than 1000 free IT eBooks: http://free-ebooks.appspot.com