Java Reference
In-Depth Information
obtain timing data, going up to
N
= 10,000,000. Can you infer the
running time of the program in this unique circumstance?
d.
Now suppose all the numbers are integers uniformly and ran-
domly distributed between -45 and 54, inclusive. Does that sig-
nificantly affect the running time?
e.
Suppose all the numbers are integers uniformly and randomly
distributed between -1 and 1, inclusive. Does that significantly
affect the running time?
Suppose you have a sorted array of positive and negative integers and
would like to determine if there exist some value
x
such that both
x
and -
x
are in the array. Consider the following three algorithms:
Algorithm #1:
For each element in the array, do a sequential search to
see if its negative is also in the array.
Algorithm #2:
For each element in the array, do a binary search to see if
its negative is also in the array.
Algorithm #3:
Maintain two indices
i
and
j
, initialized to the first and
last element in the array, respectively. If the two elements being indexed
sum to 0, then
x
has been found. Otherwise, if the sum is smaller than 0,
advance
i
; if the sum is larger than 0 retreat
j
, and repeatedly test the sum
until either
x
is found, or
i
and
j
meet.
5.43
Determine the running times of each algorithm, and implement all three
obtaining actual timing data for various values of
N
. Confirm your analy-
sis with the timing data.
As mentioned in Exercise 5.38, repeated
String
concatenation can be
expensive. Consequently, Java provides a
StringBuilder
class. A
StringBuilder
is somewhat like an
ArrayList
that stores unlimited
characters. The
StringBuilder
allows one to easily add to the end,
automatically expanding an internal character array (by doubling its
capacity) as needed. In so doing, the cost of appending can be
assumed to be proportional to the number of characters added to the
StringBuilder
(rather than the number of characters in the result). At
any point, the
StringBuilder
can be used to construct a
String
. Figure
5.16 contains two methods that return
Strings
containing
N
xs. What
is the running time of each method? Run the methods on various val-
ues of
N
to verify your answer.
5.44
Search WWH ::
Custom Search