这个算法的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.

中间循环运行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),这是你的复杂性.