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

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

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

The following content is provided under a creative commons license. Your support will help MIT OpenCourseWare continue to offer high-quality educational resources for free. To make a donation or view additional materials from hundreds of MIT courses, visit MIT OpenCourseWare at ocw.mit.edu.

PROFESSOR: Last time we were talking about binary search and I sort of left a promise to you which I need to pick up. I want to remind you, we were talking about search, which is a very fundamental thing that we do in a whole lot of applications. We want to go find things in some data set. And I'll remind you that we sort of a separated out two cases. We said if we had an ordered list, we could use binary search. And we said that was log rhythmic, took log n time where n is the size of the list.

If it was an unordered list, we were basically stuck with linear search. Got to walk through the whole list to see if the thing is there. So that was of order in. And then one of the things that I suggested was that if we could figure out some way to order it, and in particular, if we could order it in n log n time, and we still haven't done that, but if we could do that, then we said the complexity changed a little bit. But it changed in a way that I want to remind you.

And the change was, that in this case, if I'm doing a single search, I've got a choice. I could still do the linear case, which is order n or I could say, look, take the list, let's sort it and then search it. But in that case, we said well to sort it was going to take n log n time, assuming I can do that.

Once I have it sorted I can search it in log n time, but that's still isn't as good as just doing n. And this led to this idea of amortization, which is I need to not only factor in the cost, but how am I going to use it? And typically, I'm not going to just search once in a list, I'm going to search multiple times. So if I have to do k searches, then in the linear case, I got to do order n things k times. It's order k n.

Whereas in the ordered case, I need to get them sorted, which is still n log n, but then the search is only log n. I need to do k of those. And we suggested well this is better than that. This is certainly better than that. m plus k all times log n is in general going to be much better than k times n. It depends on n and k but obviously as n gets big, that one is going to be better.

And that's just a way of reminding you that we want to think carefully, but what are the things we're trying to measure when we talk about complexity here? It's both the size of the thing and how often are we going to use it? And there are some trade offs, but I still haven't said how I'm going to get an n log n sorting algorithm, and that's what I want to do today. One of the two things I want to do today.

To set the stage for this, let's go back just for a second to binary search. At the end of the lecture I said binary search was an example of a divide and conquer algorithm. Sort of an Attila the Hun kind of approach to doing things if you like. So let me say — boy, I could have made a really bad political joke there, which I will forego, right.

Let's say what this actually means, divide and conquer. Divide and conquer says basically do the following: split the problem into several sub-problems of the same type. I'll come back in a second to help binary searches matches in that, but that's what we're going to do.

PROFESSOR: Last time we were talking about binary search and I sort of left a promise to you which I need to pick up. I want to remind you, we were talking about search, which is a very fundamental thing that we do in a whole lot of applications. We want to go find things in some data set. And I'll remind you that we sort of a separated out two cases. We said if we had an ordered list, we could use binary search. And we said that was log rhythmic, took log n time where n is the size of the list.

If it was an unordered list, we were basically stuck with linear search. Got to walk through the whole list to see if the thing is there. So that was of order in. And then one of the things that I suggested was that if we could figure out some way to order it, and in particular, if we could order it in n log n time, and we still haven't done that, but if we could do that, then we said the complexity changed a little bit. But it changed in a way that I want to remind you.

And the change was, that in this case, if I'm doing a single search, I've got a choice. I could still do the linear case, which is order n or I could say, look, take the list, let's sort it and then search it. But in that case, we said well to sort it was going to take n log n time, assuming I can do that.

Once I have it sorted I can search it in log n time, but that's still isn't as good as just doing n. And this led to this idea of amortization, which is I need to not only factor in the cost, but how am I going to use it? And typically, I'm not going to just search once in a list, I'm going to search multiple times. So if I have to do k searches, then in the linear case, I got to do order n things k times. It's order k n.

Whereas in the ordered case, I need to get them sorted, which is still n log n, but then the search is only log n. I need to do k of those. And we suggested well this is better than that. This is certainly better than that. m plus k all times log n is in general going to be much better than k times n. It depends on n and k but obviously as n gets big, that one is going to be better.

And that's just a way of reminding you that we want to think carefully, but what are the things we're trying to measure when we talk about complexity here? It's both the size of the thing and how often are we going to use it? And there are some trade offs, but I still haven't said how I'm going to get an n log n sorting algorithm, and that's what I want to do today. One of the two things I want to do today.

To set the stage for this, let's go back just for a second to binary search. At the end of the lecture I said binary search was an example of a divide and conquer algorithm. Sort of an Attila the Hun kind of approach to doing things if you like. So let me say — boy, I could have made a really bad political joke there, which I will forego, right.

Let's say what this actually means, divide and conquer. Divide and conquer says basically do the following: split the problem into several sub-problems of the same type. I'll come back in a second to help binary searches matches in that, but that's what we're going to do.

Загрузка...

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

Ты добавил

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

Ты добавил