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

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

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

ANNOUNCER: Open 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 ERIC GRIMSON: Let's recap where we were. Last lecture, we talked about, or started to talk about, efficiency. Orders of growth. Complexity. And I'll remind you, we saw a set of algorithms, and part of my goal was to get you to begin to recognize characteristics of algorithms that map into a particular class.

So what did we see? We saw linear algorithms. Typical characterization, not all the time, but typical characterization, is an algorithm that reduces the size of a problem by one, or by some constant amount each time, is typically an example of a linear algorithm. And we saw a couple of examples of linear algorithms.

We also saw a logarithmic algorithm. and we like log algorithms, because they're really fast. A typical characteristic of a log algorithm is a pro — or sorry, an algorithm where it reduces the size of the problem by a constant factor. Obviously — and that's a bad way of saying it, I said constant the previous time — in the linear case, it's subtract by certain amount. In the log case, it's divide by an amount. Cut the problem in half. Cut the problem in half again. And that's a typical characterization of a log algorithm.

We saw some quadratic algorithms, typically those are things with multiple nested loops, or iterative or recursive calls, where you're doing, say, a linear amount of time but you're doing it a linear number of times, and so it becomes quadratic, and you'll see other polynomial kinds of algorithms.

And finally, we saw an example of an exponential algorithm, those Towers of Hanoi. We don't like exponential algorithms, or at least you shouldn't like them, because they blow up quickly. And we saw some examples of that. And unfortunately, some problems are inherently exponential, you're sort of stuck with that, and then you just have to try be as clever as you can.

OK. At the end of the lecture last time, I also showed you an example of binary search. And I want to redo that in a little more detail today, because I felt like I did that a little more quickly than I wanted to, so, if you really got binary search, fall asleep for about ten minutes, just don't snore, your neighbors may not appreciate it, but we're going to go over it again, because it's a problem and an idea that we're going to come back to, and I really want to make sure that I do this in a way that makes real good sense you.

Again. Basic premise of binary search, or at least we set it up was, imagine I have a sorted list of elements. We get, in a second, to how we're going to get them sorted, and I want to know, is a particular element in that list. . And the basic idea of binary search is to start with the full range of the list, pick the midpoint, and test that point. If it's the thing I'm looking for, I'm golden. If not, because the list is sorted, I can use the difference between what I'm looking for and that midpoint to decide, should I look in the top half of the list, or the bottom half of the list? And I keep chopping it down.

And I want to show you a little bit more detail of that, so let's create a simple little list here. All right? I don't care what's in there, but just assume that's my list.

PROFESSOR ERIC GRIMSON: Let's recap where we were. Last lecture, we talked about, or started to talk about, efficiency. Orders of growth. Complexity. And I'll remind you, we saw a set of algorithms, and part of my goal was to get you to begin to recognize characteristics of algorithms that map into a particular class.

So what did we see? We saw linear algorithms. Typical characterization, not all the time, but typical characterization, is an algorithm that reduces the size of a problem by one, or by some constant amount each time, is typically an example of a linear algorithm. And we saw a couple of examples of linear algorithms.

We also saw a logarithmic algorithm. and we like log algorithms, because they're really fast. A typical characteristic of a log algorithm is a pro — or sorry, an algorithm where it reduces the size of the problem by a constant factor. Obviously — and that's a bad way of saying it, I said constant the previous time — in the linear case, it's subtract by certain amount. In the log case, it's divide by an amount. Cut the problem in half. Cut the problem in half again. And that's a typical characterization of a log algorithm.

We saw some quadratic algorithms, typically those are things with multiple nested loops, or iterative or recursive calls, where you're doing, say, a linear amount of time but you're doing it a linear number of times, and so it becomes quadratic, and you'll see other polynomial kinds of algorithms.

And finally, we saw an example of an exponential algorithm, those Towers of Hanoi. We don't like exponential algorithms, or at least you shouldn't like them, because they blow up quickly. And we saw some examples of that. And unfortunately, some problems are inherently exponential, you're sort of stuck with that, and then you just have to try be as clever as you can.

OK. At the end of the lecture last time, I also showed you an example of binary search. And I want to redo that in a little more detail today, because I felt like I did that a little more quickly than I wanted to, so, if you really got binary search, fall asleep for about ten minutes, just don't snore, your neighbors may not appreciate it, but we're going to go over it again, because it's a problem and an idea that we're going to come back to, and I really want to make sure that I do this in a way that makes real good sense you.

Again. Basic premise of binary search, or at least we set it up was, imagine I have a sorted list of elements. We get, in a second, to how we're going to get them sorted, and I want to know, is a particular element in that list. . And the basic idea of binary search is to start with the full range of the list, pick the midpoint, and test that point. If it's the thing I'm looking for, I'm golden. If not, because the list is sorted, I can use the difference between what I'm looking for and that midpoint to decide, should I look in the top half of the list, or the bottom half of the list? And I keep chopping it down.

And I want to show you a little bit more detail of that, so let's create a simple little list here. All right? I don't care what's in there, but just assume that's my list.

Загрузка...

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

Ты добавил

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

Ты добавил