5

可能重复：
for i 的复杂性是多少：for o = i+1

我对长度为 5 的数组执行了以下排序算法：

int myarray[5] = {2,4,3,5,1};
    int i;
    for (i = 0; i < 5; i++)
    {
        printf("%d", myarray[i]);

        int j;
        for (j=i+1; j < 5; j++) 
        {
            int tmp = myarray[i];
            if (myarray[i] > myarray[j]) {
                tmp = myarray[i];
                myarray[i] = myarray[j];
                myarray[j] = tmp;
            }
        }
    }

我相信这种排序算法的复杂性是O(n*n)因为您将每个元素与其他元素进行比较。但是，我也注意到，每次我们在外循环中创建时，我们都不会与所有其余部分进行比较，而是与其余部分进行比较 - i。复杂度会是多少？

4

8 回答 8

7

它仍然是O(n²)（或O(n * n)，如您所写）。在分析计算复杂度时，只有最高阶项很重要。

于 2013-01-23T16:34:25.580 回答
5

你是对的：
它是 O(1 + 2 + 3... + N)
但在数学上它只是：
= O(n*((n-1)/2))
但这只是：
= O(n^2)

于 2013-01-23T16:36:06.793 回答
3

你是对的，它是 O( n 2 )。

以下是如何计算它。在第一次迭代中，您将查看n 个元素；接下来，n - 1，依此类推。如果您将该总和的两个副本写入并除以 2，您可以将这些项配对，这样您将第一个副本n中的第一项添加到第二个副本 1 的最后一项，依此类推。您最终得到n + 1 的n 个副本，因此总和为n * ( n + 1) / 2。Big-O 仅区分渐近行为；渐近行为由最高阶项描述，不考虑常数因子，即n 2。

n + ( n - 1) + ( n - 2) ... + 1
  = 2 * ( n + ( n - 1) + ( n - 2) ... + 1) / 2
  = (( n + 1) + ( n - 1 + 2) + ( n - 2 + 3) + ... + (1 + n )) / 2
  = (( n + 1) + ( n + 1) + ... + ( n + 1)) / 2
  = n * ( n + 1) / 2
  = 1/2 * n 2 + 1/2 * n
  = O( n 2 )

于 2013-01-23T16:46:04.450 回答
2

这是冒泡排序，它的复杂度确实是 O(n^2)

算法的整个运行时间可以用以下总和来推测：

n + (n-1) + (n-2) + ... + 1 = n(n+1)/2

由于在渐近分析中只对最高阶项感兴趣，因此复杂度为 O(n^2)

于 2013-01-23T16:34:11.510 回答
2

大 O 表示法是渐近的。这意味着我们忽略了常数因素，例如- i. 您的算法的复杂性是O(N²)（另请参见此处）。

于 2013-01-23T16:34:17.623 回答
1

对于多个循环

n*m*..no.of 循环

对于上面的代码，在最坏的情况下它的 n*n=n^2

BigOh 表示最大界限。

所以最大复杂度不能大于这个。

于 2013-01-23T16:36:26.003 回答
1

复杂度是O(1)。该O符号仅对大输入有意义，其中增加或减少不仅可见，而且相关。

如果你要扩展它，它会是O(n^2)，是的。

于 2013-01-23T16:35:25.487 回答
0

对于 i=0，它运行 n 次

i=1 它运行 n-1 次

i=2 它运行 n-2 次 ....

  So total Sum = (n) + (n-1) + (n-2) + .... + 1
           sum =  (n*n) - (1 + 2 + ...)
               =  n^2   -

如此大的 O 复杂度 = O(n^2) { 上限；+ 或 - 被忽略 }

于 2013-01-23T17:08:10.540 回答