Common algorithms (bubbling, insertion, selection, fast) and detailed explanation of binary tree

The same problem can be solved by different algorithms, and the quality of an algorithm will affect the efficiency of the algorithm and even the program. The purpose of algorithm analysis is to select the appropriate algorithm and improved algorithm.

In computer science, the time complexity of an algorithm is a function, which quantitatively describes the running time of the algorithm. This is a function of the length of the string representing the input value of the algorithm. The time complexity is usually expressed by the large o sign (order), excluding the lower order term and the first term coefficient of this function. In this way, the time complexity can be called asymptotic, which examines the situation when the size of the input value approaches infinity.

definition

In computer science, the time complexity of an algorithm is a function, which quantitatively describes the running time of the algorithm. This is a function of the length of the string representing the input value of the algorithm. The time complexity is usually expressed by large o sign, excluding the low-order term and first term coefficient of this function.

Algorithm complexity

The algorithm complexity is divided into time complexity and space complexity. Its function: time complexity refers to the computational workload required to execute the algorithm; Spatial complexity refers to the memory space required to execute this algorithm. (the complexity of the algorithm is reflected in the amount of resources required by the computer running the algorithm. The most important computer resources are time and space (i.e. register) resources, so the complexity is divided into time and space complexity).

Time complexity

　　1. In general, the number of times the basic operation of the algorithm is repeated is a function f (n) of module n. therefore, the time complexity of the algorithm is recorded as: t (n) = O (f (n))

Analysis: with the increase of module n, the growth rate of algorithm execution time is directly proportional to the growth rate of F (n). Therefore, the smaller f (n), the lower the time complexity of the algorithm and the higher the efficiency of the algorithm.

　　2. When calculating the time complexity, first find out the basic operation of the algorithm, then determine its execution times according to the corresponding statements, and then find the same magnitude of T (n) (its same magnitude is as follows: 1, log (2) n, N, N, log (2) n, the square of N, the third power of N, the nth power of 2, n!), After finding out, f (n) = this order of magnitude. If a constant C can be obtained by calculating the limit of T (n) / F (n), then the time complexity T (n) = O (f (n))

Example: algorithm:

Then there is t (n) = the square of N + the third power of N. according to the same order of magnitude in the brackets above, we can determine that the third power of n is the same order of magnitude of T (n)

Then there is f (n) = the third power of N, and then the constant C can be obtained by calculating the limit according to t (n) / F (n)

Then the time complexity of the algorithm: t (n) = O (n ^ 3) Note: n ^ 3 is the third power of n.

　　3. It is easy to understand and calculate in Pascal: look at how many for loops there are. If there are only one, the time complexity is O (n), and if there are two, it is O (logn). For example, binary search. If a for loop sets a binary, the time complexity is O (nlogn).

Common sorting

name

Let a [0]... A [n-1] be sorted, First, select any data (usually select the first number of the array) as the key data, and then put all smaller numbers in front of it and all larger numbers behind it. This process is called a quick sort. It is worth noting that quick sort is not stable, that is, the relative positions of multiple identical values may change at the end of the algorithm

Note: if there are multiple records with the same keyword in the file to be sorted, the relative order between these records with the same keyword remains unchanged after sorting, and the sorting method is stable; If the relative order of records with the same keyword changes, this sort method is said to be unstable. It should be noted that the stability of the sorting algorithm is for all input instances. That is, in all possible input instances, as long as one instance makes the algorithm not meet the stability requirements, the sorting algorithm is unstable.