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

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

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

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: Last time, we ended up, we sort of did this tag team thing, Professor Guttag did the first half, I did the second half of the lecture, and the second half of the lecture, we started talking about complexity. Efficiency. Orders of growth. And that's what we're going to spend today on, is talking about that topic. I'm going to use it to build over the next couple of lectures.

I want to remind you that we were talking at a fairly high level about complexity. We're going to get down into the weeds in a second here. But the things we were trying to stress were that it's an important design decision, when you are coming up with a piece of code, as to what kind of efficiency your code has.

And the second thing that we talked about is this idea that we want you to in fact learn how to relate a choice you make about a piece of code to what the efficiency is going to be. So in fact, over the next thirty or forty minutes, we're going to show you a set of examples of sort of canonical algorithms, and the different classes of complexity.

Because one of the things that you want to do as a good designer is to basically map a new problem into a known domain. You want to take a new problem and say, what does this most look like? What is the class of algorithm that's — that probably applies to this, and how do I pull something out of that, if you like, a briefcase of possible algorithms to solve?

All right, having said that, let's do some examples. I'm going to show you a sequence of algorithms, they're mostly simple algorithms, that's OK. But I want you to take away from this how we reason about the complexity of these algorithms. And I'll remind you, we said we're going to mostly talk about time. We're going to be counting the number of basic steps it takes to solve the problem.

So here's the first example I want to do. I'm going to write a function to compute integer power exponents. a to the b where b is an integer. And I'm going to do it only using multiplication and addition and some simple tests. All right? And yeah, I know it comes built in, that's OK, what we want to do is use it as an example to look at it.

So I'm going to build something that's going to do iterative exponentiation. OK? And in fact, if you look at the code up here, and it's on your handout, the very first one, x 1, right here — if I could ask you to look at it — is a piece of code to do it. And I'm less interested in the code than how we're going to analyze it, but let's look at it for a second.

All right, you can see that this little piece of code, it's got a loop in there, and what's it doing? It's basically cycling through the loop, multiplying by a each time. So first time through the loop, the answer is 1. Second time it — sorry, as it enters the loop, at the time it enter — exits, the answer is a. Next time through the loop it goes to a squared. Next time through the loop it goes to a cubed. And it's just gathering together the multiplications while counting down the exponent. And you can see it when we get down to the end test here, we're going to pop out of there and we're going to return the answer.

I could run it, it'll do the right thing.

PROFESSOR ERIC GRIMSON: Last time, we ended up, we sort of did this tag team thing, Professor Guttag did the first half, I did the second half of the lecture, and the second half of the lecture, we started talking about complexity. Efficiency. Orders of growth. And that's what we're going to spend today on, is talking about that topic. I'm going to use it to build over the next couple of lectures.

I want to remind you that we were talking at a fairly high level about complexity. We're going to get down into the weeds in a second here. But the things we were trying to stress were that it's an important design decision, when you are coming up with a piece of code, as to what kind of efficiency your code has.

And the second thing that we talked about is this idea that we want you to in fact learn how to relate a choice you make about a piece of code to what the efficiency is going to be. So in fact, over the next thirty or forty minutes, we're going to show you a set of examples of sort of canonical algorithms, and the different classes of complexity.

Because one of the things that you want to do as a good designer is to basically map a new problem into a known domain. You want to take a new problem and say, what does this most look like? What is the class of algorithm that's — that probably applies to this, and how do I pull something out of that, if you like, a briefcase of possible algorithms to solve?

All right, having said that, let's do some examples. I'm going to show you a sequence of algorithms, they're mostly simple algorithms, that's OK. But I want you to take away from this how we reason about the complexity of these algorithms. And I'll remind you, we said we're going to mostly talk about time. We're going to be counting the number of basic steps it takes to solve the problem.

So here's the first example I want to do. I'm going to write a function to compute integer power exponents. a to the b where b is an integer. And I'm going to do it only using multiplication and addition and some simple tests. All right? And yeah, I know it comes built in, that's OK, what we want to do is use it as an example to look at it.

So I'm going to build something that's going to do iterative exponentiation. OK? And in fact, if you look at the code up here, and it's on your handout, the very first one, x 1, right here — if I could ask you to look at it — is a piece of code to do it. And I'm less interested in the code than how we're going to analyze it, but let's look at it for a second.

All right, you can see that this little piece of code, it's got a loop in there, and what's it doing? It's basically cycling through the loop, multiplying by a each time. So first time through the loop, the answer is 1. Second time it — sorry, as it enters the loop, at the time it enter — exits, the answer is a. Next time through the loop it goes to a squared. Next time through the loop it goes to a cubed. And it's just gathering together the multiplications while counting down the exponent. And you can see it when we get down to the end test here, we're going to pop out of there and we're going to return the answer.

I could run it, it'll do the right thing.

Загрузка...

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

Ты добавил

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

Ты добавил