Question

这个问题在这里已经有了答案:

如何找到算法的时间复杂度 (9个答案)

封闭 2个月前.

我有一个关于计算时间复杂度的问题与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))