00:00:00
ANNOUNCER: Open content is
provided under a creative
00:00:02
commons license.
00:00:03
Your support will help MIT
OpenCourseWare continue to
00:00:06
offer High-quality educational
resources for free.
00:00:10
To make a donation, or view
additional materials from
00:00:13
hundreds of MIT courses,
visit MIT OpenCourseWare
00:00:17
at ocw.mit.edu .
00:00:19
PROFESSOR ERIC GRIMSON:
Let's recap where we were.
00:00:23
Last lecture, we talked
about, or started to
00:00:25
talk about, efficiency.
00:00:27
Orders of growth.
00:00:30
And I'll remind you, we saw a
set of algorithms, and part of
00:00:33
my goal was to get you to begin
to recognize characteristics of
00:00:36
algorithms that map into
a particular class.
00:00:40
So what did we see?
00:00:40
We saw linear algorithms.
00:00:42
Typical characterization, not
all the time, but typical
00:00:45
characterization, is an
algorithm that reduces the size
00:00:49
of a problem by one, or by some
constant amount each time, is
00:00:54
typically an example of
a linear algorithm.
00:00:57
And we saw a couple of examples
of linear algorithms.
00:01:00
We also saw a logarithmic
algorithm. and we like
00:01:03
log algorithms, because
they're really fast.
00:01:05
A typical characteristic of a
log algorithm is a pro-- or
00:01:09
sorry, an algorithm where
it reduces the size of the
00:01:12
problem by a constant factor.
00:01:14
Obviously-- and that's a bad
way of saying it, I said
00:01:16
constant the previous time--
in the linear case, it's
00:01:18
subtract by certain amount.
00:01:19
In the log case, it's
divide by an amount.
00:01:21
Cut the problem in half.
00:01:23
Cut the problem in half again.
00:01:25
And that's a typical
characterization of
00:01:26
a log algorithm.
00:01:28
We saw some quadratic
algorithms, typically those are
00:01:31
things with multiple nested
loops, or iterative or
00:01:33
recursive calls, where you're
doing, say, a linear amount of
00:01:36
time but you're doing it a
linear number of times, and so
00:01:39
it becomes quadratic, and
you'll see other polynomial
00:01:42
kinds of algorithms.
00:01:43
And finally, we saw an example
of an exponential algorithm,
00:01:46
those Towers of Hanoi.
00:01:48
We don't like exponential
algorithms, or at least you
00:01:51
shouldn't like them, because
they blow up quickly.
00:01:53
And we saw some
examples of that.
00:01:55
And unfortunately, some
problems are inherently
00:01:58
exponential, you're sort of
stuck with that, and then
00:02:00
you just have to try be
as clever as you can.
показать еще
русский▼
English
español
italiano
日本語
中文
português
français
Deutsch
