Name: 弁護士のためのCS50 2019 - アルゴリズム、データ構造 (CS50 for Lawyers 2019 - Algorithms, Data Structures)
Uploaded: 2021-01-14T10:20:50.000Z
Duration: 1 h 18 min 7 s
Description: VoiceTubeの動画で発音を聞きながら英語表現を覚えよう！学べる英語：

程度の副詞

DAVID MALAN: Recall that an algorithm is just step-by-step instructions

Not unlike this problem here wherein I sought Mike Smith among the whole phone

But up until now, we've really only focused

on those step-by-step instructions and not

so much on how the data we are searching is stored.

Of course, in this version of that problem, it's stored here on paper,

but in the digital world, it's of course not going to be paper, but 0's and 1's.

But it's one thing to say that the numbers and maybe even the names

are stored ultimately as 0's and 1's, but where and how exactly?

There's all those transistors and they're flipping on and off,

but with respect to each other, are those numbers laid out left to right,

top to bottom, are they all over the place?

Let's actually take a look at that question now

and consider how a computer leverages what

are called data structures to facilitate implementation of algorithms.

Indeed, how you lay out a computer's data inside of its memory

has non-trivial impacts on the performance or efficiency

of your algorithms, whereas the algorithm itself

can be correct as we've seen, but not necessarily efficient logically.

Both space and the representation underneath the hood of your data

And rather than focus on, say, a whole phone book of names and numbers,

let's focus just on numbers, and much smaller numbers that aren't even

phone numbers, but just integers, and only save seven of them at a time.

And I've hidden these seven numbers, if you will,

And so by knocking and opening, one of these doors

And the goal at hand, though, is to find a very specific number,

just like I sought one specific phone number before, this time I want

I'll go with the one closest to me and knock, knock, knock--

Let's open this door next and-- oh, we seem to have veered down smaller,

So 50 is not there and 50 is not there and 50 is, in fact, there.

Within just six steps, have I found the number in question.

But of course, to be fair, there were only seven doors.

So if we generalize that to say that there were n doors where n is just

a number, well that was roughly n doors I had to open among the n doors

You know, my instincts like yours were perhaps to start at the left

and move to the right, and we seem to be on a good path initially.

We went from 15 to 23, and then darn it if 16

didn't throw a wrench in the works, because I expected it,

perhaps naively, to be bigger and bigger as I moved right.

But honestly, had I not told you anything-- and indeed I did-- then

you wouldn't have known anything about these numbers other than maybe

I told you nothing as to the magnitude or the size

of any of the other numbers, let alone the order,

but in the world of the phone book, of course,

we were able to take for granted that those names were

sorted by the phone company for us-- from left to right, from A to Z.

But in this case, if your data is just added to the computer's memory one

at a time in no particular order, the onus

is on you, the programmer or algorithm, to find that number

So these seven doors were by design randomly assigned a number.

I might not have gone with my initial instincts

I might have, effectively blinded, gone and touched 50 and just gotten lucky,

and then it would have been just one step.

But there's only a one in seven chance I would have been correct so quickly,

so that's not really an algorithm that I could

reproduce with the same efficiency again and again.

And how does the phone company enable us to do better?

Well they, of course, put in a huge amount of effort upfront

to sort all of those names and associated numbers from left

to right, from A to Z. And so that's a huge leg up for us,

because then I can assume I can do divide and conquer or so-called binary

search, dividing that phone book in two as

implied by "bi" in "binary," having the problem again and again.

But someone's got to do that work for us, be it the phone company

So let's take one more stab at this problem,

this time presuming that the seven doors in question

do, in fact, have the numbers behind them sorted from left to right,

I have seven doors behind which are those same numbers,

but this time they are sorted from left to right.

And no skipping ahead thinking that, well, I remember all the other numbers,

字幕リスト動画再生

弁護士のためのCS50 2019 - アルゴリズム、データ構造 (CS50 for Lawyers 2019 - Algorithms, Data Structures)

ultimately

sort

access

constant