Analysis skills of time complexity and space complexity

One 、 Algorithm efficiency measurement

How to measure the execution efficiency of an algorithm / Time ？ You can use the timing function of the computer , To measure the efficiency of algorithm execution . This method is also called After the fact statistics .

Post hoc statistical method has great limitations ：

1. The test results depend on the environment ： Different processors 、 Different operating systems will affect the test results ; Even the same physical machine ,Cpu The test results may also be different if the utilization rate is different .
2. The test results are affected by the size of the data ： The size of the data scale , It directly determines the running time of the program .

Usually analyze the efficiency of an algorithm , There is no need to calculate the specific execution time , It is a rough estimate of the time efficiency of the algorithm .

That is, the time complexity analysis method .

Two 、 Time complexity

T（n） = O（f（n））

T（n） Represents the execution time of the algorithm ,n Represents data size . With the scale n The increase of , The growth rate of algorithm execution time and f（n） The same growth rate . It is called the progressive time complexity of the algorithm , Time complexity .

Big O Represents the execution time of the algorithm T（n） And f（n） In direct proportion to .

How to understand time complexity

1. It indicates that the execution time of code increases with the size of data , Not a specific execution time .
2. Usually it just represents the data scale n Very often the execution efficiency

How to calculate time complexity

1. Ignore constant 、 The low order 、 coefficient , Keep only the highest order .
2. The total time complexity is equal to the time complexity of the code with the largest magnitude .
3. The complexity of nested code is equal to the product of the complexity of inner and outer nested code .

Several common time complexity

1. O（1） Constant level ： Various operations on the hash table
2. O（logn） Logarithmic order ： Two points search 、 Adjust the meter
3. O（n） linear ： Array 、 Traversal of the list
4. O（nlogn） Quick sort 、 Merge sort
5. O（n^2） Bubbling 、 Insert 、 Selection sort
6. O（2^n） Exponential level ： Backtracking exhaustive algorithm , For example, the eight queens problem
7. O（n！）： Perfect permutation

best 、 The worst 、 Average time complexity

for example ： In an array , Find a value equal to X The data of . We need to traverse arrays , Each element in turn equas seek X.

1、 The time complexity of the best case Namely O（1）.（ Minimum response time of the interface ）

2、 Worst case time complexity O（n）.（ The maximum response time of the interface ）

3、 Average time complexity ： O（n）.（ Average interface response time ）

Most of the time , Average time complexity , Is the time complexity of the worst case .

4、 Average time complexity ： Is a special average time complexity . Common data structures that support dynamic capacity expansion .

A set of continuous operations on a data structure , Most of the time complexity is very low , Only in some cases, the time complexity is high , And there is a coherent sequential relationship between these operations .

Apportionment analysis ： This is the time , We can analyze this group of operations together , See if you can make the operation time-consuming with high time complexity , Spread it out to other operations with low time complexity .

In the case of being able to apply the analysis of average time complexity , The average time complexity is equal to the best case time complexity .

3、 ... and 、 Spatial complexity

Spatial complexity , It is the storage space occupied by the running process of the measurement algorithm , Usually use S（n） Express ,n The scale of the problem .

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

Common spatial complexity ：O（1）、O（n）

1. Spatial complexity O(1)

In the code m、n The allocated space is constant , Write it down as O（1）

int m = 1;
int n = 2;

2. Spatial complexity O(n)
   The code uses array Array save variables , With n The increase of , The memory occupied by the array also increases . Write it down as O（n）

int[] array = new int[n]
for(i=0; i<n; ++i)
{
   array[i] = i;
}