分治算法

    这两天在学习算法，看到了时间复杂度和空间复杂独的问题，就看到了一个问题：有一组向量，我们用数组表示，怎样能够求出这个数组中连续的一组数，并且要求最大？
   
    在思考这个问题的时候，我开始的想法是：用上三个循环嵌套，这样可能会是许多初学者的首选方法：
/*
 *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