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 .
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) 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).
O ( N 2 ) O(N^2) O(N2)
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 n∗n=n2, The time complexity of this code is naturally counted as O ( N 2 ) O(N^2) O(N2).
O ( l o g N ) O(logN) 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 2k=n
k = l o g N k = logN 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) O(logN).
Comparison of time complexity
HD video ：B standing ： Data Valley
Speed learning data structure - Big O notation （Python）