This is the 22nd day of my participation in the More text Challenge. For details, see more text Challenge

  • Following on from the previous post, this one focuses on spatial complexity and relevance

What is spatial complexity

  • In simple terms, the time complexity is the time cost of implementing the algorithm, and the empty complexity is the space cost of implementing the algorithm
  • When running a program, we not only execute the various operational instructions, but also store some temporary intermediate data as needed, so that the subsequent instructions can more easily continue to execute.
  • Is an algorithm for temporary occupy storage space in the running process of measurement, an algorithm in computer memory storage space occupied space, including storage algorithm itself occupies arithmetic and input/output storage space and temporary occupy storage space occupied three parts, the algorithm of input and output data storage space is occupied by the problems to be resolved, Through the parameter table from the call function, it varies with the algorithm, the storage algorithm itself takes up storage space is proportional to the length of the algorithm writing. The amount of temporary space taken up by the algorithm during operation is determined by different algorithms.

Memory space is limited, and in the case of the same time complexity, the algorithm naturally takes up as little memory space as possible. How do you describe the amount of memory occupied by an algorithm? This brings us to another important metric of the algorithm, space complexity.

  • Similar to time complexity, spatial complexity is a measure of how much storage an algorithm temporarily occupies while it is running, and it also uses big O notation.
  • The calculation formula of the space occupied by the program is denoted as S(n)=O(f(n)), where n is the size of the problem and f(n) is a function of the storage space occupied by the algorithm.

Computation of space complexity

  • There are several common cases of spatial complexity
      1. Constant space
    • When the storage space size of the algorithm is fixed and has no direct relationship with the input size, the space complexity is denoated as O(1). For example, the following program:
 function fun1(){
   let num = 3;
 }
Copy the code
  1. Linear space
  • When the space allocated by the algorithm is a linear set (such as a set of numbers) and the size of the set is proportional to the input size N, the space complexity is denoted as O(n).
    • For example, the following program:
function fun2(n){
   var arr = new Array(n);
 }
Copy the code

3. Two-dimensional space

  • When the space allocated by the algorithm is a set of two-dimensional arrays, and the length and width of the set are proportional to the input size N, the space complexity is denoted as O(n2).
function fun3(n){
   var myarr = new Array(n); // Declare one dimension first
        for ( var i = 0; i < n; i++) { //
            myarr[i] = new Array(a);// Declare two dimensions again
            for ( var j = 0; j < n; j++) { / / 2
                myarr[i][j] = i + j; // Assign a value of I +j for each array element}}Copy the code
  1. Recursive space

  • Recursion is a special case. Although no variables or collections are explicitly declared in recursive code, the computer allocates a special block of memory to store the “method call stack” as the program executes.