2

我有以下代码片段：

sum = 0;
for (i = 0; i < n; i++)
    for (j = 0; j < i; j++)
        sum++;

复杂性会是O(n^2)，但如果我想进一步挖掘内部循环的复杂性，那么它会是(n (n-1))/2还是(n-1)!？

4

6 回答 6

7

是的，O(n^2)，但实际上是 0+1+...+n-1=n(n-1)/2 = O(n^2)，绝对不是 (n-1)！

于 2010-02-10T02:07:36.717 回答
3 
time = n*(n-1)/2
     = (n*n - n)/2

由于 big-O 表示法是一个上限，因此小阶项 (-n) 和常数因子 (1/2) 都被移除（因为它们对于表示时间上限并不重要）以产生大- O 表示法，O(n*n)更广为人知的是O(n^2).

于 2010-02-10T02:12:29.547 回答
1

你可以有一个及时运行的算法

22222222222222 + 4444444444444*n + 9999999999999999999999999*n^2 steps

它仍然是 O(n^2)。

找到比 O 更好的算法运行时间描述是一个悬而未决的问题。

于 2010-02-10T02:47:50.053 回答
0

首先，(n-1)!意味着(n-1)(n-2)...(2)(1)。这显然不是你想要的。

如果你计算实际的迭代次数，它是0 + 1 + 2 + ... + (n-2) + (n-1). 请注意，总和中有n项，我们可以将它们配对，使得每对的平均值为(n-1)/2。（配对最高和最低，次高和次低，等等。）如果n是奇数，你会剩下一个不能配对，但方便的是它的值也是(n-1)/2。因此，您有n术语，所有术语的平均值是(n-1)/2，所以总和是n(n-1)/2。

现在，对于大 O 表示法，我们有多少次迭代并不重要——我们只是想知道极限何时n非常大。请注意，我们的迭代次数可以写为(1/2)n^2 - (1/2)n。对于 very large n，这个n^2词比这个n词大得多，所以我们放弃这个n词。这只是给我们留下了(1/2)n^2，但是大 O 表示法的另一个规则是我们不关心常数因子，所以我们只写它是 O(n^2)。

于 2010-02-10T02:43:40.340 回答
0

就大 O 表示法而言，常量是无关紧要的。

于 2010-02-10T02:06:47.717 回答
0

您计算(n(n-1)/2)的是代码的确切迭代次数。当被问及是否为大 O 的时间复杂度时，您给出的估计值刚好足以表达所花费的时间。

换句话说，您需要找到这样一些THE SMALLEST power,将大于确切的迭代次数。在您的情况下，恰好是并且恰好是。然后是你的时间复杂度。nk (k>0)k * n^powerk1power2O(n^power)

于 2010-02-10T02:11:48.880 回答