您的位置: 首页  >  文章  >  数据结构复习：解决最大子列和问题的四种算法来看时间复杂度优化的重要性

数据结构复习：解决最大子列和问题的四种算法来看时间复杂度优化的重要性

分类: 文章 • 2023-03-30 08:51:25

给定N个整数的序列｛A1,A2,····,An｝，求函数 数据结构复习：解决最大子列和问题的四种算法来看时间复杂度优化的重要性 的值

             即从A1到An的的这一连续的一个整数序列中，求出某一连续的一段子列的最大的和是多少。负数就返回0结束。

 

 

算法1 

int maxSubseqSum1(int A[],int N)
{
  int i,j,k;
  int ThisSum,MaxSum = 0;
  for( i = 0; i<N; i++)    /* i是子列左端位置 */
  {
    for( j = i; j<N; j++ )  /* j是子列右端的位置 */
    {
       ThisSum = 0;        /* ThisSum是从A[i]到A[j]的子列和 */
       for( k = i; k <=j; k++ )
       ThisSum += A[k];
       if(ThisSum>MaxSum)      /* 如果刚得到的这个子列和更大 */
       MaxSum = ThisSum;      /* 则更新结果 */
    }   /* j循环结束 */
  }     /* i循环结束 */
  return MaxSum;
}

这个算法很容易想到，当然该算法的时间复杂度也是大的可怕，为T(N)=O(N^3)

仔细分析该算法，发现该算法做了无用功，当j增加1时，我们没有必要从头算起，我们只要在前面i~j的部分和后面加一个元素就行，没有必要重新算前面i~j部分和，也就是说，k循环是多余的。

 

算法2

数据结构复习：解决最大子列和问题的四种算法来看时间复杂度优化的重要性

时间复杂度为 T(N) = O(N^2) 。

效率虽比前一个算法要好一点，但想像一下当n = 10000 时，可想而知这样的运算量依然非常的大。

面对像n^2，n^3这样的时间复杂度的算法或函数，每一个算法设计师或者资深程序猿的目标都是希望能将其改造成 log n 这样的时间复杂度，而非指数增长。

我们可以接着继续优化它，来看算法3

 

 

算法3（分而治之法）

“分而治之”的思想可以解决很多问题，大概思路是把一个较大的复杂的问题，切分成小的块，然后分头去解决它们，最后再把结果合并起来。

解题思路：把数组从中间一分为二，然后递归地去解决左右两边的问题，分别得到左右两边的最大子列和，但此时我们还不能下定论，还需要考虑跨越边界的最大子列和，即得到这三个结果，返回其中的最大值。

该算法的时间复杂度为T(N)=O(N*logN)，较之前两个有很大改进。

int Max(int A, int B, int C)
{
    /*return A > B ? A > C ? A :C: B > C ? B : C;*/
    if (A > B) {
        if (A > C)
            return A;
        else
            return C;
    }
    else if (B > C)
        return B;
    else return C;

}
int DivideAndConquer(int List[], int left, int right) {
    int MaxLeftSum, MaxRightSum;
    int MaxLeftBoardSum, MaxRightBoardSum;
    int LeftBoardSum, RightBoardSum;
    int center,i;
    /*递归终止条件*/
    if (left == right) {
        if (List[left] > 0)
            return List[left];
        else
            return 0;
    }


    center = (right + left) / 2;
    MaxLeftSum = DivideAndConquer(List, left, center);
    MaxRightSum= DivideAndConquer(List, center+1, right);

    MaxLeftBoardSum = 0; LeftBoardSum = 0;
    for (i = center;i >= left; i--)
        LeftBoardSum += List[i];
    if (LeftBoardSum > MaxLeftBoardSum)
        MaxLeftBoardSum = LeftBoardSum;
    MaxRightBoardSum = 0; RightBoardSum = 0;

    for (i = center + 1; i <= right; i++)
        RightBoardSum += List[i];
    if (RightBoardSum > MaxRightBoardSum)
        MaxRightBoardSum = RightBoardSum;

    return Max(MaxLeftSum, MaxRightSum, MaxRightBoardSum + MaxLeftBoardSum);


}
int maxsequence3(int A[], int N)
{
    return DivideAndConquer(A, 0, N-1);
}

 

 

算法4：在线处理法

int MaxSubseqSum4 (int A[], int N)
{
    int ThisSum, MaxSum;
    int i;
    ThisSum = MaxSum = 0;
    for( i=0 ; i<N ; i++ )
        ThisSum += A[i];     /*向右累加*/
        if( ThisSum > MaxSum )
            MaxSum = ThisSum;     /*发现更大和则更新当前结果*/
        else if( ThisSum < 0 )    /*如果当前子列和为负*/
            ThisSum = 0;         /*则不可能使后面的部分和增大，抛弃之*/
    }
    return MaxSum;
}

为什么叫在线处理呢，因为这个程序是一个一个的读入数字并且来进行累加，如果累加得到的是负数就抛弃之，因为不可能使得加上后面的数会更大。数据结构复习：解决最大子列和问题的四种算法来看时间复杂度优化的重要性

时间复杂度为  T(N) = O(N) 

这是我们得到的解决最大子列和问题的最快的算法了。

 

 

四种算法运行时间比较

数据结构复习：解决最大子列和问题的四种算法来看时间复杂度优化的重要性

NA代表 not available，跑不动了不算了的意思

可想而知，解决同样的问题，不一样的算法会造就的不一样的时间复杂度。而我们在解决问题的时候，如何去优化算法，降低其时间复杂度，将是我们要思考的问题！

 

 

 

 

 

 

参考：《数据结构》陈越、何钦铭

 

 

 

 

 

 

 

 

 

 

相关推荐