Explore
For Enterprise
Join for Free
Log In

Artes e Humanas
Negócios
Ciência da Computação
Ciência de Dados
Tecnologia da informação
da saúdesaúde
Matemática e Lógica
Desenvolvimento Pessoal
Ciência e Engenharia Física
Ciências Sociais
Línguas
Notas
Certificados

Explore todo o Coursera

Navegar
Pesquisar
For Enterprise
Entrar
Inscreva-se gratuitamente

Formal Statement

Loading...

Divide and Conquer, Sorting and Searching, and Randomized Algorithms

Universidade de Stanford

4.8 (2,883 classificações) | 94K alunos inscritos

Curso 1 de 4 no Algoritmos Programa de cursos integrados

The primary topics in this part of the specialization are: asymptotic ("Big-oh") notation, sorting and searching, divide and conquer (master method, integer and matrix multiplication, closest pair), and randomized algorithms (QuickSort, contraction algorithm for min cuts).

Visualizar o programa do curso

Habilidades que você aprenderá

Algorithms, Randomized Algorithm, Sorting Algorithm, Divide And Conquer Algorithms

Avaliações

4.8 (2,883 classificações)

5 stars
2,446 ratings
4 stars
371 ratings
3 stars
43 ratings
2 stars
10 ratings
1 star
13 ratings

CV

Jun 11, 2017

A really exciting and challenging course. Loved the way the instructor explained everything with so much detail and precision. Definitely looking forward to the next course in the specialization.

NE

Nov 07, 2016

Personally, I would recommend this course to anyone who really wants to learn how things work in that sort of algorithms. I found the assignments a little difficult, but also extremely helpful.

Na lição

Week 2

Divide-and-conquer basics; the master method for analyzing divide and conquer algorithms.

Formal Statement10:06

Interpretation of the 3 Cases10:46

Ministrado por

Tim Roughgarden
Professor

Transcrição

So having motivated and hyped up the generality of the master method and

its use for

analyzing recursive algorithms, let's move on to its precise mathematical statement.

Now, the master method is, in some sense, exactly what you want.

It's what I'm going to call a black box for solving recurrences.

Basically, it takes an input a recurrence in a particular format and

it spits out as output a solution to that recurrence,

an upper bound on the running time of your recursive algorithm.

That is, you just plug in a few parameters of your recursive algorithm, and

boom, out pops its running time.

Now, the master method does require a few assumptions,

and let me be explicit about one of them right now.

Namely, the master method, at least the one I'm going to give you,

is only going to be relevant for

problems in which all of the subproblems have exactly the same size.

So for example, in merge sort, there are two recursive calls, and

each is on exactly one half of the array.

So merge sort satisfies this assumption, both subproblems have equal size.

Similarly, in both of our integer multiplication algorithms,

all subproblems were on integers with n over 2 digits,

with half as many digits, so those will all also obey this assumption.

If for some reason you had a recursive algorithm that recursed on

a third of the array and then on the other two-thirds of the array,

the master method that I'm going to give you will not apply to it.

There are generalizations of the master method that I'm going to show you

which can accommodate unbalanced subproblem sizes, but

those are outside the scope of this course.

This will be sufficient for almost all of the examples we're going to see.

One notable exception, for those of you that watched the optional video on

a deterministic algorithm for linear time selection, that will be

one algorithm which has two recursive calls on different subproblem sizes.

So to analyze that recurrence,

we'll have to use a different method, not the master method.

Next I'm going to describe the format of the recurrences to which the master

method applies.

As I said, there are more general versions of the master method which apply to even

more recurrences.

But the one I'm going to give you is going to be reasonably simple, and

it will cover pretty much all the cases you're likely to ever encounter.

So recurrences have two ingredients.

There's the relatively unimportant, but still necessary, base case step.

And we're going to make the obvious assumption, which is just satisfied by

every example we're ever going to see in this course, which is that at some point,

once the input size drops to a sufficiently small amount,

then the recursion stops, and the subproblem is solved in constant time.

Since this assumption is pretty much always satisfied in every problem

we're going to see, I'm not going to discuss it much further.

Let's move on to the general case where there are recursive calls.

So we assume the recurrence is given in the following format.

The running time on an input of length n is bounded above by some number

of recursive calls, let's call it a different recursive calls.

And then each of these subproblems has exactly the same size, and

it's 1 over b fraction of the original input size.

So there's a recursive calls, each on an input of size n over b.

Now, as usual, there's the case where n over b is a fraction and not an integer.

And as usual, I'm going to be sloppy and ignore it.

And as usual, that sloppiness has no implications for the final conclusion.

Everything that we're going to discuss is true for

the same reasons in the general case where n over b is not an integer.

Now, outside the recursive calls, we do some extra work.

And let's say that it's O(n to the d) for some parameter d.

So in addition to the input size n,

there are three letters here which we need to be very clear on what their meaning is.

So first of all, there's a, which is the number of subproblems,

the number of recursive calls.

So a could be as small as 1 or it might be some larger integer.

Then there's b.

b is the factor by which the input size shrinks before a recursive call is

applied.

b is some constant strictly greater than 1.

So for example,

if you recurse on half of the original problem, then b would be equal to 2.

It better be strictly bigger than 1 so that eventually you stop recursion, so

that eventually then you terminate.

Finally, there's d, which is simply the exponent in the running time of the,

quote, unquote combine step, that is,

the amount of work which is done outside of the recursive calls.

And d could be as small as 0,

which would indicate constant amount of work outside of the recursive calls.

One point to emphasize is that a, b, and d are all constants.

They're all numbers that are independent of n.

So a, b, and d are going to be numbers like 1, 2, 3, or 4.

