Intuitive explanation for why QuickSort is n log n?
Is anybody able to give a 'plain english' intuitive, yet formal, explanation of what makes QuickSort n log n? From my understanding it has to make a pass over n items, and it does this log n times...Im not sure how to put it into words why it does this log n times.
Each partitioning operation takes O(n) operations (one pass on the array). In average, each partitioning divides the array to two parts (which sums up to log n operations). In total we have O(n * log n) operations.
Ie in average log n partitioning operations and each partitioning takes O(n) operations.
The log n part comes from the fact that it's (at least ideally) breaking the input in half at each iteration. Starting from N items, and breaking those in half each time means that you're down to 1 item after log2(N) iterations, at which point you obviously can't subdivide it any further. For example, starting from, say, 128 items, you divide into groups of 64, 32, 16, 8, 4, 2, 1 items -- 7 iterations (and log2(128) = 7).
Each of those iterations scans through the entire array to partition it, so you end up with O(log N) operations, each of which has O(n) complexity, for O(n log n) overall complexity.
To be technically correct, the Big-O is O(N2). This arises from the fact that a sufficiently bad choice of partition element could split the array into one element on one side, and the entire rest of the array on the other. If this happens at every iteration, it takes N iterations to split it down into pieces of one element apiece, so you get N operations, each with a complexity of O(N), for O(N * N) overall.
In a real implementation you usually stop before that, but that is the furthest you could go.
Well, it's not always n(log n). It is the performance time when the pivot chosen is approximately in the middle. In worst case if you choose the smallest or the largest element as the pivot then the time will be O(n^2).
To visualize 'n log n', you can assume the pivot to be element closest to the average of all the elements in the array to be sorted. This would partition the array into 2 parts of roughly same length. On both of these you apply the quicksort procedure.
As in each step you go on halving the length of the array, you will do this for log n(base 2) times till you reach length = 1 ie a sorted array of 1 element.
链接地址: http://www.djcxy.com/p/39684.html上一篇: 为新的初学者