ChapTer 3
■
CounTIng 101
45
Instead of adding two sums, you can sum their added contents. This just means that if you’re going to sum
up a bunch of stuff, it doesn’t matter how you do it; that is,
sum(f(i) for i in S) + sum(g(i) for i in S)
is exactly the same as sum(f(i) + g(i) for i in S).
1
This is just an instance of
associativity. If you want to subtract
two sums, you can use the same trick. If you want, you can pretend you’re moving the constant factor –1 into the
second sum.
A Tale
of Two Tournaments
There are plenty of sums that you might find useful in your work, and a good mathematics reference will probably give
you the solution to most of them. There are, however, two sums, or combinatorial problems, that cover the majority of
the cases you’ll meet in this book—or, indeed, most basic algorithm work.
I’ve been explaining these two ideas repeatedly over the years, using many different examples and metaphors,
but I think one rather memorable (and I hope understandable) way of presenting them is as two forms of
tournaments.
Note
■
There is, actually, a
technical meaning of the word tournament in graph theory (a complete graph, where each
edge is assigned a direction). That’s not what I’m talking about here, although the concepts are related.
There are many types of tournaments, but let’s consider two quite common ones, with rather catchy names.
These are the
round-robin tournament and the
knockout tournament.
In a round-robin tournament (or, specifically, a
single round-robin tournament), each contestant meets each of
the others in turn.
The question then becomes, how many matches or fixtures do we need, if we have, for example,
n knights jousting? (Substitute your favorite competitive activity here, if you want.) In a knockout tournament, the
competitors are arranged in pairs, and only the winner from each pair goes on to the next round. Here there are more
questions to ask: For
n knights, how many rounds do we need, and how many matches will there be, in total?
Shaking Hands
The round-robin tournament problem is exactly equivalent to another well-known puzzler: If you have
n algorists
meeting at a conference
and they all shake hands, how many handshakes do you get? Or, equivalently, how many
edges are there in a complete graph with
n nodes (see Figure
3-1
)? It’s the same count you get in any kind of “all
against all” situations. For example, if you have
n locations on a map and want to find the two that are closest to each
other, the simple (brute-force) approach would be to compare all points with all others. To find the running time to
this algorithm, you need to solve the round-robin problem. (A more
efficient solution to this closest pair problem is
presented in Chapter 6.)
1
As long as the functions don’t have any side effects, that is, but behave like mathematical functions.
ChapTer 3
■
CounTIng 101
46
You may very well have surmised that there will be a quadratic number of matches. “All against all” sounds
an awful lot like “all times all,” or
n
2
. Although it is true that the result is quadratic, the exact form of
n
2
isn’t entirely
correct. Think about it—for one thing, only a knight with a death wish would ever joust against himself (or herself).
And if Sir Galahad has crossed swords with Sir Lancelot, there is no need for Sir Lancelot to return the favor, because
they
surely have both fought each other, so a single match will do. A simple “
n times
n” solution ignores both of these
factors, assuming that each knight gets a separate match against
each of the knights (including themselves). The fix is
simple: Let each knight get a match against all the
others, yielding
n(
n–1), and then, because we now have counted
each match twice (once for each participating knight), we divide by two,
getting the final answer,
n(
n–1)/2, which is
indeed Q(
n
2
).
Now we’ve counted these matches (or handshakes or map point comparisons) in one relatively straightforward
way—and the answer may have seemed obvious. Well, what lies ahead may not exactly be rocket science either, but rest
assured, there is a point to all of this . . . for now we count them all in a
different way, which must yield the same result.
This other way of counting is this: The first knight jousts with
n–1 others. Among the remaining, the second
knight jousts with
n–2. This continues down to the next to last, who fights the last match, against the last knight (who
then fights zero matches against the zero remaining knights). This gives us the sum
n–1 +
n–2 + ... + 1 + 0, or sum(i for
i in range(n)). We’ve
counted each match only once, so the sum must yield the same count as before:
i
n n
i
n 1
= 0
2
-
å
=
-
(
)
1
I could certainly just have given you that equation up front. I hope the extra packaging makes it slightly more
meaningful to you. Feel free to come up with other ways of explaining this equation (or the others throughout this
book), of course. For example, the insight often attributed to Gauss, in the story that opened this chapter, is that the
sum of 1 through 100 can be calculated “from the outside,” pairing 1 with 100, 2 with 99, and so forth, yielding 50 pairs
that all sum to 101. If you generalize this to the case of summing from 0 to
n–1, you get the same formula as before.
And can you see how all this
relates to the lower-left half, below the diagonal, of an adjacency matrix?
Tip
■
an
arithmetic series is a sum where the difference between any two consecutive numbers is a constant.
assuming this constant is positive, the sum will always be quadratic. In fact, the sum of
i
k
, where
i = 1. . .
n, for some
positive constant
k, will always be
Q(
n
k+1
). The handshake sum is just a special case.
Do'stlaringiz bilan baham: 
