Data structure and algorithm

One inch Hui 2021-01-21 20:57:57
data structure algorithm

##### The beginning of nonsense #####, Starting today , Maybe there will be another topic , Although I have studied data structure in school before , But as a new century 90 after , Or return what you have learned to the teacher , It's not difficult to borrow or return . In fact, I've learned it one after another , But I didn't make a good summary , Easy to forget , After all, as a semi monk, for a yard farmer , This needs to be studied , It's mainly because I didn't write much code , So it's basically not used , Even if you write the code , It doesn't seem to use much , Unless it's a small partner engaged in low-level development , However, learning this data structure and algorithm has many advantages , How exactly? , Please read on .

Why write an introduction to data structure and algorithm ? At least you should know why you want to learn this thing before you learn it , What can I do if I learn it well , How to learn . This article is just to better understand the data structure and algorithm from the global , Make a cognition for later learning , After a global cognition , Later learning will be better , It will be more systematic , More consolidation , The introduction of data structure and algorithm is also very important , Because we need to know the purpose of doing everything before we do it , What are the benefits , How to do , How to do better and more efficiently . Nothing else , It's very useful for the interview , see java Source code is also useful , The more you touch the underlying code , The more important the data structure and algorithm are . If you're just content with calling encapsulated code , That's it , There's no need to look down , If you want to have a good understanding of data structure and algorithm , Just look down , What is data structure and algorithm , What's the usage? , What's the charm .

One 、 Why learn data structures and algorithms ?

In fact, as long as you are a code programmer , People who write programs need to learn this , After all : Program = data structure + Algorithm + Programming language
Data structure and algorithm are the soul of program , The procedure of losing soul must be spiritless ( Overstaffed , Slow speed , Consume more resources )
Pack to force ! Force... Force !! Forced to blow water together !!! That's important , In fact, the following is the point :

  • Algorithms exercise their logical thinking ;
  • Improve code performance , Save space complexity and time complexity
  • Be able to understand the source code in the process of learning , We can know under what scenario to choose a more efficient algorithm
  • Job interview , Some even need to write code on site , A promotion and pay increase
  • First class programmers do algorithms , Second rate programmers do architecture , Third rate programmers do business ;
  • Many times, according to the company's scene, we can choose time for space or space for time , This increases the choice
  • Better understanding of applications and frameworks , Data structure algorithms are widely used in many well-known software and frameworks , such as mysql The index of is used b+ Trees ,redis Of list There's a jump watch at the bottom , Understanding these data structures can help us better understand the use of these software

All in all , Very important ! Very important !! It's really important !!!

Two 、 What are data structures and algorithms ?

2.1、 Data structure introduction

Data structure is to organize data , To make it easier to use data We're trying to solve the problem , You need to save the data , Then according to the data storage method to design algorithm implementation for processing , Different ways of data storage will lead to different algorithms for processing . We hope that the algorithm can solve the problem as quickly as possible , So we need to consider how to save the data , This is the data structure .

The data structure can be divided into : Linear structure and nonlinear structure .

Linear structure :

  • Linear structure is the most commonly used data structure , It is characterized by a one-to-one linear relationship between data elements
  • Linear structures have two different storage structures , That is, sequential storage structure ( Array ) And chain storage structure ( Linked list ). A linear table stored in sequence is called a sequential table , The storage elements in the sequence table are continuous
  • A linear list in chain storage is called a linked list , The storage elements in a linked list are not necessarily continuous , The address information of data elements and adjacent elements in element nodes
  • The common linear structures are : Array 、 queue 、 Lists and stacks .

Nonlinear structure :

Nonlinear structures include : Two dimensional array , Multidimensional arrays , Generalized table , Tree structure , The graph structure

The nonlinear structure can be divided into two parts : aggregate 、 A tree structure 、 Figure structure

  • Set structure : Apart from being of the same type , Nothing else .
  • A tree structure : There is a one to many relationship between elements . Common types are : Trees ( There are many exceptions : Binary tree 、 Balanced binary trees 、 Look for trees, etc )
  • Graphic structure : There is a many to many relationship between elements , In the graph structure, the number of leading nodes and subsequent nodes of each node can be arbitrary .

  A storage structure represents the representation of data in a computer :

  • Sequential storage structure : The sequential storage structure stores the data in the storage unit with continuous address .
  • Link storage structure : Chain storage structure stores data in any storage unit , Find the associated data element by saving the address .
  • Index storage structure ; While storing data , Index data of resume data , Convenient for data query ;
  • Hash storage structure : The hash function is used to calculate the key words and the storage address of the element

