请简单解释一下为什么这个代码片段有O(n^4)的复杂度？

Question

评估以下代码片段的Big-Oh：

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

这是我的算法教科书中的作业问题class。教科书上的答案是O(n^4)。我试过很多方法来解决这个问题，但我总是得到 O(n^5)。

我正在使用求和法并从最内层的嵌套循环向外进行数学计算。这里没有显示求和，因为我不知道如何在这个space中表达我的数学，但请按照我下面的工作。

这是我最内层循环的逻辑：

for( k = 0; k < j; ++k )

我的想法是内部循环进行 j+1 次迭代，它可以和 i*i 一样大，它本身可以和 n 一样大，所以这个循环作为一个O(n^2) 的上限。

这是我对中间循环的逻辑：

for( j = 1; j < i * i; ++j )

j 迭代高达 i^2 次，其本身可以高达 n，因此此循环的上限为 O(n^2)。

这是我的外循环逻辑：

for( i = 1; i < n; ++i )

i 迭代高达 n 次，因此循环的上限为 O(n).

O(n * n^2 * n^2) = O(n^5)

同样，答案是 O(n^4)。请帮助我，使用数学循环来帮助您回答。请使用简单的语言。我对算法分析还是个新手。

Answer 1

诀窍就在这一行：

if( j % i == 0 )

这样做是为了确保内部循环仅在 j 是 i 的整数倍时执行；否则没有工作完成。

所以您可以想到的一种快捷方式是说这是 O(n * n^2 / n * n^2) = O(n^4)。

您可以考虑的另一种方式是，这相当于写作：

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

这是O(N^4)通过检查。

Please explain in simple terms why this code fragment has O(n^4) complexity?