時間複雜度驗證

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