Information Technology Reference
In-Depth Information
The amount of processing required to help solve a problem of
ten depends on the amount of data involved. Computational com
plexity describes this relationship. Although some solutions scale up
nicely, the work required for others quickly becomes very large as
the size of the data set increases. For this reason, some solutions be
come impractical for data sets of even moderate size.
The size of programs and various interrelationships among parts
of programs combine to yield logical complexity. When logical com
plexity is modest, programs can be built correctly and efficiently;
however, as complexity increases, programs become large, and coor
dination plays a greater part.
Complexity can contribute to the introduction of errors into
large software packages. Such errors may be extremely difficult to
locate and correct. Further, in large, complex programs, the correc
tion of some errors can lead to the introduction of others.
The introduction of new capabilities can be of great help in
some applications but is not needed in others. Also, the expansion
of features can add computational and logical complexity to pro
grams, increasing the likelihood that programs contain errors. In
addition, processing requirements and storage demands for new fea
tures may require the purchase of new computer equipment or the
extensive upgrading of current machines. This can make new fea
tures expensive—particularly for applications in which these new
features have only marginal usefulness.
■
Terminology from This Chapter
Class NP
Class P
combinatorial
explosion
computational
complexity
exhaustive listing
exhaustive search
linear search
logical complexity
Moore's Law
ply
■
Discussion Questions
1.
This chapter's discussion of the combinatorial explosion de
scribes five different formulae that might have been used by
