complexity help..O(n^2), 0(nlog) etc_问答_开发者

hey there could someone please help me determine the complexity?. An example given in my class was

bubble sort

int main() {
   int a[10] = {10,9,8,7,6,5,4,3,2,1};开发者_如何学Go
   int i,j,temp;

   for (j=0;j<10;j++) {
      for (i=0;i<9;i++) {
         if (a[i] > a[i+1]) {
            temp = a[i];
            a[i] = a[i+1];
            a[i+1] = temp;
         }
      }
   }
   for (i=0;i<10;i++) {
      printf("%d ",a[i]);
   }
}

which had a complexity of O(n^2) because it had two loops of O(n) hence O(n) x O(n).

and they said quicksort has an complexity of O(nlog(n)) .. why is this?

is it because as it goes around a loop it divides a number?

-thanks

There's no quick one sentence explanation. Quick sort is actually O(n²) in the worst case but it is O(n log n) on average, so if you try to analyze it you will not be able to prove that it is always O(n log n). It is only O(n log n) on average, averaged across all possible data sets. For any particular list it might be worse.

If the pivots end up being really, really bad then quick sort will perform very badly. This can happen on already sorted data, for instance, if you always choose a fixed element at the beginning or end of the array as the pivot element.

Other sorting algorithms like merge sort and heap sort, on the other hand, are always O(n log n). They do not have pathological cases where their performance degrades to O(n²). This makes them preferable if what you desire is consistent, predictable performance at all times. The advantage of quick sort is that is overall a faster algorithm on average, just not always so.

Edit: Indeed, as @pst says, merge sort requires O(n) space when sorting arrays (scratch space for the merges), which is less than ideal. That's a point against it. But then another point against quick sort is that it is an unstable sort. Elements that are equal to each other may be shuffled around after the sort.

Timsort is an awesome new search algorithm—well, less new, more a great combination of existing algorithms plus a lot of fine tuning and clever optimizations (the galloping thing is money). Read that text file for a glimpse of Great Programming.

Big-O notation is simply a relationship between the input value (number of elements in your case) and the complexity (time complexity in your case, van also be space complexity).

You're correct about the bubble sort. Because it loops n times inside another loop of n times, the time complexity is O(n²).

Quicksort is slightly different. It does a number of passes which depends on n but, in each case, it manages to put all the values lower than the midpoint on the "left" and all values higher than the midpoint on the "right" - both halves are still unsorted but you know that the all the left elements are less than any of the right elements (let's call this the pivot rule).

This basically chops the workload in half for each sub-loop which leads to average case O(log n). Similar to binary search or balanced trees, any algorithm that divides the workload by a factor for each iteration is O(log n).

Combining the two gives you O(n log n).

This wikipedia page actually shows a nice little graphic on the top right that shows quicksort in action. Since a picture is worth a thousand words (and an animation is worth a thousand pictures), you should look at that for a while to understand.

You'll see that it first divides the workspace in two then swaps elements between the two halves until the pivot rule is met.

Because the workload is divided into two totally separate independent areas, quicksort is ripe for parrallel processing with no resource contention. Provided you have enough processors, as soon as you've partitiond the data into two areas, you can give each area to a separate processor for further partitioning. This is not possible with bubble sort since that sort doesn't give you two independent areas.

See the analysis on Wikipedia.

Actually quicksort is O(n log(n)) in the average case. In the worst case you pick the largest or smallest element as the partition every time and do n + (n -1) + ... 1 = O (n ^ 2).

In the best case (the average case works out to the same big-O) you do n comparisons for the first partition. This makes two calls on problems of size n / 2 and those calls take n / 2 comparisons to partition. This continues so you get n + 2 * (n / 2) + 4 * (n /4) + ... . There are log(n) total terms and each one is n so the whole thing is O(n*log(n)).

As Thon said you can get the same result by applying Master's theorem, but it's probably worth your time to do some examples by hand.

The previous answers describe quicksort and its running time pretty well, but I want to comment on the worst-case running time.

It is true that quicksort in general is O(n log n) in the average case (given a random permutation of inputs) and O(n^2) in the worst case. However, quicksort in general doesn't specify which element to partition around at every step, so the O(n^2) case arises when you pick any element (usually the first or the last) as the pivot without regard to its relation to other elements in the list.

You can implement quicksort to run in worst-case O(n log n) by choosing the pivot wisely. One method is to find the median in O(n) time. (See http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_.22Median_of_Medians_algorithm.22) Then if you always partition around the median, the number of times any element is examined is at most O(log n), so that the total running time is O(n log n).

Quicksort is recursive. Simply write out the pseudocode and you can easily derive a recursive formula for each repetition's run time, and then use the Master Theorem to arrive at the final answer.

Contrary to the opinion of all people here, the complexity of your program is O(1). You haven't defined what n is. I know, my answer seems a bit daft, but in practice it is often more important to find the bounds of your problem than the complexity of the algorithm. If your dataset will never be bigger than a given size, you may better use a simpler method which has good enough performance/behaviour.