时间复杂度 - For 循环

Question

我有一个关于使用 O-Notation 计算时间复杂度的问题。我们已经给出了这个代码..

int a=0; 
For (int j=0; j<n ; j++){ 
    For(int i=0; i*i<j; i++){ 
     a++; } 
}

我认为解决方案是 O(n^2) 对于第一个 for 循环我们需要 n 而对于第二个我们需要 n... 但是我在回答考试问题时..我得了零分它

...还有另一个代码

 int g(int y){ 
  If (y<10){ 
   Return 1;} 
  else { 
    int a=0; 
    for ( int i=0;i<n;j++) { 
        a++;}
      return a+g(2(y/3)+1)+g(2(y/3)+2)+g(2(y/3)+3);}
 }

我认为解决方案是 O(n) ，不会计算变量时间... if 语句具有常数时间 O(1) 并且将由 for 循环和 for 循环支配会有 O(n)

...还有任何解释如何计算程序时间的建议或资源吗？谢谢 :)

Answer 1

对于第一个代码，您有：

T(n) = 1 + sqrt(2) + ... + sqrt(n) = Theta(n\sqrt(n))

因为 i*i < j 表示 i < sqrt(j)。对于第二个，你可以使用 Akra-Bazzi 定理：

T(n) = T(2n/3+1) + T(2n/3+2) + T(2n/3+3) + n

并达到 T(n) = 3 T(2n/3) + n 以使用主定理 (~O(n^2.7))

时间复杂度 - For 循环

Time Complexity- For Loop

algorithm

complexity-theory

time-complexity