Java Reference
In-Depth Information
2. Monte Carlo Algorithms: We find the maximum value fast, or we don't get
an answer at all (but fast). While such algorithms have good running time,
their result is not guaranteed.
Here is an example of an algorithm for finding a large value that gives up its
guarantee of getting the best value in exchange for an improved running time. This
is an example of a probabilistic algorithm, since it includes steps that are affected
by random events. Choose m elements at random, and pick the best one of those
as the answer. For large n, if m log n, the answer is pretty good. The cost is
m 1 compares (since we must find the maximum of m values). But we don't
know for sure what we will get. However, we can estimate that the rank will be
about
mn
m+1
. For example, if n = 1; 000; 000 and m = log n = 20, then we expect
that the largest of the 20 randomly selected values be among the top 5% of the n
values.
Next, consider a slightly different problem where the goal is to pick a number
in the upper half of n values. We would pick the maximum from among the first
n+1
2
values for a cost of n=2 comparisons. Can we do better than this? Not if we
want to guarantee getting the correct answer. But if we are willing to accept near
certainty instead of absolute certainty, we can gain a lot in terms of speed.
As an alternative, consider this probabilistic algorithm. Pick 2 numbers and
choose the greater. This will be in the upper half with probability 3/4 (since it is
not in the upper half only when both numbers we choose happen to be in the lower
half). Is a probability of 3/4 not good enough? Then we simply pick more numbers!
For k numbers, the greatest is in upper half with probability 1
1
2
k
, regardless of
the number n that we pick from, so long as n is much larger than k (otherwise
the chances might become even better). If we pick ten numbers, then the chance
of failure is only one in 2
10
= 1024. What if we really want to be sure, because
lives depend on drawing a number from the upper half? If we pick 30 numbers,
we can fail only one time in a billion. If we pick enough numbers, then the chance
of picking a small number is less than the chance of the power failing during the
computation. Picking 100 numbers means that we can fail only one time in 10
100
which is less chance than any disaster that you can imagine disrupting the process.
16.2.2
Skip Lists
This section presents a probabilistic search structure called the Skip List. Like
BSTs, Skip Lists are designed to overcome a basic limitation of array-based and
linked lists: Either search or update operations require linear time. The Skip List
is an example of a probabilistic data structure, because it makes some of its
decisions at random.
Skip Lists provide an alternative to the BST and related tree structures. The pri-
mary problem with the BST is that it may easily become unbalanced. The 2-3 tree
of Chapter 10 is guaranteed to remain balanced regardless of the order in which data