2.2、 Algorithm is introduced

Algorithm (Algorithm) It refers to the accurate and complete description of the solution , It's a series of clear instructions to solve problems , Algorithms represent a systematic approach to describe the policy mechanisms for solving problems . in other words , Be able to input certain specifications , Obtain the required output in a limited time . If an algorithm is defective , Or not suitable for a problem , Executing this algorithm will not solve this problem . Different algorithms may take different time 、 Space or efficiency to accomplish the same task . The advantages and disadvantages of an algorithm can be measured by the complexity of space and time .---- Algorithm Baidu Encyclopedia

Algorithm is the essence of computer processing information , Because the computer program is essentially an algorithm to tell the computer the exact steps to perform a given task . In a general way , When the algorithm is processing information , Will read data from the input device or data storage address , Write the result to the output device or a storage address for later call . Algorithm is an independent way to solve problems .

In fact, the algorithm is a way to solve the problem , So each algorithm has its own application scenarios , So in many cases, we need to choose the appropriate algorithm or design algorithm according to the actual situation . So understand the principle of the algorithm , At least you can choose the right algorithm when facing different scenes , Increase of efficiency , Saving resource , It's all time and money , So it's important to learn the algorithm well .

Five characteristics of the algorithm :

  • Fineness (Finiteness): The finiteness of the algorithm means that the algorithm must be able to terminate after a limited number of steps ;
  • Accuracy (Definiteness): Every step of the algorithm must be defined exactly ;
  • Input item (Input): An algorithm has 0 One or more inputs , To describe the initial situation of the operation object , So-called 0 An input is when the algorithm itself sets the initial conditions ;
  • Output item (Output): An algorithm has one or more outputs , To reflect the result of processing the input data . Algorithms without output make no sense ;
  • The feasibility of (Effectiveness): Any calculation step in the algorithm can be decomposed into basic executable operation steps , That is, each calculation step can be completed in a limited time ( It's also called validity )

Time complexity :
The time complexity of the algorithm refers to the amount of computation required to execute the algorithm . Generally speaking , The computer algorithm is the scale of the problem n Function of f(n), The time complexity of the algorithm is also recorded as .T(n)=Ο(f(n)), therefore , The scale of the problem n The bigger it is , The growth rate of algorithm execution time is related to f(n) There is a positive correlation between the growth rate of , It's called progressive time complexity (Asymptotic Time Complexity).

  • Time frequency The time that an algorithm takes to execute , It can't be calculated theoretically , You have to run tests on the computer to know . But we can't and don't need to test every algorithm , Just know which algorithm takes more time , Which algorithm will take less time . And the time spent by an algorithm is in direct proportion to the number of statements executed in the algorithm , Which algorithm has more statements executed , It takes more time . The number of statements executed in an algorithm is called statement frequency or time frequency . Write it down as T(n).
  • Time complexity In the time frequency mentioned just now ,n Called the scale of the problem , When n Constantly changing , Time frequency T(n) It's going to change . But sometimes we want to know how it changes . So , We introduce the concept of time complexity . In general , The number of times the basic operations are repeated in the algorithm is the scale of the problem n A function of , use T(n) Express , If there is an auxiliary function f(n), Properly n Approaching infinity ,T(n)/f(n) The limit value of is a constant not equal to zero , said f(n) yes T(n) Functions of the same order of magnitude of . Write it down as T(n)=O(f(n)), call O(f(n)) Is the incremental time complexity of the algorithm , Time complexity .
  • In a variety of different algorithms , If the number of statements executed in the algorithm is a constant , Then the time complexity is O(1), in addition , When time and frequency are different , Time complexity can be the same , Such as T(n)=n^2+3n+4 And T(n)=4n^2+2n+1 They have different frequencies , But the time complexity is the same , All for O(n^2). In increasing order of magnitude , The common time complexity is : Constant order O(1), Logarithmic order O(log2n), Linear order O(n), Linear logarithmic order O(nlog2n), Square order O(n^2), Cubic order O(n^3),..., k Order of second order O(n^k), Exponential order O(2^n). With the scale of the problem n The increase of , The time complexity is increasing , The less efficient the algorithm is . 

Common time complexity :

An example of execution function rank Informal terms
 12  O(1)   Constant order
 2n+3  O(n)   Linear order
 3n^2+2n+1  O(n^2)   Square order
 5log2n+20  O(logn)   Logarithmic order
 2n+3nlog2n+19  O(nlogn)  nlogn rank
 6n^3+2n^2+3n+4  O(n^3)   Cubic order
 2^n  O(2^n)   Exponential order

Common time complexity relationships , The time it takes to get to :O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)


