The time complexity and space complexity of the algorithm

Algorithm complexity refers to the resources required to run the algorithm after it is written into an executable program. The resources include time resources and memory resources. Applications to Introduction to Mathematics and Computing.

Definition of algorithm time complexity: (Recommended learning: PHP video tutorial)

In progress During algorithm analysis, the total number of statement executions T(n) is a function of the problem size n, and then the change of T(n) with n is analyzed and the order of magnitude of T(n) is determined. The time complexity of the algorithm, that is, the time measurement of the algorithm, is recorded as: T(n) = O(f(n)). It means that as the problem size n increases, the growth rate of the algorithm execution time is the same as the growth rate of f(n), which is called the asymptotic time complexity of the algorithm, referred to as time complexity. where f(n) is a function of problem size n.

Use capital O() to reflect the time complexity of the algorithm, which we call Big O notation.

In various algorithms, if the number of statement executions in the algorithm is a constant, the time complexity is O(1). In addition, when the time frequency is different, the time complexity may be the same. For example, T(n)=n^2 3n 4 and T(n)=4n^2 2n 1 have different frequencies, but the time complexity is the same, both are O(n^2).

Arranged in increasing order of magnitude, common time complexity is:

Constant order O(1), logarithm order O(log2n) (logarithm of n with base 2, the same below) ), linear order O(n),

Linear logarithmic order O(nlog2n), square order O(n^2), cubic order O(n^3),...,

kth power order O(n^k), exponential order O(2^n). As the problem size n continues to increase, the above time complexity continues to increase, and the execution efficiency of the algorithm becomes lower.

Algorithm Space Complexity

Similar to time complexity, space complexity refers to the measurement of the storage space required when an algorithm is executed within a computer.

Recorded as:

S(n)=O(f(n))

The storage space required during the execution of the algorithm includes 3 Part:

The space occupied by the algorithm program;

The storage space occupied by the initial data input;

The additional space required during the execution of the algorithm.

In many practical problems, in order to reduce the storage space occupied by the algorithm, compression storage technology is usually used.

For more PHP related technical articles, please visit the PHP Graphic Tutorial column to learn

The above is the detailed content of The time complexity and space complexity of the algorithm. For more information, please follow other related articles on the PHP Chinese website!