这个algorithm的大O分析是什么？

我正在研究一个数据结构课程，我不确定如何进行这个大O分析：

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++; 

我最初的想法是，这是减less后的O（n ^ 3），因为最里面的循环只会在j / i没有余数时运行，而乘法规则不适用。 我的推理在这里是正确的吗？

Answer 1

我们在这里忽略外层循环，让我们用i分析它。

中间循环运行i^2次，并且每当j%i == 0时调用内部循环，这意味着你在i, 2i, 3i, ...,i^2上运行它，并且每次运行直到相关的j ，这意味着运行时间的内部循环总和为：

 i + 2i + 3i + ... + (i-1)*i = i(1 + 2 + ... + i-1) = i* [i*(i-1)/2] 

最后的平等来自算术级数的总和 。
以上是O(i^3) 。

重复这个从1到n的外循环，你会得到运行时间O(n^4) ，因为你实际上有：

 C*1^3 + C*2^3 + ... + C*(n-1)^3 = C*(1^3 + 2^3 + ... + (n-1)^3) = = C/4 * (n^4 - 2n^3 + n^2) 

最后一个方程来自立方体的总和
以上是O(n^4) ，这是你的复杂性。