Spatial complexity :

The space complexity of the algorithm refers to the memory space consumed by the algorithm . Its computation and representation are similar to time complexity , Generally, it is expressed by the asymptotic property of complexity . Compared with time complexity , The analysis of spatial complexity is much simpler .

The spatial complexity of the algorithm (Space Complexity)S(n) It is defined as the storage space consumed by the algorithm , It's also the scale of the problem n Function of . Asymptotic space complexity is often referred to as space complexity . Write it down as S(n)=O(f(n))

Spatial complexity (Space Complexity) It is a measure of the amount of storage space temporarily occupied by an algorithm during operation . The amount of memory occupied by an algorithm in computer memory , Including the memory occupied by the algorithm itself , The storage space occupied by the input and output data of the algorithm and the storage space temporarily occupied by the algorithm in the process of running . The storage space occupied by the input and output data of the algorithm is determined by the problem to be solved , It is passed by calling function through parameter list , It doesn't change with the algorithm . The storage space occupied by the storage algorithm itself is directly proportional to the length of algorithm writing , To compress the storage space in this area , You have to write a shorter algorithm . The storage space temporarily occupied by the algorithm varies with different algorithms , Some algorithms only need to occupy a small amount of temporary work units , And it doesn't change with the size of the problem , We call this algorithm “ In situ \" On going , It's a memory saving algorithm , Some algorithms need to occupy the number of temporary work units and the scale of problem solving n of , It follows n To increase with , When n large , Will take up more storage units .

Of course, the evaluation of the algorithm is not only the time of the algorithm Complexity and spatial complexity , For example, there is correctness , Readability , Key value property etc. , Understand the time complexity and space complexity , Just know what situation and scene can consider time for space , Or space for time , These are based on the actual situation , There is no best algorithm , Only algorithms that are more suitable for some scenarios .

Analysis methods commonly used in algorithms : Recurrence method 、 Recursive method 、 Exhaustive method 、 Greedy Algorithm 、 Divide and conquer method 、 Dynamic programming 、 Iterative method 、 Branch and bound method 、 backtracking .

Algorithm classification :

Algorithms can be roughly divided into basic algorithms 、 Algorithm of data structure 、 Number theory and algebraic algorithms 、 Algorithms for Computational Geometry 、 The algorithm of graph theory 、 Dynamic programming and numerical analysis 、 encryption algorithm 、 Sorting algorithm 、 Search algorithm 、 Randomization algorithm 、 parallel algorithm , Hermite deformation model , Random forest algorithm . Algorithms can be broadly divided into three categories :

  • Limited , Deterministic algorithms Such algorithms terminate in a limited period of time . They may take a long time to perform the assigned task , But it will still end in a certain period of time . The result of this kind of algorithm often depends on the input value .
  • Limited , Nondeterministic algorithms Such algorithms terminate in a limited time . However , For one ( Or some ) Given the value , The result of the algorithm is not unique or definite .
  • Infinite algorithms It's because there are no termination conditions defined , Or defined conditions cannot be satisfied by the input data without terminating the running algorithm . Usually , The infinite algorithm is due to the undetermined defined termination condition .

3、 ... and 、 How to learn data structures and algorithms ?

  1. Clear purpose , Why learn data structures and algorithms -- powered
  2. Clear direction , Understand what you want to learn about data structures and algorithms
  3. Hands on , Hands on , Hands on , Understand the principle , Code implementation , And the most important step is to summarize and share
  4. Understand the origin of each data structure and algorithm , characteristic , Advantages and disadvantages and use scenarios
  5. You can go and see some java The source code , Think about the implementation of other people's excellent code , Why do you write that , Is there a better plan ?
  6. Of course, resources are also important : You can listen to the class , There are a lot of online courses , Reading books 《 Introduction to algorithms 》《 The beauty of Mathematics 》 etc. , Network resources : Algorithm visualization website ( Chinese version )
  7. You can brush the topic moderately , It strengthens the memory
  8. Learn to ask questions , solve the problem , Record the problem , Implementing solutions

For example, some common data structures and algorithms :

  • 10 Data structures : Array 、 Linked list 、 Stack 、 queue 、 Hash table 、 Binary tree 、 Pile up 、 Jump watch 、 chart 、Trie Trees ;
  • 10 Algorithms : recursive 、 Sort 、 Two points search 、 Search for 、 The hash algorithm 、 Greedy Algorithm 、 Divide and conquer algorithm 、 Backtracking algorithm 、 Dynamic programming 、 String matching algorithm

