Algorithm Analysis - Data Structures and Algorithm Analysis - page 79

A data structure's primary purpose is to store data in a way that allows efficient
access to those data. To provide efficient access, it may be necessary to store addi-
tional information about where the data are within the data structure. For example,
each node of a linked list must store a pointer to the next value on the list. All such
information stored in addition to the actual data values is referred to as overhead.
Ideally, overhead should be kept to a minimum while allowing maximum access.
The need to maintain a balance between these opposing goals is what makes the
study of data structures so interesting.
One important aspect of algorithm design is referred to as the space/time trade-
off principle. The space/time tradeoff principle says that one can often achieve a
reduction in time if one is willing to sacrifice space or vice versa. Many programs
can be modified to reduce storage requirements by “packing” or encoding informa-
tion. “Unpacking” or decoding the information requires additional time. Thus, the
resulting program uses less space but runs slower. Conversely, many programs can
be modified to pre-store results or reorganize information to allow faster running
time at the expense of greater storage requirements. Typically, such changes in time
and space are both by a constant factor.
A classic example of a space/time tradeoff is the lookup table. A lookup table
pre-stores the value of a function that would otherwise be computed each time it is
needed. For example, 12! is the greatest value for the factorial function that can be
stored in a 32-bit int variable. If you are writing a program that often computes
factorials, it is likely to be much more time efficient to simply pre-compute and
store the 12 values in a table. Whenever the program needs the value of n! it can
simply check the lookup table. (If n > 12, the value is too large to store as an int
variable anyway.) Compared to the time required to compute factorials, it may be
well worth the small amount of additional space needed to store the lookup table.
Lookup tables can also store approximations for an expensive function such as
sine or cosine. If you compute this function only for exact degrees or are willing
to approximate the answer with the value for the nearest degree, then a lookup
table storing the computation for exact degrees can be used instead of repeatedly
computing the sine function. Note that initially building the lookup table requires
a certain amount of time. Your application must use the lookup table often enough
to make this initialization worthwhile.
Another example of the space/time tradeoff is typical of what a programmer
might encounter when trying to optimize space. Here is a simple code fragment for
sorting an array of integers. We assume that this is a special case where there are n
integers whose values are a permutation of the integers from 0 to n 1. This is an
example of a Binsort, which is discussed in Section 7.7. Binsort assigns each value
to an array position corresponding to its value.
for(i=0;i<n;i++)
B[A[i]]=A[i];