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

刘昊源 发布于 2013/12/04 18:58
阅读 150
收藏 0
  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表示出这个函数是什么?

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

加载中
0
fokYaland
fokYaland
时间复杂度是 O(n^2) ,n的平方
fokYaland
fokYaland
算法分析方法: 找出算法中基本操作,假设运行时间为一个常数。 写出总和的时间,然后丢弃常数和低阶项。 N的函数应该就是 O(n^2) 吧。 下面的解答更专业点。 推荐看下 网易公开课里算法导论
刘昊源
刘昊源
具体分析的时候要怎么写呢?还有那个用n表示的函数是什么样子的。能不能帮我解答下呢?谢谢
0
zengxiangwei
zengxiangwei

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
刘昊源
刘昊源

引用来自“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)

谢谢大神解答。。。
返回顶部
顶部