Geek asks and answers

Big O of this sorting algorithm

Possible duplicate:
What is the difficulty for i: for o = i + 1

I performed the following sorting algorithm for arrays of length 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 the complexity of this sorting algorithm O(n*n)is because for each element you are comparing it with the rest. However, I also notice that every time we increase the outer loop, we do not compare it with everyone else, but with the rest - i. What will be the difficulty?

+5
source share
8 answers

He is still O(nĀ²)(or O(n * n), as you wrote). When analyzing the complexity of calculations, only the highest order matters.

+7
source

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

+5

, O (n 2).

, . n ; , n - 1 .. , , n 1, . n n + 1, 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)

+3

, O (n ^ 2)

:

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

, O (n ^ 2)

+2

O . , , - i. O(NĀ²) (. ).

+2

O(1). O , , , .

, O(n^2), .

+1

n * m * .. no loops

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

BigOh means maximum border.

therefore, the maximum complexity cannot be greater than this.

+1
source

For i = 0, it runs for n time

i = 1 is executed n-1 times

i = 2 holds for n-2 times ....

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

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

0
source

More articles:


All Articles