时间戳

首页 > 解决方案 > 时间复杂度 - For 循环

algorithm - 时间复杂度 - For 循环

问题描述

我有一个关于使用 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) ，不会计算变量 time ... if 语句具有恒定时间 O(1) 并且将由 for 循环控制，而 for 循环将具有 O(n )

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

标签： algorithmtime-complexitycomplexity-theory

解决方案

对于第一个代码，您有：

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))

推荐阅读