|
Figure 3-3. The height and width (number of leaves) of a perfectly balanced binary tree
Exactly how enormous the difference between these two is can be hard to fathom. One strategy would be to
simply accept that they’re extremely different—meaning that logarithmic-time algorithms are super-sweet, while
exponential-time algorithms are totally bogus—and then try to pick up examples of these differences wherever you
can. Let me give you a couple of examples to get started. First let’s do a game I like to call “think of a particle.” I think of
one of the particles in the visible universe, and you try to guess which one, using only yes/no questions. OK? Shoot!
This game might seem like sheer insanity, but I assure you, that has more to do with the practicalities (such
that keeping track of which particles have been ruled out) than with the number of alternatives. To simplify these
practicalities a bit, let’s do “think of a number” instead. There are many estimates for the number of particles we’re
talking about, but 10
90
(that is, a one followed by 90 zeros) would probably be quite generous. You can even play this
game yourself, with Python:
>>> from random import randrange
>>> n = 10**90
>>> p = randrange(10**90)
ChapTer 3
■
CounTIng 101
49
You now have an unknown particle (particle number p) that you can investigate with yes/no questions
(no peeking!). For example, a rather unproductive question might be as follows:
>>> p == 52561927548332435090282755894003484804019842420331
False
If you’ve ever played “twenty questions,” you’ve probably spotted the flaw here: I’m not getting enough “bang for
the buck.” The best I can do with a yes/no question is halving the number of remaining options. So, for example:
>>> p < n/2
True
Now we’re getting somewhere! In fact, if you play your cards right (sorry for mixing metaphors—or, rather, games)
and keep halving the remaining interval of candidates, you can actually find the answer in just under 300 questions.
You can calculate this for yourself:
>>> from math import log
>>> log(n, 2) # base-two logarithm
298.97352853986263
If that seems mundane, let it sink in for a minute. By asking only yes/no questions, you can pinpoint any particle
in the observable universe in about five minutes! This is a classic example of why logarithmic algorithms are so
super-sweet. (Now try saying “logarithmic algorithm” ten times, fast.)
Note
■
This is an example of bisection, or binary search, one of the most important and well-known logarithmic
algorithms. It is discussed further in the “Black Box” sidebar on the
bisect
module in Chapter 6.
Let’s now turn to the bogus flip side of logarithms and ponder the equally weird exponentials. Any example
for one is automatically an example for the other—if I asked you to start with a single particle and then double it
repeatedly, you’d quickly fill up the observable universe. (It would take about 299 doublings, as we’ve seen.) This
is just a slightly more extreme version of the old wheat and chessboard problem. If you place one grain of wheat on
the first square of a chessboard, two on the second, four on the third, and so forth, how much wheat would you get?
4
The number of grains in the last square would be 2
63
(we started at 2
0
= 1) and according to the sum illustrated in
Figure
3-2
, this means the total would be 2
64
–1 = 18,446,744,073,709,551,615, or, for wheat, about 5 · 10
14
kg. That’s a lot
of grain—hundreds of times the world’s total yearly production! Now imagine that instead of grain, we’re dealing with
time. For a problem size n, your program uses 2n milliseconds. For n = 64, the program would then run for 584,542,046
years! To finish today, that program would have had to run since long before there were any vertebrates around to
write the code. Exponential growth can be scary.
By now, I hope you’re starting to see how exponentials and logarithms are the inverses of one another. Before
leaving this section, however, I’d like to touch upon another duality that arises when we’re dealing with our hare and
tortoise: The number of doublings from 1 to n is, of course, the same as the number of halvings from n to 1. This is
painfully obvious, but I’ll get back to it when we start working with recurrences in a bit, where this idea will be quite
helpful. Take a look at Figure
3-4
. The tree represents the doubling from 1 (the root node) to n (the n leaves), but I
have also added some labels below the nodes, representing the halvings from n to 1. When working with recurrences,
4
Reportedly, this is the reward that the creator of chess asked for and was granted ... although he was told to count each grain he
received. I’m guessing he changed his mind.
ChapTer 3
■
CounTIng 101
50
these magnitudes will represent portions of the problem instance, and the related amount of work performed, for a
set of recursive calls. When we try to figure out the total amount of work, we’ll be using both the height of the tree and
the amount of work performed at each level. We can see these values as a fixed number of tokens being passed down
the tree. As the number of nodes doubles, the number of tokens per node is halved; the number of tokens per level
remains n. (This is similar to the ice cream cones in the hint for Exercise 2-10.)
= n
n
n
2
n
2
1
1
1
Do'stlaringiz bilan baham: |
