最大子列和问题的算法复杂度分析,不懂是怎么求出来的
#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,所以 我尝试把上面的加起来,接下来就不会了,请求赐教,或者告诉我最后图片上的那个是怎么对到出来的

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问