Name: CS50 2016 - 第4週 - 記憶 (CS50 2016 - Week 4 - Memory)
Uploaded: 2021-01-14T06:43:20.000Z
Duration: 1 h 51 min 43 s
Description: VoiceTubeの動画で発音を聞きながら英語表現を覚えよう！学べる英語：

DAVID J. MALAN: All right, this is CS50, and this is week 4.

So let's consider first what we did last time, which was focus on numbers

and focus on how we can search them and how we can sort them.

And in particular, we took a look at a number of algorithms

that we finally gave names to, a couple of which we actually saw back in week

So we looked more formally last time at linear search,

this process of searching elements from left to right or right to left

as though you're walking along a line looking for some value.

We looked at binary search, a divide and conquer algorithm

whereby we started, in this case, in the middle,

and then we looked left to right and then went to the left,

went to the right, and then did the same problem again and again.

How do you get to the point where you can

use an algorithm like binary search, which

Well, bubble sort was one algorithm that essentially

swapped elements pairwise from left to right, from left to right,

until finally the biggest elements bubbled up to the top,

and the whole list was ultimately sorted.

And selection sort is the name implied, selected,

then smallest element again and again and again, plucking it out of the list,

Insertion sort, meanwhile, walked through the list really just once,

and as it encountered each element, it then

inserted it into the sorted half of the list, the left half of the list

And then lastly, and where we really concluded and really got more bang

for our buck was this final algorithm merge

sort, which actually solved this same problem no less correctly, but so much

And indeed, lends itself perhaps to a fundamentally better design

in so far as it leverages a much better running time, so to speak.

In fact, we started to ascribe these kinds of formulas

to the running times of or the performance of our algorithms n

squared, otherwise known as quadratic, whereby

you take n times n number of steps or minutes or seconds

or some unit of measure, n log in, which is actually what we achieved

with the merge source, which was much faster

recall than the end squared algorithms like bubble sort and selection sort

and insertion sort in their upper bounds.

n would be something linear, like a straight line relationship.

Logarithmic of n, log of n, log base 2 of n,

technically, would be something like week 0's divide

and conquer approach looking for Mike Smith,

And then one, which doesn't have to be literally one step.

Maybe it's two, maybe it's 10, but it is a fixed finite constant number

And that too might be the running time of some algorithm.

Now how do we describe the running times of algorithms?

Well, we use some special notation, asymptotic notation,

so to speak, which while it might look cryptic at first glance,

really is just a handy way of succinctly expressing the fact that you know what

the upper bound on some algorithms running time is,

what the lower bounds on some algorithms running time is.

And if those are one in the same formulas in theta,

do you have a coincidence of the two of big O, so speak, and capital theta.

So that, while Greek, literally is just a way

of expressing a bit more succinctly what these running times are.

And we'll continue to revisit this issue as we

look at more algorithms and soon data structures still.

We pull back a layer here and admit that there is no such thing as a string.

Indeed, all this time we've been saying that there's ins, and there's floats,

and there's chars, and there's doubles and more.

And we've also been saying there are strings,

This is sort of a figment of the imagination of our so-called CS50

But it's a pedagogical simplification that we've

been using for the past several weeks, so as to not get

lost in the weeds, the lower level implementation

details of what a string is, so that we can just get

But now we'll begin to look underneath that hood

and see what a string actually is and what the implications are.

And it turns out, while more complicated in some sense,

it really just boils down to some first principles,

what it is the computer is doing underneath that hood.

So let's take a look at string first by way of a couple of examples.

Let's go in to CS50 IDE, create a new file, save it as Compare zero dot C,

and look at the little program that actually doesn't necessarily

In particular, let me go ahead and include our typical,

include CS 50 dot H. And let me go ahead and include standard IO dot H as well.

Let me go ahead and use main void, so I'm not

going to worry about any command line arguments for now.

And then I'm going to go ahead and just prompt the user.

Hey user, give me a string called S for instance.

Now I'm going to go ahead and do string S,

gets gets string, open paren and close parens,

字幕リスト動画再生

CS50 2016 - 第4週 - 記憶 (CS50 2016 - Week 4 - Memory)

literally

sort

pattern

character