Time complexity and space complexity

1. Time complexity

1.1 The concept of time complexity

• Time complexity is used to roughly describe Algorithm run time and Algorithm processing problem scale A measure of the relationship between

1.2 The time complexity is big O Notation

• T(n) = O(f(n))
• In this formula O Express The total execution time of the code T(n) and Its The total number of execution f(n) In direct proportion to . Call it big O Notation .

1.3 Common time complexity

name	Express
Constant order	O(1)
Logarithmic order	O(logn)
Linear order	O(n)
Linear logarithmic order	O(nlogn)
Square order	O(n^2)
Exponential order	O(2^n)
Factorial stage	O(n!))

1.4 Rules for ignoring time complexity

• After the time-consuming formula of an algorithm is calculated , Follow these steps “ Ignore standard ”
  • 1. Ignore the constant term in the formula
  • 2. Ignore the lower power term in the formula , Only the highest power term in the formula is retained
  • 3. Ignore the constant coefficient of the highest power term in the formula
  • 4. If all terms in a formula are constant terms , Then the time complexity of this algorithm is uniformly expressed as O(1)

1.5 Example analysis of time complexity

• example 1： Algorithm 1 The time-consuming formula of the operation process of is 2n^2 + 5n + 6 , The time complexity of this algorithm is O(n)
  • Ignore that the constant term in the formula becomes 2n^2 + 5n , Ignore the lower power term in the formula and become 2n^2, Ignore the constant coefficient of the highest power term in the formula Turn into n^2
• example 2： Algorithm 2 The time-consuming formula of the operation process of is nlogn + 5n + 2, The time complexity of this algorithm is O(nlogn)
  • nlogn + 5n + 2 It's written in n*(logn+5) +2, Ignore the constant term and directly become nlogn
• example 3： Algorithm 3 The time-consuming formula of the operation process of is 2n + 7, Then the time complexity of this algorithm O(n)
• example 4： Algorithm 4 The time-consuming formula of the original acid process is 1 + 1 +1 , The time complexity of this algorithm is O(1)

1.6 Comparison diagram of time complexity

• Y Axis ：T(n) ~ Algorithm execution times
• X Axis ：n ~ Problem input scale
  

1.7 Comparison of common time complexity in sorting algorithm

• In the sorting algorithm , The most common time complexity is O(n^2),O(nlogn),O(n) , among logn Said to 2 Bottom n The logarithmic

• Aforementioned 3 The size relationship between the time complexity is
  O(n^2) > O(nlogn) > O(n)

• in other words The time complexity is O(n^2) Sorting algorithm is the slowest ;
  The time complexity is O(n) Sorting algorithm runs fastest ;

1.8 Analyze the time complexity in the code

 for(int i=1;i<=n;i++) {
    
   x++;
 }

 O(1 + 3N) = O(N) N Close to infinity , that 1 and 3 It doesn't make sense , So the algorithm is simplified to O(N);

-------------------------------------------------------
  for(int i =1;i<=n;i++){
    
      for(int j =1;j<=n;j++){
    
          x++;
      }
  }   
  
  Suppose a cycle counts once ,n Layer nested n layer ,   Time complexity   that  = O(n*n)
-------------------------------------------------------
    int i=1
    while(i<n){
    
        i = i *2;
    }

    analysis  2^k = n?
        k = logn
        O(logn)
-------------------------------------------------------
     for(int i=0;i<=n;i++){
     
         int x = 1;
         while(x < n){
    
           x = x*2
         }      
     }
     
 There's a layer nested outside n The cycle of time   Then the time complexity becomes  O(nlogN)

2. Spatial complexity

2.1 The concept of spatial complexity

• It is a measure of the memory space occupied by an algorithm during its operation , Remember to do S(n)=O(f(n)).
• Spatial complexity （Space Complexity） Write it down as S(n)： Still use big O To express .
  Take advantage of the spatial complexity of the program , You can have a pre estimate of how much memory a program needs to run .

2.2 Common space complexity in sorting algorithm

• The common space complexity in sorting algorithm is 3 Kind of ：O(1), O(n), O(logn)
• O(n) > O(logn) > O(1)
• The more complicated the space is , It means that the algorithm needs to consume more additional space in the running process , in other words O(1) Is the smallest spatial complexity .

2.3 Example analysis of spatial complexity

• O(1) Spatial complexity
  • With n The increase of , The amount of memory space that needs to be opened up does not follow n Change by change .
  • That is, the space complexity of this algorithm is a constant , So it means O(1).

public static void test1(int n){
    
    int j = 0;
    for (int i = 0; i < n; i++) {
    
        j++;
    }
}    

• O(n) Spatial complexity
  • When consuming space and input parameters n Keep linear growth , This space complexity is O(n).
  • newArr The array length is n, Although there is one for loop , But there is no new space , Therefore, the space complexity of this code mainly depends on the first line , With n The increase of , The size of the opened memory increases linearly , namely O(n).

public static int[] testN(int n){
    
    int[] newArr = new int[n];
    for(int i=0;i<n;i++){
    
        newArr[i] = i;
    }
    return newArr;
}

• O(n^2) Spatial complexity
  • The input values n, The space occupied by the two-dimensional array is n*n

public  static   int[][]  testN2(int n){
    
   int[][] twoArr = new int[n][n];//  matrix 
    for (int i = 0; i < n; i++) {
     //  That's ok 
        for (int j = 0; j < n; j++) {
    //  Column 
            twoArr[i][j] = j;
        }
    }
    return twoArr;
}

• O(logn) Spatial complexity

 public static int[] testSpaceLogN(int n){
    
        int cap = 0;
        int rs = 1;
        while ((rs = rs*2)<n){
    
            cap++;
        }
        int[] arr = new int[cap];
        for (int i = 0; i < cap; i++) {
    
            arr[i] = i + 1;
        }
        return arr;
    }