時間の複雑さを検証

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^3)ではなく、O(n^2)回を実行するためです。 ifの場合は、の倍数が1からi*iまで正確にi = O(n)であるため、outerのfor eachステップごとに(i*i)^(1/2) = 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) 
      } 
     } 
    } 
}