Before reading this article, it is recommended that you first read [Data Structure]-Macro Understanding, and have a Macro understanding. We usetime complexity and space complexity to analyze the algorithm.
Time complexity
The amount of calculation included in the algorithm.
Big O notation, which means time complexity, regardless of the specific running time, only the algorithm is given A certain function of problem scale n.
The common order of time complexity has a constant order (the time complexity of the algorithm has nothing to do with the input scale n ), logarithmic order, linear order, polynomial order, exponential order. It is generally believed that an algorithm with an exponential order of time complexity is actually not computable, and an algorithm with an order lower than the square order is highly efficient.
An algorithm may have different time complexity for different input data with the same amount of input data. The worst time complexity and average time complexity are used to measure the performance of the algorithm.
Worst time complexity: For different input data with the same amount of input data, the maximum algorithm time consumption.
Average time complexity: for all different input data with the same amount of input data, the algorithm time consumption average of.
Space complexity
Space complexity is an algorithm in A measure of the amount of storage space that is temporarily occupied during operation.
The amount of storage space required by an algorithm during execution includes three parts:< /p>
The space occupied by the program code
Space occupied by input data
Space occupied by auxiliary variables
The space occupied by the input data is determined by the problem, not by the algorithm The difference varies.
The space occupied by the program code will not differ by orders of magnitude for different algorithms.
The space occupied by auxiliary variables is determined by the algorithm, and some occupations increase with the increase of the problem size n Some of the temporary space does not change with the scale of the problem.
When estimating the space complexity of the algorithm, only the space occupied by the auxiliary variable needs to be analyzed.
Summary
Master the time complexity and space complexity Analyze the focus. The calculation amount of the time complexity analysis algorithm, and the storage space occupied by the space complexity analysis algorithm when it is running, is mainly the analysis of auxiliary variables. Analyze the algorithm from these two different angles and design a high-efficiency algorithm.