algorithm - 请简单解释一下为什么这个代码片段的复杂度是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

这是我的算法课教科书中的作业问题。课本上给出的答案是O(n^4)。我尝试了多种方法来解决这个问题，但总是得到O(n^5)。

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

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

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)。