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

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

阅读 193

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表示的函数是什么样子的。能不能帮我解答下呢？谢谢

回复举报

曾相未

2013/12/04 20:36

该评论暂时无法显示，详情咨询 QQ 群：点此入群

刘昊源

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) 引用此答案举报