Why is the runtime of the Selection Algorithm O(n)

问题:

According to Wikipedia, the Selection Algorithm has runtime of O(n), but I am not convinced by it. Can anyone explain why is it O(n)?

In the normal quick-sort, the runtime is O(n log n). Every time we partition the branch into two branches (greater than the pivot, and lesser than the pivot), we need to continue process both sides of the branches, whereas Selection Algorithm only needs to process one side of the branch. I totally understand these points. But if you think of Binary Search Algorithm, after we chose the middle element, we are also continue searching one side of the branch. So does that make the algorithm O(1)? No, of course, the Binary Search Algorithm is still O(log N) instead of O(1). This is also the same thing as search element in a Binary Search Tree. We only search for one side, but we still consider O(log n) instead of O(1).

Can someone explain why in Selection Algorithm, if we continue search for one side, it can be consider O(1) instead of O(log n)? To me, I consider the algorithm to be O(n log n), O(N) for partitoning, and O(log n) for number of times to continue finding.

回答1:

There are several different selection algorithms, from the much simpler quickselect (expected O(n), worst-case O(n²)) to the more complex median-of-medians algorithm (Θ(n)). Both of these algorithms work by using a quicksort partitioning step (time O(n)) to rearrange the elements and position one element into its proper position. If that element is at the index in question, we're done and can just return that element. Otherwise, we determine which side to recurse on and recurse there.

Let's now make a very strong assumption - suppose that we're using quickselect (pick the pivot randomly) and on each iteration we manage to guess the exact middle of the array. In that case, our algorithm will work like this: we do a partition step, throw away half of the array, then recursively process one half of the array. This means that on each recursive call we end up doing work proportional to the length of the array at that level, but that length keeps decreasing by a factor of two on each iteration. If we work out the math (ignoring constant factors, etc.) we end up getting the following time:

• Work at the first level: n
• Work after one recursive call: n / 2
• Work after two recursive calls: n / 4
• Work after three recursive calls: n / 8
• ...

This means that the total work done is given by

n + n / 2 + n / 4 + n / 8 + n / 16 + ... = n (1 + 1/2 + 1/4 + 1/8 + ...)

Notice that this last term is n times the sum of 1, 1/2, 1/4, 1/8, etc. If you work out this infinite sum, despite the fact that there are infinitely many terms, the total sum is exactly 2. This means that the total work is

n + n / 2 + n / 4 + n / 8 + n / 16 + ... = n (1 + 1/2 + 1/4 + 1/8 + ...) = 2n

This may seem weird, but the idea is that if we do linear work on each level but keep cutting the array in half, we end up doing only roughly 2n work.

An important detail here is that there are indeed O(log n) different iterations here, but not all of them are doing an equal amount of work. Indeed, each iteration does half as much work as the previous iteration. If we ignore the fact that the work is decreasing, you can conclude that the work is O(n log n), which is correct but not a tight bound. This more precise analysis, which uses the fact that the work done keeps decreasing on each iteration, gives the O(n) runtime.

Of course, this is a very optimistic assumption - we almost never get a 50/50 split! - but using a more powerful version of this analysis, you can say that if you can guarantee any constant factor split, the total work done is only some constant multiple of n. If we pick a totally random element on each iteration (as we do in quickselect), then on expectation we only need to pick two elements before we end up picking some pivot element in the middle 50% of the array, which means that, on expectation, only two rounds of picking a pivot are required before we end up picking something that gives a 25/75 split. This is where the expected runtime of O(n) for quickselect comes from.

A formal analysis of the median-of-medians algorithm is much harder because the recurrence is difficult and not easy to analyze. Intuitively, the algorithm works by doing a small amount of work to guarantee a good pivot is chosen. However, because there are two different recursive calls made, an analysis like the above won't work correctly. You can either use an advanced result called the Akra-Bazzi theorem, or use the formal definition of big-O to explicitly prove that the runtime is O(n). For a more detailed analysis, check out "Introduction to Algorithms, Third Edition" by Cormen, Leisserson, Rivest, and Stein.

Hope this helps!

回答2:

Let me try to explain the difference between selection & binary search.

Binary search algorithm in each step does O(1) operations. Totally there are log(N) steps and this makes it O(log(N))

Selection algorithm in each step performs O(n) operations. But this 'n' keeps on reducing by half each time. There are totally log(N) steps. This makes it N + N/2 + N/4 + ... + 1 (log(N) times) = 2N = O(N)

For binary search it is 1 + 1 + ... (log(N) times) = O(logN)

回答3:

In Quicksort, the recursion tree is lg(N) levels deep and each of these levels requires O(N) amount of work. So the total running time is O(NlgN).

In Quickselect, the recurision tree is lg(N) levels deep and each level requires only half the work of the level above it. This produces the following:

N * (1/1 + 1/2 + 1/4 + 1/8 + ...)

or

N * Summation(1/i^2)
    1 < i <= lgN

The important thing to note here is that i goes from 1 to lgN, but not from 1 to N and also not from 1 to infinity.

The summation evaluates to 2. Hence Quickselect = O(2N).

回答4:

Quicksort does not have a big-O of nlogn - it's worst case runtime is n^2.

I assume you're asking about Hoare's Selection Algorithm (or quickselect) not the naive selection algorithm that is O(kn). Like quicksort, quickselect has a worst case runtime of O(n^2) (if bad pivots are chosen), not O(n). It can run in expectation time n because it's only sorting one side, as you point out.

回答5:

Sorting = rearranging elements is O(n log n), but selection is something like taking the ith element = indexing. And for that both in a linked list, or binary tree it is O(n).

回答6:

Because for selection, you're not sorting, necessarily. You can simply count how many items there are which have any given value. So an O(n) median can be performed by counting how many times each value comes up, and picking the value that has 50% of items above and below it. It's 1 pass through the array, simply incrementing a counter for each element in the array, so it's O(n).

For example, if you have an array "a" of 8 bit numbers, you can do the following:

int histogram [ 256 ];
for (i = 0; i < 256; i++)
{
    histogram [ i ] = 0;
}
for (i = 0; i < numItems; i++)
{
    histogram [ a [ i ] ]++;
}
i = 0;
sum = 0;
while (sum < (numItems / 2))
{
    sum += histogram [ i ];
    i++;
}

At the end, the variable "i" will contain the 8-bit value of the median. It was about 1.5 passes through the array "a". Once through the entire array to count the values, and half through it again to get the final value.