3

我想知道以下算法的时间复杂度。乍一看，时间复杂度看起来是 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++;
            }
       }
   }
}
4

1 回答 1

2

请注意，这j%i c== 0将产生true O(i)时间（对于每个 distinct 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)有点棘手：

对于 each 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)

于 2012-11-26T09:48:52.377 回答