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) 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]所创,转载请带上原文链接,感谢

  1. Day17 Java Foundation
  2. Day18 Java Foundation
  3. Linux installe JDK 1.8 et configure les variables d'environnement
  4. Tutoriel d'utilisation Maven super détaillé
  5. Spring boot reads project parameter configuration
  6. Docker installing rocketmq
  7. Java Zero Basic small white Beginner must make a summary of issues (recommended Collection) Chapitre 1
  8. Manuel pour vous apprendre à utiliser le développement Java pour générer des documents PDF en ligne
  9. 40 + comment les femmes s'habillent - elles pour montrer leur jeunesse?Un manteau et une jupe vous donnent un look haut de gamme tout au long de l'automne et de l'hiver
  10. Tutoriel d'installation Ubuntu 16.04 / Hadoop 3.1.3Configuration autonome / pseudo - distribuée
  11. L'apprentissage le plus détaillé de springboot à l'échelle du réseau - day01
  12. L'apprentissage le plus détaillé de springboot sur le Web - day02
  13. L'apprentissage le plus détaillé de springboot sur le Web - day03
  14. L'apprentissage le plus détaillé de springboot sur le Web - day04
  15. Tutoriel d'utilisation Maven super détaillé
  16. L'apprentissage le plus détaillé de springboot sur le Web - day05
  17. L'apprentissage le plus détaillé de springboot sur le Web - day06
  18. L'apprentissage le plus détaillé de springboot sur le Web - day07
  19. Introduction to JavaScript - write a photo album for your girlfriend
  20. [Hadoop 3. X] HDFS storage type and storage strategy (V) overview
  21. L'apprentissage le plus détaillé de springboot sur le Web - day08
  22. Introduction à la page Web de rabbitmq (3)
  23. No Converter found for return value of type: class java.util.arraylist Error Problem
  24. (16) , spring cloud stream message driven
  25. Que faut - il apprendre de l'architecture des microservices Spring Cloud?
  26. Résolution: erreur: Java: distribution cible invalide: 11problème d'erreur
  27. Springboot démarre en une minute et sort de l'enfer de la configuration SSM!
  28. Maven - un outil de gestion essentiel pour les grands projets d'usine, de l'introduction à la maîtrise![️ Collection recommandée]
  29. ️ Push to interview in Large Factory ᥧ - - Spring Boot Automatic Assembly Principle
  30. [️ springboot Template Engine] - thymeleaf
  31. Springboot - MVC Automatic configuration Principle
  32. Mybatis reverse engineering and the use of new version mybatisplus 3.4 reverse engineering
  33. Base de données MySQL - transactions et index
  34. Sécurité du printemps - [authentification, autorisation, déconnexion et contrôle des droits]
  35. Moteur de base de données InnoDB diffère de myisam
  36. Swagger - [springboot Integrated Swagger, configure Swagger, configure scan Interface, configure API Group]
  37. Cadre de sécurité Shiro - [QUICKstart, login Block, User Authentication, request Authorization]
  38. [Introduction à Java] installation de l'environnement de développement - Introduction à Java et construction de l'environnement
  39. 【 linux】 notes d'utilisation tmux
  40. MySQL + mybatis paging query - database series learning notes
  41. Usage relations and differences of count (1), count (*) and count (a field) in MySQL
  42. 2021 Ali Java advanced interview questions sharing, Java Architect interview materials
  43. Mybatis - dynamic SQL statement - if usage - MySQL series learning notes
  44. [go to Dachang series] deeply understand the use of where 1 = 1 in MySQL
  45. [secret room escape game theme ranking list] Based on spring MVC + Spring + mybatis
  46. Redis log: the killer mace of fearless downtime and rapid recovery
  47. 5 minutes to build redis cluster mode and sentinel mode with docker
  48. Java小白入门200例106之遍历ArrayList的几种方式
  49. Java小白入门200例105之Java ArrayList类
  50. Java小白入门200例104之JDK自带记录日志类logging
  51. Practice of high availability architecture of Tongcheng travel network based on rocketmq
  52. Chapter 9 - Linux learning will - file archiving and compression tar --- zip
  53. Java小白入門200例104之JDK自帶記錄日志類logging
  54. JDK avec journalisation de classe dans 200 cas 104
  55. Java ArrayList Class for Introduction to Java LITTLE WHITE 200 example 105
  56. Plusieurs façons de traverser ArrayList à partir de 200 exemples 106
  57. Provectus / Kafka UI: open source Apache Kafka's Web GUI Graphical interface management tool
  58. Design pattern series: Singleton pattern
  59. Java小白入門200例105之Java ArrayList類
  60. Understanding Java record types