求解代码复杂度的分析。。

刘昊源发布于 2013/12/04 18:58

阅读 150

MaxSum = 0;
   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表示出这个函数是什么？

怎么分析时间复杂度。求各位帮忙结下。。。谢谢真诚的谢谢

加载中

fokYaland

2013/12/04 19:17

时间复杂度是 O(n^2) ,n的平方

评论 (2) 引用此答案举报

fokYaland

2013/12/04 22:25

算法分析方法：找出算法中基本操作，假设运行时间为一个常数。写出总和的时间，然后丢弃常数和低阶项。 N的函数应该就是 O(n^2) 吧。下面的解答更专业点。推荐看下网易公开课里算法导论

回复举报

刘昊源

2013/12/04 19:37

具体分析的时候要怎么写呢？还有那个用n表示的函数是什么样子的。能不能帮我解答下呢？谢谢

回复举报

zengxiangwei

2013/12/04 20:36

ThisSum = ThisSum + A[j] 是累加

MaxSum = 0; t1

   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 +(n + (n-1)+ ...+1 ) * （t3+t4)

T = t1 + n*t2 + (n*(n+1)/2 ) * (t3+t4) =c1 + c2*n +c3*n^2 = O(n^2)

评论 (0) 引用此答案举报

刘昊源

2013/12/04 20:39

引用来自“zengxiangwei”的答案

MaxSum = 0; t1
   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)

谢谢大神解答。。。

评论 (0) 引用此答案举报