This course teaches a calculus that enables precise quantitative predictions of large combinatorial structures. In addition, this course covers generating functions and real asymptotics and then introduces the symbolic method in the context of applications in the analysis of algorithms and basic structures such as permutations, trees, strings, words, and mappings. All the features of this course are available for free. It does not offer a certificate upon completion.
Standard Scale
Loading...
Из курса от партнера Princeton University
Analysis of Algorithms
37 оценок
Из урока
Asymptotics
Exact answers are often cumbersome, so we next consider a scientific approach to developing approximate answers that, again, mathematicians and scientists have used for centuries.
Познакомьтесь с преподавателями
Robert SedgewickWilliam O. Baker *39 Professor of Computer Science
Computer Science
Today, we're going to talk about asymptotics.
This is mathematics that was developed well before the advent of computers in
the 18th and 19th centuries.
But it's quite relevant to the analysis of algorithms and to analytic combinatorics.
We'll start off by talking about the standard asymptotic scale.
So the goal is to develop concise and accurate expressions
that give us good estimates of the quantities we're interested in studying.
As I mentioned in the first few lectures,
the big O notation is really not adequate for this.
If you say big O(log N), it doesn't give you an accurate measure of the quantity.
It's an upper bound, and it's within a constant factor, and
there's no way to get a precise estimate of what the quantity is.
If we had to take a definition like this, say H sub N, for
the harmonic numbers, that one's accurate, but it's not concise.
It's going to take time to compute the exact value that you want.
Now, that's not too bad, but still the spirit of we're talking
about is to try to get accurate and concise expressions like this one.
Natural log N + gamma + big O of 1 over N.
So that one, for large values of N, will give a numerical result
that's very close to the quantity that we're interested in studying.
And we'll see lots and lots of examples, but that's the basic goal.
We want a concise and
accurate estimates of the quantities we're interested in studying.
Now we won't go crazy with defining what concise means,
what I mean by it is I've got standard functions and I've got constants that
are maybe known and I want to be able to compute this value for large N.
It's as simple as that.
I want to write a program or use a calculator to compute the value.
And actually, that kind of definition,
it's easy to understand the motivation for Scientists in the 18th and
19th centuries, who were learning more about mathematical models of the world and
coming up with functions that describe whatever their interests in studying.
They wanted to be able to do calculations in order to be able to compare
their hypotheses with what goes on in the natural world.
And without asymptotics, it would be hard to do so
because without computers you definitely need to be able to compute your answer.
And that's always a good perspective to have
in the back of our minds when we're thinking about asymptotics.
So this is just a reminder I talked about this notation earlier on.
So the big O notation for upper bounds.
If you say g of N = big O of N.
That means the absolute value of the ratio is bounded from above as N
goes to infinity.
And we're going to use that notation for error terms,
but not for our leading terms.
Also we use the little o notation which says that g of N is little o f(N).
If their ratio tends to 0 as N approaches infinity.
So that's gN asymptotically smaller than f(N).
And again, we use that for error terms,
in fact, often we use the so-called tilde notation,
which just says that g(N) and f(N) ratio approaches 1 as N approaches infinity.
That's the weakest nontrivial little o.
So we use those notations to come up with approximations.
So, if we say that g(N) = f(N) + big O(h(N)),
it means the error will be within at most a constant factor of h(N) as N increases.
A little o means that we know the error will decrease as N increases.
And that's good, that means that for larger N, we get a better result.
And tilde again is the weakest, nontrivial little o.
As N increases we expect a better result and
that's basic approximations that we're going to be trying to develop.
So now with that background, what we're
looking at is developing a series of functions.
And if we have a series of functions gk with g k + 1 = little o(gk),
so that's an asymptotically decreasing series of functions.
Then if we write fN as a linear combination of those as they decrease,
we call that an asymptotic expansion of the function f,
and since the function's decreased,
the expansion is supposed to get more accurate as we add more and more terms.
Precisely, it represents the collection of formula, f(N) is big O of g sub 0.
It's also c0, g0, plus big O of g sub 1, and so forth.
And we can pick off of this list of formulas the one that suits our
purposes best in terms getting an accurate estimate of the quantity we're looking at.
And this will become more clear when we look at specific examples.
So, we're using big 0 notation but then in the specific technical sense, we want to
be able to be ensured that we can get more accurate asymptotic estimates if needed.
So the standard scale we use the functions gk, we use powers of N and log N.
And maybe log N and log log N in exponentials.
So those are the standard functions that we want to use and
we'll see it's very easy to express many of the functions that arise
in scientific studies in terms of the standard scale, and
it's not necessary to give a detailed definition of this.
So typically what happens is we only use a few terms.
Maybe two, three or four terms, the second,
third or fourth equation from this.
When the unused terms are extremely small that's when we stop.
Because we have the big O estimate that says we're within a constant of that
unused term and it's extremely small relatively that's when we stop.
[COUGH] So we use the tilde notation if we don't want to bother carrying around
the big O information, and a lot of times that simplifies the calculations and
there's no reason not to.
We usually check our asymptotic estimates against the actual values
to make sure that what we have is giving us the accuracy that we want.
And if we do mathematically want to specify information on the unused
terms we go ahead and do that using the big O notation or the little o notation.
But the main point is that the methods we use, in principle,
should extend to any desired precision.
If we need more terms, we can get them.
And that's a very big difference from the use of the big O notation in
the theory of algorithms where it's both expressing an upper bound and
capturing the concept of the worst case.
This is more in the spirit of science, the origins are clear in the 18th and
19th centuries, where people wanted to be able to calculate things and
then compare those with the results of scientific experiments.
That's what we want to do in the analysis of algorithms, and
that's why we embrace all of this classical mathematics.
So here's an example that we looked at in the second lecture.
We came up against a theorem that was going to give us coefficient abstraction
this was for solving linear recurrences, and eventually we found
through the use of generating functions that the quantity that we're interested in
is the coefficient of z to the N and the ratio of two polynomials.
And so, what we can do with asymptotics is take
pretty complicated theorem statement that I'll show in just a second and
reduce it down to actually a pretty general result.
The coefficient of cb vn in the two ratio of the two polynomials is
asymptotic to a constant times beta vn into the new minus
1 where beta is the smallest modulus root of
the polynomial in the denominator and mu is its multiplicity.
So this is just picking the leading term off of the more detailed theorem.
So in lecture two, I gave this detailed theorem that showed that
the coefficient of z to the n in that ratio,
there's a term corresponding to each 0 of g of z.
And then according to its multiplicity, and with asymptotics,
we cannot worry about all the smaller terms in that sum and
just pick out the largest one in a precise technical sense.
So for example, if the roots are three and
two then it may be 3 to the N and 3 to the N plus 2 to the N and
you can see as N gets even to 11 they're pretty close,
and when N gets very high they're going to get closer and closer.
So, usually the pole of smallest modulus really dominates.
So no question 3 to the N plus 2 to the N is asymptotic 3 to the N.
You can forget about the 2 to the n for large N.
And [COUGH] in fact the convergence is exponentially fast,
as N gets large even by 1, it gets closer and
closer to being accurate.
The ratio gets closer and closer to 1.
So usually that pull of smallest modulus that the place where the denominator
goes 0, closest to the origin that's the one that really matters, and
I've emphasized this because this particular scenario turns out to be
very important in a general context later on in analytic combinatorics.
Now there are situation depending on what these polynomials are where the polls
are close together or the multiple polls very close to the one with small modulus.
And in those kinds of cases,
we have to figure out how to extract the leading terms.
But still it's very important to realize that we don't need to carry around
the small ones.
So sure, if one of the routes is 2 and the other one is one-half, and the other one
is 1 over 1.99999, it's not going to be that close should be off by a factor of 2.
I'd try to throw that one away.
But it seems easy to figure that out, and
it's important to know that it's easy to throw away the small ones.
So here's how analysis would go for a recurrence,
say like one of the earlier recurrences that started out with.
A sub N = 5 aN- 1- 6a- 2 when a0 and a1 = 1.
So we only worry about the root
of g that's smallest.
So to solve the recurrence, we make it valid for all n.
Then we multiply by z and sum on n to get polynomial and
that gives us, for the generating function, a ratio of two polynomials.
And what we're interested in is the coefficient of z to the n in that
generating function and now we can just plug in chug in the theorem.
The smallest root of the denominator is one-third so
it's going to be asymptotic to 3 to the n.
And then we go ahead and calculate the constant.
And if you plug in the values for
the constant in that formula, you just get one.
And if you want to apply the same thing to, say, the recurrence for
the Fibonacci numbers, again the same steps are going to work.
In that case the constant will be one over square root of 5, and
it'll be phi to the n, the golden ratio to the n.
The extra term in that case is phi hat which is less than 1 and
totally negligible.
So, with asymptotics, we get a relatively simple general theorem
that gives us a precise and concise result for a big family of problems.
So back to the basics.
Where do we start out?
Where do we get the asymptotic expansions that we need to start out?
For a lot of the generating functions that arise,
Taylor's theorem immediately gives us an answer.
It's an expansion through power series and Taylor's theorem.
They're infinite but since they converge,
they can stop at any point to give results like this.
In principle, we can take as many terms as we want off the infinite series.
And then [COUGH] we have a asymptotic series in the standard scale, so
again, these are just immediate from Taylor's theorem where the term of x and
n over n factorials the nth derivative of the function.
So we looked at all of these when we talked about expanding generating
functions and the difference now is with asymptotics we're only interested in
taking couple of terms for the purpose of being able to accurately compute values.
So those are standard examples.
Now these are Taylor's theorem for x goes to 0 actually
we're usually interested in coefficient zbn as n increases.
So what we'll do is just substitute 1 over N in all of these formulas,
to get asymptotic expansions.
And these are in maybe more familiar terms,
if you wanted to compute e to the 1 over N, say for N equals a million,
this will tell you it's going to be pretty close to 1.
It'll 1 plus 1 over 1 million plus 1 over 2 times a million squared.
I'm not going to be worth trying
to compute that any more accurately than that.
This will give very great accuracy just with a few turns.
Same log of 1 over 1+1 over N for if it equals a millionth,
that's pretty close to 1 millionth.
The next term you won't notice until 12 decimal places out, and
the next one 18 decimal places out.
If you just want it to a few decimal places, use 1 over a million,
that's the whole idea of asymptotics.
And binomial has, this is for
k constant, will have a similar kind of character.
Now, this gets more complicated if k grows within and
that would be one of the things that we'll talk about later on.
And the one that we used really most often, is geometric.
So, anyway that's what you get when you plug in 1 over N,
in the straight geometric series.
1 over N minus what it says is that 1 over N minus 1, is really close to 1 over N.
For a million again next term out wouldn't happen for 12 decimal places.
So those are the basic building blocks of the asymptotic expansions
that we work with.
So just as exercises just using those simple formulas
then we can get relatively accurate approximations of say,
sums and differences of functions, just using those formulas.
And so it's worthwhile to take a look at these exercises and
as just as getting started.
A problem in asymptotics, we specify the function and then we specify how
accurately we want to estimate it, and so these two problems,
it's definitely worthwhile just working for a second on those.
And if you go ahead and just plug in from before on our previous slide,
log n 1 plus 1 over N is 1 over N minus 1 over 2N squared plus big O 1 over N cubed.
And log of n 1 minus 1 over N is a minus 1 over N and so
the 1 over N terms cancel, and then you've got 2, 1 over 2N squared terms,
which makes it just -1 over N squared plus big O 1 over N cubed.
So right away, you can see the log of 1+1 over N is a rather complicated function,
but we can approximate it very accurately as just minus 1 over N squared and
that's going to be quite accurate for N in the practical ranges of interest.
If it's minus, then what happens is the 1 over N squared terms cancel out
we're just left with 2 over N.
So that's just simple, simple example of asymptotic
expansions using the basic information that we get from Taylor's theorem.
And then combining those results really just using algebra.
For lots and lots of functions that come up,
we can apply techniques like this to develop accurate expansions.
That's what we'll look at next.
Ознакомьтесь с нашим каталогом
Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.
Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.
© Coursera Inc., 2018 Все права защищены.
