Java Reference
In-Depth Information
examples of algorithm
running times
5.2
In this section we examine three problems. We also sketch possible solutions and
determine what kind of running times the algorithms will exhibit, without provid-
ing detailed programs. The goal in this section is to provide you with some intu-
ition about algorithm analysis. In Section 5.3 we provide more details on the
process, and in Section 5.4 we formally approach an algorithm analysis problem.
We look at the following problems in this section:
minimum element in an array
Given an array of N items, find the smallest item.
closest points in the plane
Given N points in a plane (that is, an x-y coordinate system), find the pair of points
that are closest together.
colinear points in the plane
Given N points in a plane (that is, an x-ycoordinate system), determine if any three
form a straight line.
The minimum element problem is fundamental in computer science. It
can be solved as follows:
1.
Maintain a variable min that stores the minimum element.
2.
Initialize min to the first element.
3.
Make a sequential scan through the array and update min as appropriate.
The running time of this algorithm will be , or linear, because we will
repeat a fixed amount of work for each element in the array. A linear algo-
rithm is as good as we can hope for. This is because we have to examine every
element in the array, a process that requires linear time.
The closest points problem is a fundamental problem in graphics that can
be solved as follows:
O ( N )
1.
Calculate the distance between each pair of points.
2.
Retain the minimum distance.
This calculation is expensive, however, because there are
NN 1
(
-
)
2
pairs
of points. 1
Thus there are roughly
N 2
pairs of points. Examining all these
1. Each of N points can be paired with
N
-
1
points for a total of
NN 1
(
-
)
pairs. However,
this pairing double-counts pairs A , B and B , A , so we must divide by 2.
 
 
 
Search WWH ::




Custom Search