嵌套循环中模数的时间复杂度

Question

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

我知道最外层的循环执行n次，下一个循环执行n^2次，但我如何将j% I与循环分解?正确的答案是0 (N^4)，但我不确定这是怎么得到的。

Answer 1

因为我们知道k循环只在j被i整除时执行(这是模的来源)，我们可以计算出k在每个i循环中循环的次数:

• i = 2, j:1..4:循环2次(j=2).
• i = 3, j:1..9:循环3 + 6次(j=3,6)。
• i = 4, j:1..16:循环4 + 8 + 12次(j=4,8,12)。
• …
• i = n, j:1..n*n:循环n + 2n + ... (n - 1) * n
  • 或者Sum(k * n, k = 1, n - 1)=n^2 * (n - 1) / 2times.

我意识到这应该在i = n - 1停止，但这足以显示增长。

这意味着我们的复杂度是 的复杂度

2 + (3 + 6) + (4 + 8 + 12) + ... + (n^2 * (n - 1) / 2)
=Sum(
i^2 * (i - 1) / 2, 
i = 2, n - 1
)
=Sum(
(i^3 - i^2) / 2, 
i = 2, n - 1
)

由于i^3项占主导地位，除以2无关紧要，因此它具有与

相同的时间复杂度。

Sum(i^3, i=2, n - 1)

即O(n^4)