Java Reference
In-Depth Information
In this chapter, we show the following:
How to estimate the time required for an algorithm
n
How to use techniques that drastically reduce the running time of an
algorithm
n
How to use a mathematical framework that more rigorously describes
the running time of an algorithm
n
How to write a simple
binary search
routine
n
what is algorithm analysis?
5.1
The amount of time that any algorithm takes to run almost always depends on
the amount of input that it must process. We expect, for instance, that sorting
10,000 elements requires more time than sorting 10 elements. The running
time of an algorithm is thus a function of the input size. The exact value of the
function depends on many factors, such as the speed of the host machine, the
quality of the compiler, and in some cases, the quality of the program. For a
given program on a given computer, we can plot the running time function on a
graph. Figure 5.1 illustrates such a plot for four programs. The curves repre-
sent four common functions encountered in algorithm analysis: linear,
, quadratic, and cubic. The input size
N
ranges from 1 to 100
More data means
that the program
takes more time.
O
(
N
log
N
)
figure 5.1
Running times for
small inputs
10
Linear
O(
N
log
N
)
Quadratic
Cubic
8
6
4
2
0
10
20
30
40
50
60
70
80
90
100
Input Size (
N
)
Search WWH ::
Custom Search