They do not depend on the input size n.

And in fact, let me just redraw the d so that you don't confuse it with the a.

So again, a is the number of recursive calls and d is the exponent and

the running time governing the work done outside of the recursive calls.

Now, one comment about that final term, that big O(n to the d).

On the one hand, I'm being sort of sloppy.

I'm not keeping track of the constant that's hidden inside the big-O notation.

I'll be explicit with that constant when we actually prove the master method.

But it's really not going to matter.

It's just going to carry through the analysis without affecting anything.

So you can go ahead and ignore that constant inside the big-O.

Obviously, the constant in the exponent, namely d, is very important.

So depending on what d is, depends on whether that amount of time is constant,

linear, quadratic, or so on.

So certainly we care about the constant d.

So that's the input to the master method.

It is a recurrence of this form.

So you can think of it as a recursive algorithm which makes a recursive calls,

each on subproblems of equal size, each of size n over b,

plus it does n to the d work outside of the recursive calls.

So having set up the notation, I can now precisely state the master method for you.

So given such a recurrence, we're going to get an upper bound on the running time.

So the running time on inputs of size n is going to be upper bounded by

one of three things.

So somewhat famously, the master method has three cases.

So let me tell you about each of them.

The trigger,

which determines which case you're in, is a comparison between two numbers.

First of all, a, recall, a is the number of recursive calls made.

And b raised to the d power.

Recall, b is the factor by which the input size shrinks before you recurse.

d is the exponent in the amount of work done outside of the recursive call.

So we're going to have one case for when they're equal,

we're going to have one case for when a is strictly smaller than b to the d.

And the third case is when a is strictly bigger than b of the d.

And in the first case, we got a running time of big O of n to the d times log n.

And again, this is d, the same d that was in the final term of the recurrence.

Okay, the work done outside of the recursive calls.

So the first case,

the running time is the same as the running time in the recurrence,

outside of the recursive calls, but we pick up an extra log n factor.

In the second case, where a is smaller than b to the d,

the running time is merely big-O of n to the d.

And this case might be somewhat stunning that this could ever occur,

because of course, in recurrence, what do you do?

You do some recursion, plus you do n to the d work outside of the recursion.

So in the second case, it actually says that the work is dominated by

just what's done outside the recursion in the outermost call.

The third case will initially seem the most mysterious.

When a is strictly bigger than b to the d,

we're going to get a running time of big-O of n to the log base b of a.

Where, again, recall, a is the number of recursive calls and

b is the factor by which the input size shrinks before you recurse.

So that's the master method with its three cases.

Let me give this to you in a cleaner slide to make sure there's no

ambiguity in my handwriting.

So here's the exact same statement, the master method

once again with its three cases, depending on how a compares to b to the d.

So one thing you'll notice about this version of the master method is that it

only gives upper bounds.

So we only say that the solution to the recurrence is big-O of some function.

And that's because if you go back to our recurrence,

we used big-O rather than theta in the recurrence.

And this is in the spirit of the course, where as algorithm designers,

our natural focus is on upper bounds, on guarantees for

the worst case running time of an algorithm.

And we're not going to focus too much most of the time on proving stronger bounds in

terms of theta notation.

Now, a good exercise for

you, to check if you really understand the proof of the master method after we go

through it will be to show that if you strengthen the hypothesis and

you assume the recurrence has the form T of n equals a times T of n over b plus

theta of n to the d, then in fact, all three of these big-O's in the statement of

the master method become thetas and the solution becomes asymptotically exact.

So one final comment.

You'll notice that I'm being asymmetrically sloppy with the two

logarithms that appear in these formulas.

So let me just explain why.

In particular, you'll notice that in case one, with the logarithm,

I'm not specifying the base.

Why is that true?

Well, it's because the the logarithm, with respect to any two different bases,

differs by a constant factor.

So the logarithm base e, that is, the natural logarithm, and the logarithm base

2, for example, differ by only a constant factor independent of the argument n.

So you can switch this logarithm to whatever constant base you like,

it only changes the leading constant factor,

which of course is being suppressed in the big-O notation anyways.

On the other hand, in case three, where we have a logarithm in the exponent,

once it's in the exponent, we definitely care about that constant.

Constants is the difference between, say, linear time and quadratic time.

So we need to keep careful track of the logarithm base

in the exponent in case three, and that base is precisely b,

the factor by which the input shrinks with each recursive call.

So that's the precise statement of the master method,

and the rest of this lecture will work toward understanding the master method.

So first, in the next video, we'll look at a number of examples, including resolving

the running time of Gauss's recursive algorithm for integer multiplication.

Following those several examples, we'll prove the master method.

And I know now these three cases probably look super mysterious,

but if I do my job, by the end of the analysis,

these three cases will seem like the most natural thing in the world, as

will these somewhat exotic looking formula for exactly what the running time is.

Explore nosso catálogo

Registre-se gratuitamente e obtenha recomendações, atualizações e ofertas personalizadas.

O Coursera proporciona acesso universal à melhor educação do mundo fazendo parcerias com as melhores universidades e organizações para oferecer cursos on-line.

© 2019 Coursera Inc. Todos os direitos reservados.

Baixar na App Store

Baixar no Google Play

Coursera
Sobre
Liderança
Carreiras
Lista de cursos
Certificados
Certificados MasterTrack™
Notas
For Enterprise
For Government

Comunidade
Learners
Partners
Developers
Beta Testers
Translators

Conectar
Blog
Facebook
LinkedIn
Twitter
Instagram
YouTube
Tech Blog

Mais
Termos
Privacidade
Ajuda
Acessibilidade
Imprensa
Contato
Diretório
Afiliados