文档介绍：Algorithms plexity
Herbert S. Wilf
University of Pennsylvania
Philadelphia, PA 19104-6395
Copyright Notice
Copyright 1994 by Herbert S. Wilf. This material may be reproduced for any educational purpose, multiple
copies may be made for classes, etc. Charges, if any, for reproduced copies must be just enough to recover
reasonable costs of reproduction. Reproduction mercial purposes is prohibited. This cover page must
be included in all distributed copies.
Edition, Summer, 1994
This edition of Algorithms plexity is the
le “pub/wilf/” at the anonymous ftp site
“”. It may be taken at no charge by all interested persons. Comments and corrections
are e, and should be sent to ******@
Orders of magnitude
Chapter 1: Mathematical Preliminaries
Orders of magnitude
In this section we’re going to discuss the rates of growth of di
erent functions and to introduce the
ve
symbols of asymptotics that are used to describe those rates of growth. In the context of algorithms, the
reason for this discussion is that we need a good language for the purpose paring the speeds with
which di
erent algorithms do the same job, or the amounts of memory that they use, or whatever other
measure of plexity of the algorithm we happen to be using.
Suppose we have a method of inverting square nonsingular matrices. How might we measure its speed?
monly we would say something like ‘if the matrix is n
n then the method will run in time .’
Then we would know that if a 100
100 matrix can be inverted, with this method, in 1 minute puter
time, then a 200
200 matrix would require 23 = 8 times as long, or about 8 minutes. The constant ‘’
wasn’t used at all in this example; only the fact that the labor grows as the third power of the matrix size
was relevant.
Hence we need a language that will allow us to say that puting time, as a function of n,grows
‘on the order of n3,’or‘atmostasfastasn3,’ or ‘at least as