(Sort Algorithm)
1.1 the profile
Sorting algorithm is the process of arranging a set of data in a specified order.
1.2 classification
1.2.1 Internal sorting — key points
All the data that needs to be processed is loaded into internal memory for sorting
1.2.2 External Sorting
The amount of data is too large to be loaded into memory, and external storage (files, etc.) is needed to sort the data
1.2.3 Common sorting algorithms are classified as follows:
Second, time complexity of the algorithm
2.1 Two ways to measure the execution time of a program (algorithm)
(1) Post-statistical methods
This method is feasible, but there are two problems: first, in order to evaluate the performance of the designed algorithm, it is necessary to run the program; Second, the statistics of the time obtained depend on the hardware, software and other environmental factors of the computer. In this way, it is necessary to run in the same state of the same computer to compare the algorithm faster.
(2) The method of prior estimation
The time complexity of an algorithm is analyzed to determine which algorithm is better.
2.2 Time frequency
Time frequency: The time taken by an algorithm is directly proportional to the number of statements executed in the algorithm. The algorithm that has more statements executed takes more time. The number of statements executed in an algorithm is called statement frequency or time frequency. Notes for T (n).
2.2.1 Examples
For example, to calculate the sum of all numbers from 1 to 100, we designed two algorithms:
2.2.2 Ignore the constant term
Conclusion:
- 2n+20 and 2n as n gets larger, the execution curves approach infinity, and 20 can be ignored
- 3n+10 and 3n as n gets larger, the execution curves approach infinity, and 10 can be ignored
2.2.3 Ignore low-order items
Conclusion:
- 2n^2+3n+10 and 2n^2 as n gets bigger, the execution curve gets infinitely close, and you can ignore 3n+10
- N ^2+5n+20 and n^2 as n gets larger, the execution curve gets infinitely close, and you can ignore 5n+20
2.2.4 Ignore coefficient
Conclusion:
- As n gets bigger, 5n^2+7n and 3n^2+2n, they start repeating themselves, and eventually the ratio gets closer to 5/3.
- As n gets bigger, n^3+5n and 6n^3+4n, they gradually separate, and eventually the ratio is close to 1/6.
- The power of the expression represents the growth rate, and the coefficient can be temporarily ignored when calculating the time frequency.
2.3 Time Complexity
- In general, the number of repeated execution of the basic operation statement in the algorithm is a function of the problem size N, which is expressed by T(n). If there is some auxiliary function F (n) such that the limit value of T(n)/f(n) is a constant not equal to zero when n approaches infinity, then F (n) is said to be a function of the same order of magnitude as T(n). Denoted as T(n)=O(f(n)), O(f(n)) is called the asymptotic time complexity of the algorithm, or time complexity for short.
- T(n) is different, but the time complexity might be the same. Such as: T (n) = n squared + 7 n + 6 and T (n) = 3 + 2 n + 2 n squared them T (n) is different, but same time complexity, is O (n squared).
- Method for calculating time complexity:
- Replace all addition constants in running time with constant 1. T (n) = 3 n squared + 7 n + 6 = > T (n) = 3 n squared + 7 n + 1
- In the modified run times function, only the highest order items are retained. T (n) = T (n) = 3 n squared + 7 n + 1 = > T (n) = 3 n squared
- Subtract the coefficient of the highest order term. T (n) = 3 n squared = > T (n) = n squared = > O (n squared)
2.4 Common time complexity
- Constant order O (1)
- The logarithmic order O (log2n)
- Linear order O (n)
- Linear log order O(nlog2n)
- Square order O (n ^ 2)
- Cubic order O (n ^ 3)
- Order N to the k.
- The index order O (2 ^ n)
2.4.1 Diagram of common time complexity
Description:
- The time complexity of common algorithms increases in descending order: O (1) < O (log2N) < O (N) < O (nLOG2N) < O (n2) < O (N3) < O (NK) < O (2N). As the problem size n increases, the time complexity increases and the algorithm execution efficiency decreases
- As can be seen from the figure, we should avoid using exponential algorithms whenever possible
2.4.2 Details
- Constant order O (1)
- Linear log order O(nlog2n)
Note: refer to the above O(n²) to understand, O(n³) is equivalent to three layers of n cycle, other similar
2.5 Average and Worst Time Complexity
- Average time complexity refers to the running time of the algorithm when all possible input instances occur with equal probability.
- The worst-case time complexity is called the worst-case time complexity. Generally, the time complexity discussed is the worst case time complexity. The reason for this is that the worst-case time complexity is the limit on the running time of the algorithm on any input instance, which guarantees that the algorithm will not run longer than the worst-case time.
- Whether the average time complexity is consistent with the worst time complexity depends on the algorithm (see figure :).
Third, the spatial complexity of the algorithm
- Similar to the discussion of time complexity, the spatial complexity of an algorithm (SpaceComplexity) is defined as the storage space consumed by the algorithm, which is also a function of problem size N.
- SpaceComplexity is a measure of the amount of storage space temporarily occupied by an algorithm while it is running. The number of temporary units of work that some algorithms need to occupy is related to the problem size N, which increases with the increase of N. When N is large, more storage units will be occupied, such as quicksort and merge sort algorithms, such as radix sort
- When we do algorithm analysis, we mainly discuss time complexity. From the perspective of user experience, the speed of program execution is more important. Some caching products (Redis,memcache) and algorithms (radix sort) essentially trade space for time.
- The spatial complexity of each algorithm, as shown in the previous section.