Java Reference
In-Depth Information
them on a suitable range of inputs, measuring how much of the resources in ques-
tion each program uses. This approach is often unsatisfactory for four reasons.
First, there is the effort involved in programming and testing two algorithms when
at best you want to keep only one. Second, when empirically comparing two al-
gorithms there is always the chance that one of the programs was “better written”
than the other, and therefor the relative qualities of the underlying algorithms are
not truly represented by their implementations. This can easily occur when the
programmer has a bias regarding the algorithms. Third, the choice of empirical
test cases might unfairly favor one algorithm. Fourth, you could find that even the
better of the two algorithms does not fall within your resource budget. In that case
you must begin the entire process again with yet another program implementing a
new algorithm. But, how would you know if any algorithm can meet the resource
budget? Perhaps the problem is simply too difficult for any implementation to be
within budget.
These problems can often be avoided by using asymptotic analysis. Asymp-
totic analysis measures the efficiency of an algorithm, or its implementation as a
program, as the input size becomes large. It is actually an estimating technique and
does not tell us anything about the relative merits of two programs where one is
always “slightly faster” than the other. However, asymptotic analysis has proved
useful to computer scientists who must determine if a particular algorithm is worth
considering for implementation.
The critical resource for a program is most often its running time. However,
you cannot pay attention to running time alone. You must also be concerned with
other factors such as the space required to run the program (both main memory and
disk space). Typically you will analyze the time required for an algorithm (or the
instantiation of an algorithm in the form of a program), and the space required for
a data structure.
Many factors affect the running time of a program. Some relate to the environ-
ment in which the program is compiled and run. Such factors include the speed of
the computer's CPU, bus, and peripheral hardware. Competition with other users
for the computer's (or the network's) resources can make a program slow to a crawl.
The programming language and the quality of code generated by a particular com-
piler can have a significant effect. The “coding efficiency” of the programmer who
converts the algorithm to a program can have a tremendous impact as well.
If you need to get a program working within time and space constraints on a
particular computer, all of these factors can be relevant. Yet, none of these factors
address the differences between two algorithms or data structures. To be fair, pro-
grams derived from two algorithms for solving the same problem should both be
compiled with the same compiler and run on the same computer under the same
conditions. As much as possible, the same amount of care should be taken in the
programming effort devoted to each program to make the implementations “equally
Search WWH ::




Custom Search