Name: 資料結構（Data Structures Easy to Advanced Course - Full Tutorial from a Google Engineer）
Uploaded: 2022-10-23T12:48:01.000Z
Duration: 8 h 3 min 17 s
Description: 【看影片學英語】數萬部 YouTube 影片，搭配英漢字典即點即查，輕鬆掌握單字發音與用法，長久累積看電影不必再看字幕。

In these first few videos, I want to lay the foundation of some core concepts you will

need throughout these video tutorials. Let's get started with the basics. So what is a

程度副詞

data structure? one definition that I really like is a data structure is a way of organizing

data so that it can be used efficiently. And that's all data structure really is it is

a way of organizing data in some fashion so that later on it can be accessed, queried,

or perhaps even updated quickly and easily. So why data structures? Why are they important?

Well, they are essential ingredients in creating fast and powerful algorithms. Another good

reason might be that they help us manage and organize our data in a very natural way. And

this last point, is more of my own making. And it's that it makes code cleaner and easier

to understand. As a side note, one of the major distinctions that I have noticed from

bad mediocre to excellent programmers is that the ones who really excel are the ones who

fundamentally understand how and when to use the appropriate data structure for the task

they're trying to finish. data structures can make the difference between having an

okay product and an outstanding one. It's no wonder that every computer science undergraduate

student is required to take a course in data structures. It is strange that before we even

begin talking about data structures that we need to talk about the abstraction of data

structures. What I'm talking about is the concept of an abstract data type. What is

an abstracted type and how does it differ from a data structure? Well, the answer is

that an abstract data type is an abstraction of a data structure, which provides only the

interface to which that data structure must adhere to. The interface does not give any

a specific data structure should be implemented, or in what programming language. One particular

example I like to give is to suppose that your abstract data type is for a mode of transportation

to get from point A to point B. Well, as we both know, there are many modes of transportation

to get from one place to another. So which one do you choose? some specific modes of

transportation might be walking or biking, perhaps even taking a train and so on, these

specific modes of transportation would be analogous to the data structures themselves.

We want to get from one place to another through some mode of transportation, that was our

abstract data type. How did we do that? Exactly? Well, that is the data structure. Here are

some examples of abstract data types on the left, and some possible underlying implementation

on the right hand side. As you can see, a list can be implemented in two ways. You can

have a dynamic array or a linked list. They both provide ways of adding, removing and

indexing elements in the list. Next, we have a queue and the map abstract data types, which

themselves can be implemented in a variety of ways. Notice that under the implementation

for a queue, I put a stack based queue because yes, you can have a queue, which is implemented

using only stacks. This may not be the most efficient way of implementing a queue. But

it does work and it is possible. The point here is that the abstract data type only defines

how a data structure should behave, and what methods it should have, but not the details

surrounding how those methods are implemented. Alright, now that we were done with abstract

data types, we need to have a quick look at the wild world of computational complexity,

to understand the performance that our data structures are providing. So as programmers,

we often find ourselves asking the same two questions over and over and over again. That

is, how much time does this algorithm need to finish and also how much space Does this

algorithm need for my computation. So, if your program takes a lifetime of the universe

to finish, then it's no good. Similarly, if your program runs in constant time, but requires

a space equal to the sum of all the bytes of all the files on the internet, internet,

your algorithm is also useless. So just standardize a way of talking about how much time and how

much space is required for an algorithm to run. theoretical computer scientists have

invented big O notation, amongst other things like big theta, big omega, and so on. But

we're interested in Big O because it tells us about the worst case. Big O notation only

cares about the worst case. So if your algorithm sorts numbers, imagine the input is the worst

possible arrangement of numbers for your particular sorting algorithm. Or, as a concrete example,

suppose you have an unordered list of unique numbers, and you're searching for the number

seven, or the position where seven occurs in your list. And the worst case isn't one

seven, that is at the beginning. Or in the middle of the list, it's one seven is the

very last element of the list. for that particular example, the time complexity would be linear

with respect to the number of elements in the size view list. Because you have to traverse

every single element until you find seven. The same concept applies to space, you can

just consider the worst possible amount of space your algorithm is going to need for

that particular input. There's also the fact that big O really only cares about what happens

when your input becomes arbitrarily large. We're not interested in what happens when

the input is small. For this reason, you'll see that we ignore things like constants and

multiplicative factors. So in our big O notation, you'll often see these coming up. Again, again,

when I say n, n is usually always want to be the input size coming into your algorithm,

there's always going to be some limitation of size n. So constant time referred to as

a one wrapped around a big O. If your algorithm case in logarithmic amount of time to finish,

we say that's big O of a log event. If it's linear, then we just say n, if it takes like

quadratic time or cubic time, then we say that's n raised to that power, it's exponential.

Usually, this is going to be something like two to the n three, the N, N number be greater

than one to the n. And then we also have n factorial. But we also have things in between

these like square root of n log log of n, n to the fifth and so on. Actually, almost

any mathematical expression containing n can be wrapped around a big O. And is big O notation

valid. Now, we want to talk about some properties of Big O. So to reiterate what we just saw

in the last two slides, Big O only really cares about what happens when input becomes

really big. So we're not interested when n is small, only

what happens when n goes to infinity. So this is how and why we get the first two properties.

The first that we can simply remove constant values added to our big O notation. Because

if you're adding a constant to infinity, well, let's just infinity, or if you're multiplying

a constant by infinity, yeah, that's still infinity. So we can ignore constants. But

of course, this is all theoretical. In the real world. If your constant is of size, 2

billion, probably, that's going to have a substantial impact on the running time of

However, let us look at a function f, which I've defined over some input size. And if

f of n is seven log of n cubed plus 15 n squared plus two n q plus eight. Well, big O of f

of n is just n cubed, because n cubed is the biggest, most dominant term in This function.

look at some concrete examples of how big O is used. So both of the following run in

constant time with respect to the input size, and because they don't depend on n

So on the left, when we're just adding or doing some mathematical formula, yes, that's

constant time. And on the right, okay, we're doing a loop, but the loop itself doesn't

depend on n. So it runs also in a constant amount of time. So as our input size gets

arbitrarily large, well, that loop is still going to run in the same amount of time regardless.

Now let's look at a linear example. So both the following actually run in

linear time with respect to the input size, and because we do a constant amount of work,

So on the left, we're incrementing, the counter AI by one each time. So f of n is and, and

clearly, when we wrap this in a big go get a big O of n. On the right, a little bit more

complicated, we're not incrementing by one, we're incrementing by three, so we're going

字幕列表影片播放

資料結構（Data Structures Easy to Advanced Course - Full Tutorial from a Google Engineer）

constant

structure

common

capacity