Java Reference
In-Depth Information
important difference is that a good randomized algorithm has no bad inputs—
only bad random numbers (relative to the particular input). This difference
may seem only philosophical, but actually it is quite important, as we show in
the following example.
Let us say that your boss asks you to write a program to determine the
median of a group of 1,000,000 numbers. You are to submit the program
and then run it on an input that the boss will choose. If the correct answer
is given within a few seconds of computing time (which would be expected
for a linear algorithm), your boss will be very happy, and you will get a
bonus. But if your program does not work or takes too much time, your
boss will fire you for incompetence. Your boss already thinks that you are
overpaid and is hoping to be able to take the second option. What should
you do?
The quickselect algorithm described in Section 8.7 might seem like the
way to go. Although the algorithm (see Figure 8.23) is very fast on average,
recall that it has quadratic worst-case time if the pivot is continually poor.
By using median-of-three partitioning, we have guaranteed that this worst case will
not occur for common inputs, such as those that have been sorted or that contain a
lot of duplicates. However, there is still a quadratic worst case, and as Exercise 8.8
showed, the boss will read your program, realize how you are choosing the
pivot, and be able to construct the worst case. Consequently, you will be
fired.
The running time of
a randomized algo-
rithm depends on
the random num-
bers that occur, as
well as the particu-
lar input.
By using random numbers, you can statistically guarantee the safety of
your job. You begin the quickselect algorithm by randomly shuffling the input
by using lines 10 and 11 in Figure 9.7.
1
As a result, your boss essentially loses
control of specifying the input sequence. When you run the quickselect algo-
rithm, it will now be working on random input, so you expect it to take linear
time. Can it still take quadratic time? The answer is yes. For any original
input, the shuffling may get you to the worst case for quickselect, and thus the
result would be a quadratic-time sort. If you are unfortunate enough to have
this happen, you lose your job. However, this event is statistically impossible.
For a million items, the chance of using even twice as much time as the aver-
age would indicate is so small that you can essentially ignore it. The computer
is much more likely to break. Your job is secure.
Instead of using a shuffling technique, you can achieve the same result
by choosing the pivot randomly instead of deterministically. Take a random
item in the array and swap it with the item in position
low
. Take another
Randomized quick-
select is statistically
guaranteed to work
in linear time.
1. You need to be sure that the random number generator is sufficiently random and that its
output cannot be predicted by the boss.
Search WWH ::
Custom Search