##### 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|
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 ：