这个排序算法的大O [重复]

Possible Duplicate:
What’s the complexity of for i: for o = i+1

可能重复:i的复杂性是什么:o = i + 1

I have done the following sorting algorithm for arrays of length 5:

我为长度为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;
            }
        }
    }

I believe that the complexity of this sorting algorithm is O(n*n) because for each element you compare it with the rest. However, I also notice that for each time we increate in the outer loop, we don't compare with all the rest, but with the rest - i. What would be the complexity?

我相信这种排序算法的复杂性是O(n * n),因为对于每个元素,你将它与其余元素进行比较。但是,我也注意到,每次我们在外循环中增加时,我们都不会与其他所有内容进行比较,但其余部分 - 我。复杂性会是什么?

8 个解决方案

#1

It's still O(n²) (or O(n * n), as you wrote). Only the highest order term matters when analysing computational complexity.

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

#2

You are right:
It's O(1 + 2 + 3... + N)
But mathematically it's just:
= O(n*((n-1)/2))
but that is just:
= O(n^2)

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

#3

You are right, that it is O(n²).

你是对的,它是O(n2)。

Here's how to calculate it. On the first iteration, you will look at n elements; on the next, n - 1, and so on. If you write two copies of that sum, and divide by two, you can pair up the terms, such that you add the first term in the first copy n to the last term of the second copy 1, and so on. You wind up with n copies of n + 1, so the sum winds up being n * (n + 1) / 2. Big-O only distinguishes asymptotic behavior; the asymptotic behavior is described by the highest order term, without regard to constant factor, which is n².

这是如何计算它。在第一次迭代中,您将看到n个元素;在下一个,n - 1,依此类推。如果您写入该总和的两个副本,并除以2,则可以将这些术语配对,以便将第一个副本中的第一个术语添加到第二个副本1的最后一个术语中,依此类推。你得到了n + 1的n个副本,所以总和最多为n *(n + 1)/ 2.Big-O只能区分渐近行为;渐近行为由最高阶项描述,而不考虑常数因子,即n2。

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²)

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

#4

This is bubble sort, and it is indeed of complexity O(n^2)

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

The entire run time of the algorithm can be surmised in the following summation:

算法的整个运行时间可以通过以下求和推测:

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

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

Since only the highest order term is of interest in asymptotic analysis, the complexity is O(n^2)

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

#5

The big O notation is asymptotic. It means that we overlook constant factors such as - i. The complexity of your algorithm is O(N²) (see also here).

大O符号是渐近的。这意味着我们忽略了诸如-i之类的常数因素。算法的复杂程度为O(N²)(另请参见此处)。

#6

The complexity is O(1). The O notation only makes sense for large inputs, with, where an increase or decrease is not only visible, but relevant.

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

If you were to extend it, it would be O(n^2), yes.

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

#7

for multiple loops

用于多个循环

n*m*..no.of loops

for above code in worst case its n*n=n^2

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

BigOh means the max bound.

BigOh表示最大界限。

so the maximum complexity can't be greater then this.

所以最大的复杂性不能大于此。

#8

For i=0 it runs for n time

对于i = 0,它运行n次

i=1 it runs for n-1 time

i = 1,运行n-1次

i=2 it runs for n-2 time ....

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

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

So big O complexity = O(n^2) { upper bound; + or - gets ignored }

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

#1