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

我正在学习数据结构类(class)，但不确定如何进行这个 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 没有余数并且乘法规则不适用时才会运行。我的推理在这里正确吗？

最佳答案

让我们在这里暂时忽略外部循环，让我们从 i 的角度分析它。

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

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

最后一个相等来自 sum of arithmetic progression 。
以上在 j 中。

对从 O(i^3) 到 1 的外循环重复此操作，您将获得 n 的运行时间，因为您实际上有:

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) ，这是你的复杂性。

关于algorithm - 这个算法的大O分析是什么？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/29152881/