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.
Manipulating Expansions
Loading...
From the course by Princeton University
Analysis of Algorithms
32 оценки
From the lesson
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.
Meet the Instructors
Robert SedgewickWilliam O. Baker *39 Professor of Computer Science
Computer Science
Okay, next we'll take a look at the basic techniques that we use for
manipulating asymptotic expansions to derive accurate and
concise estimates of the quantities that we're trying to study.
So our goal is to develop an expansion on a standard scale for
any expression that might arise in the analysis.
And these are just examples of the kinds of expressions that might show up.
Some of them are artificial, but some of them actually turn up in our analysis.
So we saw 2 inches, and we studied the catalan numbers.
And the problem with some of these, like 2 inches N,
it might be hard to compute that.
So imagine a 17th century mathematician
trying to compute that for n=1,000, that's a lot of multiplications.
Or, imagine a computer programmer today given the job that computing has,
it's simple to define, but if you use the basic definition for n = a million,
a million factorials, pretty big number, so you have to deal with it in some way.
On the other hand, using asymptotic expansions,
we're going to get all of these in a kind of coherent form
where we can be confident that we can work with them.
So there's a lot different techniques that we use and each one of them is relatively
simple but it's still worthwhile calling out examples of each.
So, and we'll look at each one of these simplification,
substitution, factoring, multiplication, division, and composition.
They seem really simple to call out but
on the other hand, when faced with dealing with one of these functions,
you really want to think in terms of there is an easy way to do this,
one of these basic ways, just have to figure out which one it is.
And there'll also be a x log trick is an important one or
technique and I'll show that in a minute.
So again, the whole idea is that a lot of times we have
not just these quantities, but maybe they combine in some way.
So like what's the value of 1 over 4 to the N 2N, choose N.
That's an expression that arises that's of importance in the analysis of algorithms.
And if you ask the program to try to compute that for N equals 10 to the 6th,
it's going to be a challenge.
And we'll actually see that it's relatively simple to express this in terms
of standard functions via asymptotics.
And all of these functions and all of the functions that arise we can do that.
So, let's take a look at the various techniques.
So the first thing is, that an asymptotic series is only as good as its O-term.
So that means there's no point in carrying around smaller terms,
if you have something that's encompassed by the O, just drop it.
It's only going to make the calculation more complicated and
it's not helpful in any way.
So we don't write log N + gamma + O of 1 where gamma is a constant,
because the O of 1 says the air is bounded by some constant and
so to have that constant might as well be gamma or whatever.
It's better to say that write down this expression as log N + O of 1,
it's more compact.
So, the other idea we already talked about was substitution,
where you can just change variables in a known expansion.
So, the Taylor Series for log of 1 + X is X-X
squared over 2 + X squared of 3 and so forth.
And if we just plug in a value for X, we plug in 1 over n,
then we get the expansion, so that's one technique that we already used.
Factoring, a very common thing to do is to estimate what the leading term is,
then factor that out and expand the rest.
So, look at this function, 1/N squared plus N and we think to ourselves,
what's this going to be close to when N is large, like N is a million.
It's going to be close to 1/N squared, so
we might as well factor out the 1 over N squared.
And then in this case, what we're left with, is 1/1 + 1/N and
that's a geometric series and we have asymptotic expansion for geometric series.
So expand it since it's 1+1/N,
it's 1-1/N or 1/N squared.
So and we could take that to more terms if we wanted to but
that's an asymptotic expansion of that.
If we use that expansion is says that for
N=1 million that value is going to be very close to 1/N squared.
The relative error that we would make
would be 1 over 1,000,000 in that case which is small enough for our purposes.
You'd distribute that so
it's 1 over N squared plus 1 over N cubed plus big O 1 over N to the 4th.
That's a asymptotic series in the standard scale for
1 over N squared + N, very easy to obtain.
Multiplication, so multiplication is just algebra but
also employing simplification when we have smaller terms and we throw them out.
So let's look at the square of the harmonic numbers, so
we did estimate on the harmonic numbers.
We talked about the asymptotic series for the harmonic numbers
is given by approximation with the sum and I'll talk briefly about that.
And we'll talk more about that kind of asymptotics later.
So the harmonic number, is approximated by log N + gamma plus big O,
over 1 over N, where gamma is always constant 0.577.
So, to compute the square, of the harmonic numbers, we have to square those.
So, that's 2 terms with 2 factors with 3 terms each.
So we're going to wind up with six factors when we add all that together.
So ln N times each one of those,
ln N squared + gamma ln N + big O (ln N over N).
Inside big O, we usually don't specify the base of the logarithm since it
only differs by a constant.
So it doesn't matter that it's natural log so
we just write log, this means it's not specified at some constant.
Then the next row is gamma times each one, gamma log N + gamma squared + O of 1/N.
And the next term is O(1 over N) times all of them, O(1 over N),
log N over N gamma times O(1 over N) is O(1 over N), and
so O(1 over N) times O(1 over N), so O(1 over N) squared.
So that gives us nine terms but,
we can throw a lot of them out, because well first of all,
all the big O terms you just pick the largest one.
So, big O of 1 over N squared is much smaller than log N over N so
it can be [INAUDIBLE] in that.
Same with O of 1 over N, so all the big O terms and
there's five of them, get subsumed in that O of log n over n.
There's the gamma squared, and the gamma log N appears twice, so
that's an asymptotic series in the standard scale for
the square of the harmonic numbers.
Now just taking a look at this series,
it's important to note that there's a difference between
the first couple of terms and the big O that we lost.
So log N squared, so N is a million,
log N it’s going to be some small integer so
log N squared and 2 log N is not there not that far apart.
So it seems like were going to need those and the gamma squared is a constant,
but log N is a small integer is only a slight improvement in precision to carry
on those terms and so probably want those terms.
But when we get a divided by N,
that's when we have a huge improvement in precision.
Now, we can't always tell ahead of time, how far you have to go before you get this
big improvement, but in real problems it usually happens after three or
four terms and that's what happened here.
If you look the tables of these quantities, for N equals 100, I'm sorry,
1,000, 10,000 and 100,000, you can see,
so HN squared is the quantity that we're trying to estimate.
And then if you just try to estimate it with log N squared you can see it will
be off by fair amount 10% for even a 100,000.
If you add the 2 gamma log N you come much closer and add the gamma squared,
actually we're accurate to three decimal places because the next term,
the one that we're missing is going to differ.
It's going to be bounded by a constant times log N over N and for
100,000 that's going to be out in the fourth or
fifth decimal place, assuming the constant's small,
which normally we assume in these asymptotic series is they are.
But we can check as in this case that that's an accurate approximation.
So usually we'll try to carry it out long enough
until we get this big improvement in precision.
All right, division, that's like multiplication,
so let's look at this example, HN over natural log of N + 1.
So what we'll do for that, is we'll expand the numerator and the denominator,
both and then we'll use the geometric series to expand the denominator and
that will give us a multiplication problem, so let's look how that works.
So [COUGH] H of n is log N + gamma + O of 1 over N,
that's the approximation that we've been using for H of N.
Natural log of N + 1, factor out a log N and
it becomes natural log of N + natural log of 1+1 over N,
natural log of 1 plus 1 over N plus big O 1 over N just from Taylor.
So, now we have the ratio of 2 asymptotic series,
and what we'll do is factor out the log N as before.
So, that's divide by numerator and denominator by log N and
so the numerator becomes 1 + N over log N, + 1 over N,
over 1 over N log N, so we're simplifying that,
the denominator becomes 1 + plus O over N.
We could make it 1 over N log N, to make it a little bit bigger and
again that's just to simplify the formulas if we did not get
a sufficiently accurate estimate we could go back and try to correct that.
And now 1 + O of 1 over N, if you expand as a geometric series,
it just becomes 1 + 1 over 1 + O of 1 over N,
is 1 + O of 1 over N, just as a geometric series.
And again, if there are more terms, you could carry more terms out there.
So now we have a multiplication problem and if we multiply that out,
that's proof that the asymptotic expansion of HN over log
of N + 1 to with 1 over N is 1 + gamma over log N + O of 1.
And again, there's a big improvement in precision when we get
to the 1 over N term.
So this is going to be a very accurate estimate of
that more complicated quantity as N increases.
Composition, so this is similar, so
we're just going to substitute an expansion and figure out what to do.
So if you had to compute e to the H of n,
you plug in the expansion for the H of n and see what you get.
What you get is e to the log N + gamma + big O of 1 over N e to the log N,
that's N, e to the gamma is e to the gamma, that's a constant and
then what's left is e to the big O of 1 over N.
And then that one you expand with Taylor, although it's a little
more work to actually prove that but you can from now on use that Lemma.
e to the O of 1 over N is 1 + O of 1 over N, and
you can expand it a couple of terms if you need to, and
that gives the simplification that e to the HN is Ne to the gamma
to then 1 over N or Ne to the gamma plus O of 1.
And again Ne to the gamma that grows with N over 1 as a constant so
there is a big change in precision, so
that's going to be a very accurate approximation for large N.
Each time that we do an asymptotic expansion, we go down to where,
we usually try to go, where we can get a big improvement in precision like this.
And gives us a simple expression in terms of familiar functions for
this thing where otherwise its growth might not be so obvious to see.
And again, you can see, for N = a million, this is accurate to within 1,
absolute 1, which is a fine small irrelative error.
Okay, x blog log,
so this is a way to bring us into position where we can apply
the composition in more complicated scenarios.
And all we'll do is write f(x) as
e to the log of f(x), then we can expand the log of f(x), and
we can expand e to that series, as we did before.
And here's a fine example, 1- 1/N to the N and when you see a thing like that,
you have to think, how would you compute that for that log value of N.
Ask a programmer to compute that for N = a million,
maybe not necessarily so easy to do.
It's going to at least take time proportional to N, and
there might be precision problems or
as with factorial there might be problems in needing to carry too many digits.
Well, actually, the way people compute things like that, is use the X log trick.
So that is, we write that as e to the log of 1- 1 over N to the N-th.
So, in the log of 1- 1 over N to the N-th,
we can bring the N down, it's N times the log of 1- 1 over N.
And so now, if we expand log of 1- 1 over N, again,
using the Taylor Series, we have -1 over N, plus O of 1 over N squared.
And then do the algebra, that's e to the -1 + O(1/N) and
again, e to the O(1/N) = 1 + O(1/N), so that's 1 over e.
It says that that function,
1- 1 over N to the N is going to be very close to 1 over e.
And again, that's the big improvement in precision we always look for and again,
we can check that for N = a million, that's accurate to six decimal places.
Because the bigger O says that the error is going to be out there around the six
decimal place.
So again, when we're trying to understand what the value of the quantity is,
If we know that it's 1 over e, which is this constant,
0.367879, that's very precise and concise information, as opposed
to that exact expression which maybe is hard to know what it is.
And when we start combining these kinds of formulas, which we do all the time,
we're going to want to work with the precise and concise expressions.
So that's the exp log technique and we actually use that one quite a bit.
So thinking about these various techniques, here's just a couple
more examples that you might want to try doing,
to make sure that you understand the kinds of techniques that we're using.
So log of N over N- 2 to O 1 over N squared and Hn squared and what's that
constant, times the 1 over N term because we only got it to log n over N.
And that is just to illustrate that if
desired we can go to more asymptotic accuracy.
Maybe we need to do that because we have got a function where we are multiplying
that thing by N squared and so we need more accuracy, just for example.
So, for log N- 2, what we do is factor out the N,
so that's a leading term, and then we have log 1- 2/N and then just expand the rest.
And so it's -2 over N plus big O of 1 over N squared, so
that's the solution to that one and this one is just
carrying out the asymptotic approximations to one more term which is
1 over N squared term and then that gives the coefficient of log N over N is 1.
And again, these types of things,
as with any kind of mathematics, they require a little bit of practice.
But the techniques are so simple, it's not difficult
to learn how to do these kinds of expansions.
So that's a quick introduction to manipulating asymptotic expansions.
Ознакомьтесь с нашим каталогом
Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.
Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.
© Coursera Inc., 2018 Все права защищены.
