One , Relevant

Time complexity ： Time taken to execute the current algorithm , Remember to do that T(n) = O(f(n))

Spatial complexity ： A measure of the amount of storage space temporarily occupied by an algorithm during operation , Remember to do S(n)=O(f(n))

summary ： Time complexity refers to the number of statement executions , Space complexity refers to the storage space occupied by the algorithm

Two , Time complexity

1. computing method

* Constant used 1 Replace all addition constants in runtime
* In the modified run times function , Keep only the highest order items
* Coefficient of removing the highest order term
2. Common complexity

Low to high complexity examples

O(1)： Constant order
public void Constant(int n){ int i = n+1;// Only one calculation is required , Time complexity and n Irrelevant
System.out.println(i); }
O(logn)： Logarithmic order
public static void logarithm(int n){ for (int i = 1;i < n;i = 2*i){
System.out.println(i); } }
In the above method , Set execution times to x, The last execution is with a remainder of m, Then there are ：x^2  +  m = n, Constant terms are not considered in the calculation of time complexity , So about T(n) Yes ：x^2
= n, that x=log2n, That is to say, at this time T(n)=log2n

O(n)： Linear order
public static void linear(int n){// Linear order for (int i = 0;i<n;i++){// The number of program execution times and n Relationship
System.out.println(i); } }
O(n^2)： Square order
public static void square(int n){// Print from 1*1 reach n*n Multiplication table for (int i = 1;i<n+1;i++){
for (int m = 1;m<n+1;m++){ System.out.print(i+"*"+m+"="+i*m+" "); }
System.out.println(); } }
The square upgrade has k Order of second order

O(2^n)： Exponential order （m It's a constant ）
public static long index(int n){ if (n <= 1){ return 1; }else { return
index(n-1)+index(n-2); } }
As can be seen from the program ,T(0)=T(1)=1, meanwhile T(n) = T(n - 1) + T(n - 2) + 1, There 1 It's one of the addition operations . Obviously
T(n) = T(n - 1) + T(n - 2)  It's a Fibonacci series , It can be proved by inductive proof , When n >= 1 Time T(n) < (5/3)^n, At the same time
n > 4 Time T(n) >= (3/2)^n. So the time complexity of this method can be expressed as O((5/3)^n), After simplification O(2^n).

3. Worst time complexity and average time complexity

The worst-case time complexity is called the worst-case time complexity . Generally not specified , The time complexity discussed is the worst case time complexity .

Average time complexity refers to the case that all possible input instances occur with equal probability , Expected running time of algorithm . Let the probability of each situation be pi, The average time complexity is sum(pi*f(n))

Three , Spatial complexity

1. Relevant

In general, space complexity is not considered , Spatial complexity does not mean the space occupied by all data , But the size of the secondary space used , For example, the operation of two matrices , An intermediate matrix is set in the middle to save some data , These spaces are called space complexity . The calculation of space complexity is very troublesome , The general simple algorithm space complexity is O(1).

2. Common space complexity

O(1)
public static void constant(int n){// Constant order int i = n+1; System.out.println(i); }
whether n Why value? , The temporary space required for execution does not follow a variable n The size of , That is to say, the space complexity of this algorithm is a constant , Can be expressed as O(1)

O(n)
public static void linear(int n){// Linear order int[] m = new int[n]; }
Simple to understand , In this method , Space needed and n It's linear

Four , summary

For a given algorithm , We have to do it.
Two analyses . The first is to prove the correctness of the algorithm mathematically , This step mainly uses the method of formal proof and related reasoning mode , Such as loop invariant , Mathematical induction, etc . On the basis of proving that the algorithm is correct , The second part is to analyze the time complexity of the algorithm . The time complexity of the algorithm reflects the magnitude of the increase of program execution time with the increase of input scale , To a great extent, it can well reflect the advantages and disadvantages of the algorithm . therefore , As a programmer , It is necessary to master the basic algorithm time complexity analysis method .

Technology
Daily Recommendation
views 26
views 2