24-01-2013, 12:19 PM
The Running Time of Programs
1The Running.pdf (Size: 479.15 KB / Downloads: 157)
INTRODUCTION
In Chapter 2, we saw two radically different algorithms for sorting: selection sort
and merge sort. There are, in fact, scores of algorithms for sorting. This situation
is typical: every problem that can be solved at all can be solved by more than one
algorithm.
How, then, should we choose an algorithm to solve a given problem? As a
general rule, we should always pick an algorithm that is easy to understand, im-
plement, and document. When performance is important, as it often is, we also
need to choose an algorithm that runs quickly and uses the available computing
resources efficiently. We are thus led to consider the often subtle matter of how we
can measure the running time of a program or an algorithm, and what steps we can
take to make a program run faster.
Choosing an Algorithm
If you need to write a program that will be used once on small amounts of data
and then discarded, then you should select the easiest-to-implement algorithm you
know, get the program written and debugged, and move on to something else. How-
ever, when you need to write a program that is to be used and maintained by many
people over a long period of time, other issues arise. One is the understandability, or
simplicity, of the underlying algorithm. Simple algorithms arSimplicity e desirable for several
reasons. Perhaps most important, a simple algorithm is easier to implement cor-
rectly than a complex one. The resulting program is also less likely to have subtle
bugs that get exposed when the program encounters an unexpected input after it
has been in use for a substantial period of time.
Benchmarking
When comparing two or more programs designed to do the same set of tasks, it is
customary to develop a small collection of typical inputs that can serve as bench-
marks. That is, we agree to accept the benchmark inputs as representative of the
job mix; a program that performs well on the benchmark inputs is assumed to
perform well on all inputs.
For example, a benchmark to evaluate sorting programs might contain one
small set of numbers, such as the first 20 digits of ; one medium set, such as the
set of zip codes in Texas; and one large set, such as the set of phone numbers in the
Brooklyn telephone directory. We might also want to check that a program works
efficiently (and correctly) when given an empty set of elements to sort, a singleton
set, and a list that is already in sorted order. Interestingly, some sorting algorithms
perform poorly when given a list of elements that is already sorted.
Analysis of a Program
To analyze a program, we begin by grouping inputs according to size. What we
choose to call the size of an input can vary from programto program, as we discussed
in Section 2.9 in connection with proving properties of recursive programs. For a
sorting program, a good measure of the size is the number of elements to be sorted.
For a program that solves n linear equations in n unknowns, it is normal to take n to
be the size of the problem. Other programs might use the value of some particular
input, or the length of a list that is an input to the program, or the size of an array
that is an input, or some combination of quantities such as these.