##### 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)=Ｏ(f(n)), call Ｏ(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 ？

- Clear purpose , Why learn data structures and algorithms -- powered
- Clear direction , Understand what you want to learn about data structures and algorithms
- Hands on , Hands on , Hands on , Understand the principle , Code implementation , And the most important step is to summarize and share
- Understand the origin of each data structure and algorithm , characteristic , Advantages and disadvantages and use scenarios
- 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 ？
- 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 ）
- You can brush the topic moderately , It strengthens the memory
- 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 ：**

https://www.cnblogs.com/54chensongxia/p/11448695.html

https://www.cnblogs.com/chjxbt/p/10967968.html

https://baike.baidu.com/item/%E7%AE%97%E6%B3%95/209025

https://www.cnblogs.com/songQQ/archive/2009/10/20/1587122.html