您的位置: 首页  >  文章  >  最大子列和（时间复杂度）代码实现及结果对比

最大子列和（时间复杂度）代码实现及结果对比

分类: 文章 • 2024-11-13 17:56:04

题目：给定N个整数的序列{A1,A2,A3...ANA_1,A_2,A_3...A_N}, 求函数f(i,j)=max(0,Σk=1jAk)f(i,j)=max(0,\Sigma_{k=1}^jA_k)的最大值

这一部分是浙大数据结构第一章节的一道题目，主要目的是讲解时间复杂度。

文章目录

方法一

  • 直接使用循环遍历的方法。
int MaxSubseqSum1( int A[], int N)
{
	int ThisSum, MaxSum = 0;
	int i,j,k;
	for (i=0; i<N, i++){//左边最小值
		for (j=i; j<N; j++){//右边最小值
			ThisSum = 0;
			for (k=i; k<=j; k++)//中间全部加和
				ThisSum +=A[k];
			if(ThisSum > MaxSum)//如果大于最大值
				MaxSum = ThisSum;//替换
		}
	}
}
  • 这种方法比较暴力，需要全部遍历，因为嵌套了3层循环，所以时间复杂度为T(N)=O(N3)T(N)=O(N^3)

方法二

  • 第一步在进行k循环时很显然是没有必要的，因为每次增加一个j的时候，只需要在上一步ThisSum上加一个A[j]A[j]就可以了。
int MaxSubseqSum1( int A[], int N)
{
	int ThisSum, MaxSum = 0;
	int i,j,k;
	for (i=0; i<N, i++){
		for (j=i; j<N; j++){
			ThisSum += A[j];//在上一个的基础上直接加一个A[j]就可以了
			if(ThisSum > MaxSum)
				MaxSum = ThisSum;
		}
	}
}
  • 这种方法只嵌套了两个循环，所以时间复杂度为T(N)=O(n2)T(N)=O(n^2).

方法三：分而治之

前两种方法都比较好理解，这种分而治之的方法就有一定的难度了。这个问题的本质是一个递归的问题。

把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并.

分治法在每一层递归上都有三个步骤：

  1. 分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；

  2. 解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题

  3. 合并：将各个子问题的解合并为原问题的解。

对于这一个问题，可以简化先进行分析：
最大子列和（时间复杂度）代码实现及结果对比

  1. 首先，假设数组中有8个元素，如上图所示，我们先沿红色的线从中间分开，得到两部分，发现可以进一步的划分，直到使用黄色的线划分完毕。
  2. 首先看4，-3，我们可以看出最大的值为4，这里我们记下最大值为4，然后看5，-2，记下最大值5.同样的道理可以得到最大值2，6。
  3. 下一步，我们来看跨越分割线的最大值，首先是4，-3，5，-2这4个数。从-3开始向右，得到最大的值要加到4，然后向左，得到最大的值为5，这样得到跨越边界的最大值为6，比较红线右侧得到的最大值，得到最大值为6。同理我们可以得到左侧的最大值为8.
    4.同理继续向下，跨越红色的最大值为11，这样得到所有子空间的最大值为11。

以上就是使用分而治之的思想得到的最大值的结果。

这一部分的代码见完整代码部分。

方法四：在线处理

在线处理的方法是这些的方法中时间复杂度最小的算法。就我的理解写一些。
最大子列和（时间复杂度）代码实现及结果对比
这种算法只需要遍历一遍数组，其核心的思想是置零的那一部分。分为

  1. 首先从第一个非零数字开始，向后加和。
  2. 在加的过程中不断的判断是否为最大值，将最大值储存。
  3. 直到遇到子列和负值，将已经得到的最大值保存，然后结束这一部分，直到遇到下一个正数再重新进行第1步。

带入到上图中的例子，第一个数为-1，直接舍掉，第二个为正3，最大值记为3，加上第三个数-2，为1小于3，最大值仍然为3，加上4，最大值变为5，大于3，此时最大值变为5.因为加上下一个数之后小于零，所以这一部分计算结束，这部分子空间的最大值为5.从下一个1开始，可以得到最大值为7，所以最大的子空间的加和为7.

int MaxSubseqSum4( intA[], 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)T(N) = O(N),已经是时间复杂度最小的方法。

完整代码及对比

#include <stdio.h>
#include <time.h>
#include <math.h>

clock_t start, stop;

double duration;

