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 ⁶ )，即 O(n ⁸ )，因为 ∑<sub>i=1 ^{n 2} O(i ³ ) = O(n ⁸ )。

（请注意，我假设第二个循环递增j++，而不是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)。