Name: CS50 2017 - 再生4 - メモリ (CS50 2017 - Lecture 4 - Memory)
Uploaded: 2021-01-14T07:21:04.000Z
Duration: 1 h 42 min 50 s
Description: VoiceTubeの動画で発音を聞きながら英語表現を覚えよう！学べる英語：

DAVID MALAN: All right, well, this is CS50.

And you'll recall that last time, we focused really on algorithms.

Not so much code, but on algorithms, the step-by-step instructions

And we did this in the context of numbers.

But more specifically, we assumed that we had places to put these numbers.

And that was back-to-back-to-back memory where we could put numbers or maybe

But for the most part, we haven't really had more sophisticated ways

of laying information out in memory, and so we're kind of

stuck going left to right, right to left, or maybe a little more

intelligently using what we call binary search, or divide

and conquer, and kind of split the difference.

Because if you recall, we have memory inside

of our computers, which we keep modeling as this rectangular region

Much like you could paint on a canvas, so could we kind of move things around

But we don't yet have the vocabulary or really the data structures,

as they're going to be called, to do anything more

And so today and next time when we begin to start

to solve problems more cleverly and then revisit some of the kinds of algorithms

that we've seen already, and those algorithms last time

were like these, linear search and binary search.

And that brought us full circle back to week zero when we used those,

And then recall that we introduced sorting.

Sorting's a more involved algorithm, more time-consuming.

But it was a precondition for which of those first two algorithms

Yeah, so binary search assumes, just like a phone book

assumes that the names are actually sorted from left to right.

Otherwise, you're completely wasting your time,

if you're splitting a phone book in half,

if there's no rhyme or reason to where the names and the numbers are.

So this is sort of a requisite ingredient

to get better efficiency with other algorithms.

And it's going to be up to decide, you know what?

It's going to take me more time to figure out

how to write the code for an algorithm than it

is to just write it the easy way, and just cut a corner

But if you're a company, if you're a website,

if you're a piece of software that's doing the same algorithm again

and again and again, maybe you do want to spend that upfront cost.

Maybe it's human time, like your time, figuring out the algorithm.

Or maybe it's n squared or hopefully something better, n log n,

that you have to spend just to get the data in a nice format,

and then, thereafter, everything can be blazing fast.

So especially when we get to web programming,

we'll revisit these questions when we talk about databases as well.

But recall last time we also introduced a bit of formalism.

And we won't get more mathematical than this.

But These were sort of broad strokes with which

we can paint the efficiency of algorithms from sort of slowest on top

And recall that we introduced some Greek symbols here just

to kind of standardize what it is we're talking about.

And as a quick check, big O refers to what kind of boundary?

So maybe in the worst case, what's the upper bound on your algorithm's running

How many steps, how many seconds, how many hours might it take?

By contrast, we had omega, which was the lower bound.

And then less commonly used, at least in CS50,

will be theta, which is just when those two are the same.

But realize those are the three ingredients,

especially if you continue on in other CS classes, that might be revisited.

And we introduce this, so that we're not just counting seconds.

We're not, like, looking at our watch and counting how fast our algorithm is,

because that's not a very reliable way of measuring whose algorithm is better

Maybe my Mac is faster than your Mac or your PC.

And so we don't want to just look at raw time.

We want to think about things a little more theoretically,

albeit without worrying about denominators and lower order terms.

We talk generally in terms of these higher order terms

So I thought it would be fun to kind of reminisce.

Some years ago, when a certain someone was still

just a senator, being interviewed by Google's own Eric Schmidt,

And this was an interview that took an interesting algorithmic turn.

And I like to think of the presidency as a job interview.

- I mean, you're going through the rigors now.

字幕リスト動画再生

CS50 2017 - 再生4 - メモリ (CS50 2017 - Lecture 4 - Memory)

literally

sort

context

negative