Java Reference
In-Depth Information
algorithms run in less than 10 μs. Consequently, when input sizes are very small,
a good rule of thumb is to use the simplest algorithm.
Figure 5.2 clearly demonstrates the differences between the various
curves for large input sizes. A linear algorithm solves a problem of size
10,000 in a small fraction of a second. The algorithm uses
roughly 10 times as much time. Note that the actual time differences depend
on the constants involved and thus might be more or less. Depending on these
constants, an algorithm might be faster than a linear algorithm
for fairly large input sizes. For equally complex algorithms, however, linear
algorithms tend to win out over
O
(
N
log
N
)
O
(
N
log
N
)
O
(
N
log
N
)
algorithms.
This relationship is not true, however, for the quadratic and cubic algo-
rithms. Quadratic algorithms are almost always impractical when the input
size is more than a few thousand, and cubic algorithms are impractical for
input sizes as small as a few hundred. For instance, it is impractical to use a
naive sorting algorithm for 1,000,000 items, because most simple sorting
algorithms (such as bubble sort and selection sort) are quadratic algorithms.
The sorting algorithms discussed in Chapter 8 run in
subquadratic
time—that
is, better than
O
(
N
2
)—thus making sorting large arrays practical.
Quadratic algo-
rithms are impracti-
cal for input sizes
exceeding a few
thousand.
The most striking feature of these curves is that the quadratic and cubic
algorithms are not competitive with the others for reasonably large inputs. We
can code the quadratic algorithm in highly efficient machine language and do a
poor job coding the linear algorithm, and the quadratic algorithm will still lose
badly. Even the most clever programming tricks cannot make an inefficient
algorithm fast. Thus, before we waste effort attempting to optimize code, we
need to optimize the algorithm. Figure 5.3 arranges functions that commonly
describe algorithm running times in order of increasing growth rate.
Cubic algorithms
are impractical for
input sizes as small
as a few hundred.
figure 5.3
Functions in order of
increasing growth rate
Function
Name
c
Constant
log
N
Logarithmic
log
2
N
Log-squared
N
Linear
N
log
N
N
log
N
N
2
Quadratic
N
3
Cubic
2
N
Exponential
Search WWH ::
Custom Search