这个算法的Big O分析是什么？

Question

我正在学习数据结构课程，但我不确定如何继续进行此 Big 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++;

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

Answer 1

这里暂且忽略外层循环，用i.

来分析一下

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

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

最后一个相等来自sum of arithmetic progression。
以上内容在O(i^3).

在从 1 到 n 运行的外循环中重复此操作，您将获得 O(n^4) 的运行ning 时间，因为您实际有：

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)

最后一个等式来自sum of cubes
而上面是在O(n^4)，就是你的复杂度

What is the Big O analysis of this algorithm?