for (i=0; i<n; i++) {
ThisSum = 0;
for (j=i; j<n; j++) {
ThisSum = ThisSum + A[j];
MaxSum = max(MaxSum,ThisSum);
}
这个代码中ThisSum = ThisSum + A[j]用n表示出这个函数是什么?
怎么分析时间复杂度。求各位帮忙结下。。。谢谢真诚的谢谢
}
这个代码中ThisSum = ThisSum + A[j]用n表示出这个函数是什么?
怎么分析时间复杂度。求各位帮忙结下。。。谢谢真诚的谢谢
引用来自“zengxiangwei”的答案
for (i=0; i<n; i++) {
ThisSum = 0; t2
for (j=i; j<n; j++) {
ThisSum = ThisSum + A[j]; t3
MaxSum = max(MaxSum,ThisSum); t4
}
T = t1 + n*(t2+t4) +(n + (n-1)+ ...+1 ) * t3
T = t1 + n*(t2+t4) + (n*(n+1)/2 ) * t3 =c1 + c2*n +c3*n^2 = O(n^2)