for-loop - ネストされた for ループのランタイム

Question

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

私の解決策の試み：

j は i*i = n^4 まで反復します。'k' ループの場合、1 から n^4 までの k の合計は n^4(n^4-1)/2 になります。したがって、実行時間は O(n^8) です。これは高すぎると思いますが、エラーは表示されません。

Answer 1

外側のループは n ²回実行されます。^{次のループは ∑<sub>i=1 n 2} i ²の合計を実行します。これは O(n ⁶ ) です。

最も内側のループjは、 が の倍数である場合にのみ実行され、 の値ごとに回数i発生します。最も内側のループは、、、などの値ごとに を実行します。したがって、最も内側のループは、各 に対して ∑<sub>j=1 ⁱ ij 回、つまり O(i ³ ) を実行します。iijji2i3ii*ii

したがって、総実行時間は ∑<sub>i=1 ^{n 2} O(i ³ ) + O(n ⁶ ) であり、 ∑<sub>i=1 ^{n 2} O(i ³ )であるため、これは O(n ⁸ ) です。 = O(n ⁸ )。

j++(2 番目のループが ではなく をインクリメントすると仮定していることに注意してくださいi++。答えが の場合はかなり異なりますi++)。

Answer 2

そう：

i goes from 1 to n*n.
j goes from 1 to i*i

ただし、最も内側のループは、i が j を除算するときにのみ実行されます。1 と i*i の間に、i で割り切れる数が正確に i 個あります。したがって、最も内側のループは、1 から n*n までの各 i に対して i 回実行されます。

ここまでは n^4 です。

しかし、現在、j は最大で i*i なので、最大で n^4 です。

はい、複雑さは O(n^8) です。