时间复杂度验证

Question

所以我有这个代码块：

int sum=0; 
for (int i=1; i<n; ++i){ 
    for (int j=1; j<i*i; ++j){ 
     if (j%i==0){ 
      for (int k=0; k<j; ++k){ 
       ++sum; 
      } 
     } 
    } 
} 

，我想通这有$ O（N^5）$的复杂性。我试着对此进行计时来验证，但我无法确定是否最适合使用$ n^4 $或$ n^5 $。

Answer 1

复杂度是n^4。 原因是，第三个将运行O(n^2)时间而不是O(n^3)，因为您可能已计算。 if case只会被称为(i*i)^(1/2) = O(n)次，因为从1到i*i的i的倍数数字恰好是i = O(n)。

所以我有这个代码块：

int sum=0; 
for (int i=1; i<n; ++i){ 
    for (int j=1; j<i*i; ++j){   // O(n) 
     if (j%i==0){ 
      for (int k=0; k<j; ++k){ // O(n^2) 
       ++sum;     // O(n^4) 
      } 
     } 
    } 
}