这个算法的渐进时间复杂度

Question

我希望知道以下算法的时间复杂度。乍一看，时间复杂度似乎是O(n^5)，这也是我在大多数网站上看到的内容。但仔细分析似乎给出了不同的答案，以下是代码：

public void fun(int n)
{
   int i,j,k,sum=0;
   for(i=0;i<n;i++)
   {
       for(j=0;j<i*i;j++)
       {
            if(j%i==0)
            {
                for(k=0;k<j;k++)
                sum++;
            }
       }
   }
}

- sasidhar

---

如果 i < j，那么 i % j 是多少？ - chill

@chill 抱歉，那是个打错字了... 应该是 j%i。 - sasidhar

Answer 1

请注意，j%i c== 0将会在每个不同的i上产生trueO(i)次-因此，内部循环将在每个“外部”迭代中重复O(i)次。

因此，复杂度为O(n*n^2 + n*n^3) = O(n^4) 解释如下：
O(n*n^2)是指“中间循环”，它无论是否满足if条件都会重复自身。 它是O(n^3)，因为您得到：1 + 4 + 9 + 16 + ... + n^2这是一个平方和，是O(n^3)。
O(n*n^3)有点棘手：

对于每个 i ，每个内部循环重复 i 次，因此对于每个 i ，您得到： 总共重复 i + 2i + 3i + ... + (i-1)i 次。 很容易看出实际上是i（1 + 2 + ... + i-1），这是O(i ^ 3)。

现在，我们可以看到它对每个 i 都发生-总体复杂度将是（不正式，只是直觉）：O(1^3) + O(2^3) + ... + O(n^3)这是来自立方序列的总和，是O(n ^ 4) 结论： 虽然冷静的分析可能表明是 O(n ^ 5)-因为内部循环不会在每次中间循环迭代中重复自身-但总复杂度是O(n ^ 4)。

- amit