### 1.1 What is the data structure

What is the data structure ？

In ordinary life , We need to design the steel frame structure of the house to build a house , Line up orderly when you go shopping , This is the embodiment of a structural system , The data is the same , Although it is something in the virtual world , But there is also structure and order between data and data , We can call it a data structure .

This paper will explain various data structures commonly used in algorithms from simple to complex .

### 1.2 Big O notation

In terms of building a house , We can judge the quality of the steel frame structure by testing the ability of the house to resist wind and rain , For data structures and algorithms, we also have special ways to judge good and bad —— Big O notation （BigO）.

Big O The representation is used to represent the time complexity of the algorithm , Time complexity is used to determine the running time of a piece of code , Simply put, we can think that a unit of time has passed ,n The second operation is naturally n Time units . Here are some common time complexity ：

**$O(N)$**

Look at the following pseudo code ：

```
s = 0
for i in range(n):
s += 1
```

We focus on... In the code for loop , In the code , Every time you do a cycle , Inside the loop s+=1(s=s+1) All do an operation , loop n Time , The operation is carried out n Time , therefore , The time complexity of this code can be counted as $O(N)$.

**$O(N_{2})$**

Take a look at the following pseudo code ：

```
s = 0
for i in range(n):
for j in range(n):
s += 1
```

The same idea as above , When there is a double cycle , The number of operations we perform becomes $n∗n=n_{2}$, The time complexity of this code is naturally counted as $O(N_{2})$.

**$O(logN)$**

```
i = 1
while i < n:
i = i*2
```

Compared with the first two logN It seems more special , According to the code , When we use while Cycle through i To control the stop of the cycle , By giving n To calculate the number of cycles k：

$2_{k}=n$

$k=logN$(log With 2 Base number )

In this way, it is easy to see that the time complexity of this code is $O(logN)$.

** Comparison of time complexity **

### Video Explanation

HD video ：B standing ： Data Valley

Speed learning data structure - Big O notation （Python）