这个排序算法的时间复杂度（Big O）。

Question

我已经为长度为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进行比较。那么它的复杂度会是多少呢？

- Hommer Smith

---

请参见此链接。 - user529758

Answer 1

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

- user529758

Answer 2

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

- Roee Gavirel

Answer 3

你说得对，这是O(n²)。

下面是计算方法。第一轮迭代时，您将查看n个元素；下一轮是n-1，以此类推。如果您将该总和的两个副本写下来，并除以二，则可以配对这些术语，例如，在第一个副本中将第一个术语n与第二个副本中的最后一个术语1相加，依此类推。您最终会得到n个n+1的副本，因此总和最终为n*（n+1）/ 2。Big-O仅区分渐近行为；渐近行为由最高阶项描述，而不考虑常数因子，即n²。

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² + 1/2 * n
  = O(n²)

- Brian Campbell

Answer 4

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

该算法的整个运行时间可以总结在以下求和式中：

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

由于渐近分析只关注最高阶项，因此复杂度为O(n^2)。

- StoryTeller - Unslander Monica

Answer 5

大O符号是一种渐进性的表示法。它意味着我们忽略常数因素，如- i。你的算法的复杂度是O(N²)（也可以参见这里）。

- md5

Answer 6

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

如果您扩展它，则为O(n^2)，是的。

- Luchian Grigore

Answer 7

对于多重循环

n*m*..循环次数

对于上述代码，在最坏情况下，它的复杂度是n*n=n^2

BigOh表示最大边界。

因此，最大复杂度不能超过这个值。

- Arpit

---

不仅在最坏的情况下，而是在任何情况下... - Roee Gavirel

同意你的观点。但是bigoh表示最大边界，因此它是最坏情况 :)。 - Arpit

Answer 8

当 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) {上限; +或-被忽略}

- rai.skumar