Java Reference
In-Depth Information
set
A
. Since the
contains
method requires
O
(
m
) steps for each item in set
A
, then this
requires
O
(
m
)
×
O
(
n
) steps, or
O
(
mn
) steps. These are inefficient methods in our
implementation of sets. A different approach to represent the set—for example, one
that used hash tables instead of a linked list— could result in an
intersection
method
that runs in
O
(
n
m
) steps. Nevertheless, our linked list implementation would prob-
ably be fine for an application that uses small sets or for an application that does not
frequently invoke the
intersection
method, and we have the benefit of relatively sim-
ple code that is easy to understand.
If we really needed the efficiency, then we could maintain the same interface to the
Set<T>
class but replace our linked list implementation with something else. If we used the
hash table implementation from Section 15.5, then the
contains
method could run in
O
(
1
) steps instead of
O
(
n
) steps. It might seem like the
intersection
method will now run
in
O
(
n
) steps, but by switching to a hash table it becomes more difficult to iterate through
the set of items. Instead of traversing a single linked list to retrieve every item in the set, the
hash table version must now iterate through the hash table array and then for each index in
the array iterate through the linked list at that index. If the array is size
N
and the number of
items in the hash table is
n,
then the iteration time becomes
O
(
N
+
n
)
.
In practice, we would
expect
N
to be larger than
n
. So although we have decreased the number of steps it takes to
look up an item, we have increased the number of steps it takes to iterate over every item. If
this was troublesome, you could overcome this problem with an implementation of
Set<T>
that used both a linked list (to facilitate iteration) and a hash table (for fast lookup). How-
ever, the complexity of the code is significantly increased using such an approach. You are
asked to explore the hash table implementation in Programming Project 10.
+
Self-Test Exercises
23. Write a method named
difference
that returns the difference between two
sets. The method should return a new set that has items from the first set that
are not in the second set. For example, if
setA
contains {1, 2, 3, 4} and
setB
contains {2, 4, 5}, then
setA.difference(setB)
should return the set {1, 3}.
24. What is the run time of the
difference
method for the previous question? Give
your answer using big-
O
notation.
15.7
Trees
I think that I shall never see a data structure as useful as a tree.
ANONYMOUS
The tree data structure is an example of a more complicated data structure made with
links. Moreover, trees are a very important and widely used data structure. So, we will
