“This is the third day of my participation in the November Gwen Challenge. See details of the event: The last Gwen Challenge 2021”.

I originally wanted to call it “Introduction to Front-end Algorithms”, but I was afraid that I was not good enough to lead you to the bottom, so this series of articles was renamed to learn front-end algorithms with me

Yesterday liver to 11:30 😹, finally finished the time complexity, today continue to talk about space complexity.

Spatial complexity

In computer science, the spatial complexity of an algorithm or program qualitatively describes the amount of storage required by the algorithm or program to run. Spatial complexity is a function of the length of the input values corresponding to the computation problem, which represents the amount of storage required for an algorithm to fully execute.

Like time complexity, spatial complexity is usually expressed incrementally using the big O notation.

Compared with time complexity, spatial complexity is much simpler to analyze.

Because in general, the amount of memory that we need to execute our algorithm is the amount of memory that we need to apply for variables during the run. Further simplification allows you to count the number of simple variables and the number of properties of array variables \ object variables (possibly recursively). Although there is a difference in the amount of memory required to apply a numeric variable and a string variable, coefficients are ignored when deriving asymptotic space complexity, so all simple variables can be treated as occupying the same amount of memory.

Here are a few simple examples to help you understand:

const add = (a, b) => a + b; // 2 => O(1) const getArr = (n) => { const arr = []; let i = 0; while (i < n) { arr[i] = 1; } return arr; } // n + 2 => O(n) const convert = (arr) => arr.map(n => n * 2); // 2n + X => O(n)Copy the code

N refers to the problem size, not simply the number of entries. It could be the numeric value of the incoming parameter or the length of the array of incoming parameters. This value determines the number of cycles.

Similarly, the same rule applies to spatial complexity: if two algorithms are combined, they generally can only be added or multiplied. When they are added, the higher complexity is directly taken, and when multiplied, the complexity is multiplied.

Here’s an example:

  • O(1) + O(n) = O(n)
  • O(n) * O(log n) = O(n log n)

By the way, in the case of recursion, if it’s tail-call recursion, the overall space complexity is equal to that of the layer with the highest space complexity.

If there is no tail call, since the call stack is always retained, the space footprint will be only and!!! For example, if the complexity of each layer is O(n) and n times of recursion is required, the space complexity is increased to O(n ^ 2)!!

This is why some poorly written recursions can spill memory.

Auxiliary space complexity

The term auxiliary space refers to the storage space used in addition to the space occupied by input data. For example, for the depth-first search algorithm with balanced binary tree, if the binary tree has one node, the auxiliary space complexity is O(logn).

Time or space?

We can see from the content of today and yesterday that the complexity is evaluated separately. The time complexity is evaluated without considering the space complexity, and the space complexity is evaluated without considering the time complexity. Student: Are they proportional?

The answer is no, for the most part, time complexity is inversely proportional to space complexity. In other words, when the time complexity is low, the space complexity may be high. And vice versa.

Of course, some of the worst algorithms have a high time and space footprint, which is out of the discussion 🤣

You can’t have your cake and eat it too. Sometimes we have to choose between time and space. You’ve probably heard the term space for time, and it’s a trade-off.

In general, time is more important. Think about how often we want to be faster when we write programs. Scenarios that specifically require a smaller footprint are not very common (Chrome laughs). After all, time is money, right? Saving users time earns the company money.

conclusion

It is necessary to understand the time complexity and spatial complexity. Knowing how to calculate these two can be a good way to evaluate the algorithm written by yourself, and can also provide direction for optimization algorithms.

So much for these two, the next article will briefly cover the basics of data structures.

In this series of articles, you will learn about front-end algorithms step by step.

Series of all articles will be included in the column for you to view, you can follow me or bookmark this column.