请简单地解释为什么这段代码片段具有O（n^4）的复杂性？

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 

这是我的算法类教科书的家庭作业的问题。教科书中所述的答案是O(n^4)。我尝试了很多方法来解决这个问题，但我总是得到O(n^5)。

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

这里是我的最里面的循环逻辑：

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