Explanation of time complexity and space complexity

Preface

   If you find it useful , Remember to give Bloggers like it , Comment on , Collect one button and three links , Writing is not easy ^ _ ^.
   And I heard that People who like it don't have bad luck every day , If you're really whoring for nothing , Then welcome to come often !!!

---

Explanation of time complexity and space complexity

01 Time complexity

01::01 summary

The calculation of time complexity describes the running time of the algorithm , That is, the trend of time growth , The total number of executions of a piece of code is T(n) Express .

T(n)- It represents how many statements are executed ;
O(n)- Simplified estimate ( Time complexity );

---

01::02 Calculation

01::02::01 Example :

public int test(int n){
    
   for(int i=0;i<n;i++){
    
     printf(i);
   }
   return 0;
}

among :

int i=0   --->  perform 1 Time 
i<n       --->  perform n+1 Time 
i++       --->  perform n Time 
printf(i) --->  perform n Time 
return 0  --->  perform 1 Time 

So call once test The total number of executions of the method is :T(n) = 3n + 3;

01::02::02 T(n) How to get O(n)?

1、T(n) = constant ;
answer :
1) If T(n) If the number of executions of is constant , The time complexity can be directly estimated as 【1】;
2) namely O(1);
2、T(n) = constant *n + constant ;
answer :
1) Remove the following constants , Because with n The increase of , The front is getting bigger , The latter value is constant , Equivalent to the constant part does not exist , Omit directly , obtain 【 constant n】;
2) The constant can be directly estimated as 1, So its time complexity is
【n】------------------> namely O(n);
3、T(n) = 5n^3 + 9090*n^2 +78;
answer :
1) For polynomials , Just keep n The highest power of , Because with n The increase of , Other content can never match its maximum number , obtain
【5n^3】;
2) The constant can be directly estimated as 1, So its time complexity is
【n^3】------------------> namely O(n ^3);

---

01::03 summary

The expression of time complexity is if T(n) Is a constant , So time complexity is O(1),
Otherwise keep T(n) And remove the coefficient of the highest order .

Example :

 When T(n) = n + (n-2) + (n-1) + ……+2 + 1 when ,O(n) How much ?

Explain :
T(n) = n + (n-2) + (n-1) + ……+2 + 1
= n*(n+1)/2
= n^2/2 + n/2
= O(n^2)

---

02 Spatial complexity

02::01 summary :

Space complexity description The trend of memory space growth .

02::02 Common space complexity ,O(1)、O(n)、O(n^2)

example :O(1):

int i = 0;
ing j = 0;
i++;
j++;

This code requires a constant amount of space ,i,j At large , It will not affect the space allocation of memory , So it is O(1).

example :O(n):

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

The factors that this code affects spatial memory depend on newArray The length of , With newArray The higher the length , The more complicated the space is .

example :O(n^2):
matrix :n That's ok 、n Column , The growth trend of memory space is n*n = n^2;