# Data structure ｜ time complexity (with video explanation)

data structure time complexity video

### 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 ) 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) .

O ( N 2 ) 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 n*n=n^2 , The time complexity of this code is naturally counted as O ( N 2 ) O(N^2) .

O ( l o g N ) 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 2^k = n

k = l o g 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 ( l o g N ) O(logN) .

Comparison of time complexity ### Video Explanation

HD video ：B standing ： Data Valley

Speed learning data structure - Big O notation （Python）

https://javamana.com/2021/10/20211002150018495N.html