编程知识 cdmana.com

Data structure | time complexity (with video explanation)

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) 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 nn=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
 Insert picture description here

Video Explanation

HD video :B standing : Data Valley

Speed learning data structure - Big O notation (Python)

版权声明
本文为[The second brother is not like a programmer]所创,转载请带上原文链接,感谢
https://cdmana.com/2021/10/20211002150018495N.html

Scroll to Top