Java Reference
In-Depth Information
17
Limits to Computation
This topic describes data structures that can be used in a wide variety of problems,
and many examples of efficient algorithms. In general, our search algorithms strive
to be at worst in O(log n) to find a record, and our sorting algorithms strive to be
in O(n log n). A few algorithms have higher asymptotic complexity. Both Floyd's
all-pairs shortest-paths algorithm and standard matrix multiply have running times
of (n
3
) (though for both, the amount of data being processed is (n
2
)).
We can solve many problems efficiently because we have available (and choose
to use) efficient algorithms. Given any problem for which you know some alg-
orithm, it is always possible to write an inefficient algorithm to “solve” the problem.
For example, consider a sorting algorithm that tests every possible permutation of
its input until it finds the correct permutation that provides a sorted list. The running
time for this algorithm would be unacceptably high, because it is proportional to
the number of permutations which is n! for n inputs. When solving the minimum-
cost spanning tree problem, if we were to test every possible subset of edges to
see which forms the shortest minimum spanning tree, the amount of work would
be proportional to 2
jEj
for a graph with jEj edges. Fortunately, for both of these
problems we have more clever algorithms that allow us to find answers (relatively)
quickly without explicitly testing every possible solution.
Unfortunately, there are many computing problems for which the best possible
algorithm takes a long time to run. A simple example is the Towers of Hanoi
problem, which requires 2
n
moves to “solve” a tower with n disks. It is not possible
for any computer program that solves the Towers of Hanoi problem to run in less
than (2
n
) time, because that many moves must be printed out.
Besides those problems whose solutions must take a long time to run, there are
also many problems for which we simply do not know if there are efficient algo-
rithms or not. The best algorithms that we know for such problems are very slow,
but perhaps there are better ones waiting to be discovered. Of course, while having
a problem with high running time is bad, it is even worse to have a problem that
cannot be solved at all! Such problems do exist, and are discussed in Section 17.3.
535
