Материал готовится,

пожалуйста, возвращайтесь позднее

пожалуйста, возвращайтесь позднее

My name is Erik Demaine. You should call me Erik. Welcome back to 6.046. This is Lecture 2. And today we are going to essentially fill in some of the more mathematical underpinnings of Lecture 1. So, Lecture 1, we just sort of barely got our feet wet with some analysis of algorithms, insertion sort and mergesort. And we needed a couple of tools. We had this big idea of asymptotics and forgetting about constants, just looking at the lead term. And so, today, we're going to develop asymptotic notation so that we know that mathematically. And we also ended up with a recurrence with mergesort, the running time of mergesort, so we need to see how to solve recurrences. And we will do those two things today. Question? Yes, I will speak louder. Thanks. Good.

Even though I have a microphone, I am not amplified. OK, so let's start with asymptotic notation. We have seen some basic asymptotic notation. I am sure you have seen it in other classes before, things like big O-notation. And today we are going to really define this rigorously so we know what is true and what is not, what is valid and what is not. We are going to define, and unfortunately today is going to be really mathematical and really no algorithms today, which is sort of an anticlimax. But next lecture we will talk about real algorithms and will apply all the things we learned today to real algorithms.

This is big O-notation, capital O-notation. We have f(n)=O[g(n)]. This means that there are some suitable constants, c and n_o, such that f is bounded by cg(n) for all sufficiently large n. So, this is pretty intuitive notion. We have seen it before. We are going to assume that f(n) is non-negative here. And I just want f(n) to be bounded above by g(n). We have seen a bunch of examples, but something like 2n^2=O(n^3) defined.

And roughly this means if you drop leading constants and low order terms then this is less than or equal to that. So, big O corresponds roughly to less than or equal to. But this is the formalization. Another way to think of it formally, a funny thing about this notation is it is asymmetric. Normally, you think of a quality being symmetric. If A=B then B=A. But it's not true here. We do not have n^3 being big O of n^2.

We don't even have big O of n^3 equaling n^2. So, we will see exactly what that means in a second. But before we get there, this is a bit bizarre notation and you should always think about what it really means. Another way to think about what it really means is that f(n) is in some set of functions that are like g. You could define big O[g(n)] to be a set of functions, let's call it f(n), such that there exist constants. They are the same definition, I think, fancy here, c and n_o, such that we have the bound f(n) is between zero and cg(n).

It is a bit of a long definition, and that is why we use the notation, to avoid having to write this over and over. You can think of instead of n^2 being equal to big O of n^3, what we really mean is that 2n^2 is in the set big O(n^3). When we write equal sign, we in some sense mean this in the set, but we are going to use equal sign. You could write this. And occasionally you see papers that write this, but this is the notation that we are going to use. That has the consequence the equal sign is asymmetric, just like this operator. We have some nifty ways that we actually use big O-notation.

And it is using it as a macro. By the way, we have a lot to cover today, so I am going to go relatively fast.

Even though I have a microphone, I am not amplified. OK, so let's start with asymptotic notation. We have seen some basic asymptotic notation. I am sure you have seen it in other classes before, things like big O-notation. And today we are going to really define this rigorously so we know what is true and what is not, what is valid and what is not. We are going to define, and unfortunately today is going to be really mathematical and really no algorithms today, which is sort of an anticlimax. But next lecture we will talk about real algorithms and will apply all the things we learned today to real algorithms.

This is big O-notation, capital O-notation. We have f(n)=O[g(n)]. This means that there are some suitable constants, c and n_o, such that f is bounded by cg(n) for all sufficiently large n. So, this is pretty intuitive notion. We have seen it before. We are going to assume that f(n) is non-negative here. And I just want f(n) to be bounded above by g(n). We have seen a bunch of examples, but something like 2n^2=O(n^3) defined.

And roughly this means if you drop leading constants and low order terms then this is less than or equal to that. So, big O corresponds roughly to less than or equal to. But this is the formalization. Another way to think of it formally, a funny thing about this notation is it is asymmetric. Normally, you think of a quality being symmetric. If A=B then B=A. But it's not true here. We do not have n^3 being big O of n^2.

We don't even have big O of n^3 equaling n^2. So, we will see exactly what that means in a second. But before we get there, this is a bit bizarre notation and you should always think about what it really means. Another way to think about what it really means is that f(n) is in some set of functions that are like g. You could define big O[g(n)] to be a set of functions, let's call it f(n), such that there exist constants. They are the same definition, I think, fancy here, c and n_o, such that we have the bound f(n) is between zero and cg(n).

It is a bit of a long definition, and that is why we use the notation, to avoid having to write this over and over. You can think of instead of n^2 being equal to big O of n^3, what we really mean is that 2n^2 is in the set big O(n^3). When we write equal sign, we in some sense mean this in the set, but we are going to use equal sign. You could write this. And occasionally you see papers that write this, but this is the notation that we are going to use. That has the consequence the equal sign is asymmetric, just like this operator. We have some nifty ways that we actually use big O-notation.

And it is using it as a macro. By the way, we have a lot to cover today, so I am going to go relatively fast.

Загрузка...

Выбрать следующее задание

Ты добавил

Выбрать следующее задание

Ты добавил