int MaxSubseqSum1( int A[], int N)
{
	int ThisSum, MaxSum = 0;
	int i,j,k;
	for (i=0; i<N; i++){
		for (j=i; j<N; j++){
			ThisSum = 0;
			for (k=i; k<=j; k++)
				ThisSum +=A[k];
			if(ThisSum > MaxSum)
				MaxSum = ThisSum;
		}
	}
	return MaxSum;
}

int MaxSubseqSum2( int A[], int N)
{
	int ThisSum, MaxSum = 0;
	int i,j,k;
	for (i=0; i<N; i++){
		for (j=i; j<N; j++){
			ThisSum +=A[j];
			if(ThisSum > MaxSum)
				MaxSum = ThisSum;
		}
		ThisSum = 0;
	}
	return MaxSum;
}

int Max3( int A, int B, int C )
{ /* 返回3个整数中的最大值 */
    return A > B ? A > C ? A : C : B > C ? B : C;
}

int DivideAndConquer( int List[], int left, int right )
{ /* 分治法求List[left]到List[right]的最大子列和 */
    int MaxLeftSum, MaxRightSum; /* 存放左右子问题的解 */
    int MaxLeftBorderSum, MaxRightBorderSum; /*存放跨分界线的结果*/

    int LeftBorderSum, RightBorderSum;
    int center, i;

    if( left == right )  { /* 递归的终止条件，子列只有1个数字 */
        if( List[left] > 0 )  return List[left];
        else return 0;
    }

    /* 下面是"分"的过程 */
    center = ( left + right ) / 2; /* 找到中分点 */
    /* 递归求得两边子列的最大和 */
    MaxLeftSum = DivideAndConquer( List, left, center );
    MaxRightSum = DivideAndConquer( List, center+1, right );

    /* 下面求跨分界线的最大子列和 */
    MaxLeftBorderSum = 0; 
    LeftBorderSum = 0;
    for( i=center; i>=left; i-- ) { /* 从中线向左扫描 */
        LeftBorderSum += List[i];
        if( LeftBorderSum > MaxLeftBorderSum )
            MaxLeftBorderSum = LeftBorderSum;
    } /* 左边扫描结束 */

    MaxRightBorderSum = 0; RightBorderSum = 0;
    for( i=center+1; i<=right; i++ ) { /* 从中线向右扫描 */
        RightBorderSum += List[i];
        if( RightBorderSum > MaxRightBorderSum )
            MaxRightBorderSum = RightBorderSum;
    } /* 右边扫描结束 */

    /* 下面返回"治"的结果 */
    return Max3( MaxLeftSum, MaxRightSum, MaxLeftBorderSum + MaxRightBorderSum );
}

int MaxSubseqSum3( int A[], int N )
{ /* 保持与前2种算法相同的函数接口 */
    return DivideAndConquer( A, 0, N-1 );
}

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;
}

int main(){
	int N = 8;
	int max1, max2, max3, max4;
	int A[8] = {-1, 3, -2, 4, -6, 1, 6, -1};

	start = clock();
	max1 = MaxSubseqSum1(A, N);
	stop = clock();
	duration = ((double)(stop-start))/CLOCKS_PER_SEC;
	printf("Max1 = %d\n",max1);
	printf("duration1 = %6.2e\n",duration);

	start = clock();
	max2 = MaxSubseqSum2(A, N);
	stop = clock();
	duration = ((double)(stop-start))/CLOCKS_PER_SEC;
	printf("Max2 = %d\n",max2);
	printf("duration2 = %6.2e\n",duration);

	start = clock();
	max3 = MaxSubseqSum3(A, N);
	stop = clock();
	duration = ((double)(stop-start))/CLOCKS_PER_SEC;
	printf("Max3 = %d\n",max3);
	printf("duration3 = %6.2e\n",duration);

	start = clock();
	max4 = MaxSubseqSum4(A, N);
	stop = clock();
	duration = ((double)(stop-start))/CLOCKS_PER_SEC;
	printf("Max4 = %d\n",max4);
	printf("duration4 = %6.2e\n",duration);
}
  • 再贴一下运行的结果，其实已经可以看出来速度的差距了
Max1 = 7
duration1 = 3.00e-06
Max2 = 7
duration2 = 2.00e-06
Max3 = 7
duration3 = 2.00e-06
Max4 = 7
duration4 = 1.00e-06
[Finished in 2.1s]

参考文献

五大常用算法之一：分治算法
PTA 数据结构题目（1）：最大子列和问题（分而治之、在线处理算法）

相关推荐