Why is bubble sort O(n^2)?

问题:

int currentMinIndex = 0;

for (int front = 0; front < intArray.length; front++)
{
    currentMinIndex = front;

    for (int i = front; i < intArray.length; i++)
    {
        if (intArray[i] < intArray[currentMinIndex])
        {
            currentMinIndex = i;
        }
    }

    int tmp = intArray[front];
    intArray[front] = intArray[currentMinIndex];
    intArray[currentMinIndex] = tmp;
}

The inner loop is iterating: n + (n-1) + (n-2) + (n-3) + ... + 1 times.

The outer loop is iterating: n times.

So you get n * (the sum of the numbers 1 to n)

Isn't that n * ( n*(n+1)/2 ) = n * ( (n^2) + n/2 )

Which would be (n^3) + (n^2)/2 = O(n^3) ?

I am positive I am doing this wrong. Why isn't O(n^3)?

回答1:

You are correct that the outer loop iterates n times and the inner loop iterates n times as well, but you are double-counting the work. If you count up the total work done by summing the work done across each iteration of the top-level loop you get that the first iteration does n work, the second n - 1, the third n - 2, etc., since the ith iteration of the top-level loop has the inner loop doing n - i work.

Alternatively, you could count up the work done by multiplying the amount of work done by the inner loop times the total number of times that loop runs. The inner loop does O(n) work on each iteration, and the outer loop runs for O(n) iterations, so the total work is O(n²).

You're making an error by trying to combine these two strategies. It's true that the outer loop does n work the first time, then n - 1, then n - 2, etc. However, you don't multiply this work by n to to get the total. That would count each iteration n times. Instead, you can just sum them together.

Hope this helps!

回答2:

Your inner loop is iterating, IN TOTAL, as you said n + (n-1) + (n-2) + (n-3) + ... + 1 times. So it is O(n + (n-1) + (n-2) + (n-3) + ... + 1) = O(n(n+1)/2) = O(n^2)

回答3:

The inner loop iterates n times(in worst case):

for(int i = front; i < intArray.length; i++)

The outer loop iterates n times:

for(int front = 0; front < intArray.length; front++)

Therefore O(n^2)

回答4:

How you basically calculate N...

• Each line: +1

• Each Loop *N

  So you start adding numbers get to your first loop now you have N+1, you keep going and you eventually get N*N or N^2 for the time plus some number. Pulling off the number as it is generally insignificant compared to N.

Pretty much N is a representation of all the items in the loop kind of like 1,2,3...N. So it is simply representing a number not how many times a loop, loops.

回答5:

k=1(sigma k)n = n(n+1)/2
because:
  s = 1 +  2    + ... + (n-1) + n
  s = n + (n-1) + ... + 2     + 1
+)
===================================
  2s = n*(n+1)
   s = n(n+1)/2
in bubble sort, 
(n-1) + (n-2) + ... + 1 + 0 times compares 
which means, k=0(sigma k)n-1
, k=0(sigma k)n-1 equals [k=1(sigma k)n] - n
therefore, n(n+1)/2 - n = n(n-1)/2
which is 1/2(n^2-n) => O(1/2(n^2-n))
in big O notation, we remove constant, so
O(n^2-n)
n^2 is larger than n
O(n^2)

回答6:

Just for the sake of having some Python version of bubble sort...

def bubble_sort(input):
    n = len(input)
    iterations = 0
    for i in xrange(n, 1, -1):
        for j in range(0, i - 1):
            iterations += 1
            if input[j] > input[j+1]:
                input[j],input[j+1] = input[j+1],input[j]

    print iterations
    return input

Iterations was added to the inner loop to count the total iterations. Nothing to do with bubble sort.

Passing an array of 5 elements, results in 15 iterations not 25. Also when pre-sorted it also results in 15 iterations. But the complexity must also take into account the comparison and the swapping.