Data structure and algorithm knowledge structure mind map ( Quote excellent blog posts , See reference article ):

Reference resources :

本文为[One inch Hui]所创,转载请带上原文链接,感谢

  1. 【计算机网络 12(1),尚学堂马士兵Java视频教程
  2. 【程序猿历程,史上最全的Java面试题集锦在这里
  3. 【程序猿历程(1),Javaweb视频教程百度云
  4. Notes on MySQL 45 lectures (1-7)
  5. [computer network 12 (1), Shang Xuetang Ma soldier java video tutorial
  6. The most complete collection of Java interview questions in history is here
  7. [process of program ape (1), JavaWeb video tutorial, baidu cloud
  8. Notes on MySQL 45 lectures (1-7)
  9. 精进 Spring Boot 03:Spring Boot 的配置文件和配置管理,以及用三种方式读取配置文件
  10. Refined spring boot 03: spring boot configuration files and configuration management, and reading configuration files in three ways
  11. 精进 Spring Boot 03:Spring Boot 的配置文件和配置管理,以及用三种方式读取配置文件
  12. Refined spring boot 03: spring boot configuration files and configuration management, and reading configuration files in three ways
  13. 【递归,Java传智播客笔记
  14. [recursion, Java intelligence podcast notes
  15. [adhere to painting for 386 days] the beginning of spring of 24 solar terms
  16. K8S系列第八篇(Service、EndPoints以及高可用kubeadm部署)
  17. K8s Series Part 8 (service, endpoints and high availability kubeadm deployment)
  18. 【重识 HTML (3),350道Java面试真题分享
  19. 【重识 HTML (2),Java并发编程必会的多线程你竟然还不会
  20. 【重识 HTML (1),二本Java小菜鸟4面字节跳动被秒成渣渣
  21. [re recognize HTML (3) and share 350 real Java interview questions
  22. [re recognize HTML (2). Multithreading is a must for Java Concurrent Programming. How dare you not
  23. [re recognize HTML (1), two Java rookies' 4-sided bytes beat and become slag in seconds
  24. 造轮子系列之RPC 1:如何从零开始开发RPC框架
  25. RPC 1: how to develop RPC framework from scratch
  26. 造轮子系列之RPC 1:如何从零开始开发RPC框架
  27. RPC 1: how to develop RPC framework from scratch
  28. 一次性捋清楚吧,对乱糟糟的,Spring事务扩展机制
  29. 一文彻底弄懂如何选择抽象类还是接口,连续四年百度Java岗必问面试题
  30. Redis常用命令
  31. 一双拖鞋引发的血案,狂神说Java系列笔记
  32. 一、mysql基础安装
  33. 一位程序员的独白:尽管我一生坎坷,Java框架面试基础
  34. Clear it all at once. For the messy, spring transaction extension mechanism
  35. A thorough understanding of how to choose abstract classes or interfaces, baidu Java post must ask interview questions for four consecutive years
  36. Redis common commands
  37. A pair of slippers triggered the murder, crazy God said java series notes
  38. 1、 MySQL basic installation
  39. Monologue of a programmer: despite my ups and downs in my life, Java framework is the foundation of interview
  40. 【大厂面试】三面三问Spring循环依赖,请一定要把这篇看完(建议收藏)
  41. 一线互联网企业中,springboot入门项目
  42. 一篇文带你入门SSM框架Spring开发,帮你快速拿Offer
  43. 【面试资料】Java全集、微服务、大数据、数据结构与算法、机器学习知识最全总结,283页pdf
  44. 【leetcode刷题】24.数组中重复的数字——Java版
  45. 【leetcode刷题】23.对称二叉树——Java版
  46. 【leetcode刷题】22.二叉树的中序遍历——Java版
  47. 【leetcode刷题】21.三数之和——Java版
  48. 【leetcode刷题】20.最长回文子串——Java版
  49. 【leetcode刷题】19.回文链表——Java版
  50. 【leetcode刷题】18.反转链表——Java版
  51. 【leetcode刷题】17.相交链表——Java&python版
  52. 【leetcode刷题】16.环形链表——Java版
  53. 【leetcode刷题】15.汉明距离——Java版
  54. 【leetcode刷题】14.找到所有数组中消失的数字——Java版
  55. 【leetcode刷题】13.比特位计数——Java版
  56. oracle控制用户权限命令
  57. 三年Java开发,继阿里,鲁班二期Java架构师
  58. Oracle必须要启动的服务
  59. 万字长文!深入剖析HashMap,Java基础笔试题大全带答案
  60. 一问Kafka就心慌?我却凭着这份,图灵学院vip课程百度云