keke1314521
ffffff3w5tst
2019-04-12 23:50

最大子列和问题的算法复杂度分析,不懂是怎么求出来的

  • c语言
#include<iostream>
#include<stdio.h>
using namespace std;

int MaxSubsequenceSum(int a[],int n);

int main(){
    //int a[6] = {-2, 11, -4, 13, -5, -2};
    int a[8] = {4, -3, 5, -2, -1, 2, 6, -2};
    printf("%d\n",MaxSubsequenceSum(a,8));
}

int MaxSubsequenceSum(int a[],int n){
    int ThisSum, MaxSum;
    MaxSum = 0;
    for(int i = 0; i < n; i++){
        for(int j = i; j < n; j++){
            ThisSum = 0;
            for(int k = i; k <= j; k++){
                ThisSum += a[k];
            }
            if(ThisSum > MaxSum){
                MaxSum = ThisSum;
            }
        }
    }
    return MaxSum;
}

这是一种O(n^3)的解法,说实话,我是写不来这样高时间复杂度的算法,这个算法重复做了很多的无用的计算,强行将算法复杂化,经过简单的分析,直接可以求 ThisSum += a[k] 语句的次数,就能够得出它的时间复杂度:
图片说明

请问经过简单分析,是怎么分析的。
我假设i=1,经过运算得出 最内层循环执行了(1+n)n/2 次,i=2时 最内层循环执行了(2+n)(n-1)/2次,i=3时,最内层循环执行了(3+n)(n-2)/2次……
因为 i的取值范围是0到N,所以 我尝试把上面的加起来,接下来就不会了,请求赐教,或者告诉我最后图片上的那个是怎么对到出来的

  • 点赞
  • 回答
  • 收藏
  • 复制链接分享

0条回答

为你推荐