Explore
For Enterprise
Join for Free
Log In

Гуманитарные науки и искусства
Бизнес
Компьютерные науки
Наука о данных
Информационные технологии
здоровье
Математика и логика
Личное развитие
Естественные и технические науки
Социальные науки
Изучение языков
Степени и сертификаты

Полный обзор Coursera

Обзор
Поиск
Для организаций
Войти
Присоединиться бесплатно

Standard Scale

Loading...

Анализ алгоритмов

Принстонский университет

4.7 (оценок: 50) | Зарегистрировано учащихся: 21K

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.

Просмотреть программу курса

Рецензии

4.7 (оценок: 50)

5 stars
43 ratings
4 stars
3 ratings
3 stars
3 ratings
1 star
1 ratings

AK

Apr 29, 2018

This course is more about mathematic than algorithms, it teaches how to solve tricky combinatorial problems

HL

Mar 10, 2018

This is great course if you already done some algorithms courses and want to go deeper.

Из урока

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.

Standard Scale18:52

Manipulating Expansions 19:23

Asymptotics of Finite Sums 16:42

Bivariate Asymptotics 28:03

Преподаватели

Robert Sedgewick
William O. Baker *39 Professor of 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., 2019 Все права защищены.

Загрузить из App Store

Загрузить в Google Play

Coursera
О проекте
Руководство
Карьера
Каталог
Сертификаты
Сертификаты MasterTrack™
Степени
Для организаций
Для правительственных организаций

Сообщество
Learners
Partners
Developers
Beta Testers
Translators

На связи
Блог
Facebook
LinkedIn
Twitter
Instagram
YouTube
Технический блог

Еще
Условия
Конфиденциальность
Помощь
Доступность
Пресса
Контакты
Справочник
Филиалы