What is an algorithm
In mathematics, a formula or idea used to solve a class of problems. In computer: instructions for a series of programs used to solve specific arithmetic and logic problems.
Second, the measurement of the algorithm
1. Time complexity
It’s the time cost of executing the algorithm. 1.1 The absolute execution time of code cannot be estimated due to the environment and input size!! But we can calculate the number of times the basic operation of the code is executed T(n);
Where: O is the progressive time complexity of the algorithm, also known as the legendary time complexity. The principle of time complexity is deduced: ① If the operation time is constant, it is represented by 1; ② Only retain the highest term in the function; ③ If the highest order exists, the preceding coefficients are omitted.
Eg. T (n) = 3 n2 + 6 n + 5 T (n) = n ^ 2 + 3 + 5 6 n T (n) = 3 n2 + 6 n + 5 its time complexity is: T (n) = O (n2) T (n) = O (n ^ 2) T (n) = O (n2)
O(1) < O(log(n)) < O(n) < O(n^2)
1.3 Importance of Time Complexity As the size of the problem increases, the gap between good and bad algorithms becomes more obvious.
2. Space complexity
The space cost of performing the algorithm. 2.1 Calculation of common space complexity
| type | Spatial complexity | For example, |
|---|---|---|
| Constant space | O(1) | The storage space of the algorithm is fixed and has no direct relationship with the input size |
| Linear space | O(n) | When the space allocated by the algorithm is a linear set (such as an array) and the set size is proportional to the size n |
| A two-dimensional space | O(n^2) | When the space allocated by the algorithm is a two-dimensional array set, and the length and width of the set are proportional to the size n of the input |
| Recursive space | O(n) | The amount of memory required to perform a recursive operation is proportional to the depth of the recursion. (The space complexity of purely recursive operations is also linear.) |
3. Choice of time and space
Because the computing speed and space resources of the computer are limited, for example: a very rich person is not worried about how much money to eat every day, only the people without money will be careful every day. But in today’s world of skyrocketing CPU processing speed and increasing memory and hard disk space, most of the time, we want to sacrifice space for time, to improve the execution speed of programs.
What is a data structure
A data structure is a format for organizing, managing, and storing data in order to access and modify it more efficiently
