Java Reference
In-Depth Information
pairs and finding the minimum distance among them takes quadratic time. A
better algorithm runs in time and works by avoiding the compu-
tation of all distances. There is also an algorithm that is expected to take
time. These last two algorithms use subtle observations to provide
faster results and are beyond the scope of this text.
The colinear points problem is important for many graphics algorithms.
The reason is that the existence of colinear points introduces a degenerate
case that requires special handling. It can be directly solved by enumerating
all groups of three points. This solution is even more computationally expen-
sive than that for the closest points problem because the number of different
groups of three points is (using reasoning similar to that
used for the closest points problem). This result tells us that the direct
approach will yield a cubic algorithm. There is also a more clever strategy
(also beyond the scope of this text) that solves the problem in quadratic time
(and further improvement is an area of continuously active research).
In Section 5.3 we look at a problem that illustrates the differences among
linear, quadratic, and cubic algorithms. We also show how the performance of
these algorithms compares to a mathematical prediction. Finally, after dis-
cussing the basic ideas, we examine Big-Oh notation more formally.
O
(
N
log
N
)
O
(
N
)
NN
1
(
-
)
(
N
-
2
)
⁄
6
the maximum contiguous
subsequence sum problem
5.3
In this section, we consider the following problem:
maximum contiguous subsequence sum problem
Given (possibly negative) integers , find (and identify the sequence
corresponding to) the maximum value of . The maximum contiguous sub-
sequence sum is zero if all the integers are negative.
A
1
A
2
,
,
…
,
A
N
∑
j
A
k
ki
=
As an example, if the input is {-2,
11
,
-4
,
13
, -5, 2}, then the answer is 20,
which represents the contiguous subsequence encompassing items 2 through
4 (shown in boldface type). As a second example, for the input { 1, -3,
4
,
-2
,
-1
,
6
}, the answer is 7 for the subsequence encompassing the last four items.
In Java, arrays begin at zero, so a Java program would represent the input
as a sequence
Programming
details are consid-
ered after the algo-
rithm design.
A
0
to
A
N
. This is a programming detail and not part of the
-
1
algorithm design.
Before the discussion of the algorithms for this problem, we need to com-
ment on the degenerate case in which all input integers are negative. The prob-
lem statement gives a maximum contiguous subsequence sum of 0 for this case.
One might wonder why we do this, rather than just returning the largest (that is,
Always consider
emptiness.
Search WWH ::
Custom Search