Chapter 0: What This Book Is About
0.1 Background
An algorithm is a method for solving a class of problems on a computer. The complexity of an algorithm
is the cost, measured in running time, or storage, or whatever units are relevant, of using the algorithm to
solve one of those problems.
This book is about algorithms and complexity, and so it is about methods for solving problems on
computers and the costs (usually the running time) of using those methods.
Computing takes time. Some problems take a very long time, others can be done quickly. Some problems
seem to take a long time, and then someone discovers a faster way to do them (a ‘faster algorithm’). The
study of the amount of computational effort that is needed in order to perform certain kinds of computations
is the study of computational complexity.
Naturally, we would expect that a computing problem for which millions of bits of input data are
required would probably take longer than another problem that needs only a few items of input. So the time
complexity of a calculation is measured by expressing the running time of the calculation as a function of
some measure of the amount of data that is needed to describe the problem to the computer.
For instance, think about this statement: ‘I just bought a matrix inversion program, and it can invert
an n × n matrix in just 1.2n
3
minutes.’ We see here a typical description of the complexity of a certain
algorithm. The running time of the program is being given as a function of the size of the input matrix.
A faster program for the same job might run in 0.8n
3
minutes for an n × n matrix. If someone were
to make a really important discovery (see section 2.4), then maybe we could actually lower the exponent,
instead of merely shaving the multiplicative constant. Thus, a program that would invert an n × n matrix
in only 7n
2.8
minutes would represent a striking improvement of the state of the art.
For the purposes of this book, a computation that is guaranteed to take at most cn
3
time for input of
size n will be thought of as an ‘easy’ computation. One that needs at most n
10
time is also easy. If a certain
calculation on an n × n matrix were to require 2
n
minutes, then that would be a ‘hard’ problem. Naturally
some of the computations that we are calling ‘easy’ may take a very long time to run, but still, from our
present point of view the important distinction to maintain will be the polynomial time guarantee or lack of
it.
The general rule is that if the running time is at most a polynomial function of the amount of input
data, then the calculation is an easy one, otherwise it’s hard.
Many problems in computer science are known to be easy. To convince someone that a problem is easy,
it is enough to describe a fast method for solving that problem. To convince someone that a problem is
hard is hard, because you will have to prove to them that it is impossible to find a fast way of doing the
calculation. It will not be enough to point to a particular algorithm and to lament its slowness. After all,
that algorithm may be slow, but maybe there’s a faster way.
Matrix inversion is easy. The familiar Gaussian elimination method can invert an n × n matrix in time
at most cn
3
.
To give an example of a hard computational problem we have to go far afield. One interesting one is
called the ‘tiling problem.’ Suppose* we are given infinitely many identical floor tiles, each shaped like a
regular hexagon. Then we can tile the whole plane with them, i.e., we can cover the plane with no empty
spaces left over. This can also be done if the tiles are identical rectangles, but not if they are regular
pentagons.
In Fig. 0.1 we show a tiling of the plane by identical rectangles, and in Fig. 0.2 is a tiling by regular
hexagons.
That raises a number of theoretical and computational questions. One computational question is this.
Suppose we are given a certain polygon, not necessarily regular and not necessarily convex, and suppose we
have infinitely many identical tiles in that shape. Can we or can we not succeed in tiling the whole plane?
That elegant question has been proved* to be computationally unsolvable. In other words, not only do
we not know of any fast way to solve that problem on a computer, it has been proved that there isn’t any
* See, for instance, Martin Gardner’s article in Scientific American, January 1977, pp. 110-121.
* R. Berger, The undecidability of the domino problem, Memoirs Amer. Math. Soc. 66 (1966), Amer.
我的内容管理
收起
我的收益 登录查看自己的收益
我的积分
登录查看自己的积分
我的C币
登录后查看C币余额
我的收藏 
我的下载 
下载帮助 
评论0