How to calculate the space complexity of an algorithm?

Question

Algorithms

I understand algorithms and came across the analysis. How to correctly calculate the space complexity of an algorithm?
The dependence of the amount of memory occupied on the size of the input data, is it just the ratio of the total script memory consumed to the input data, or did I misunderstand?
If it is possible a usual example on fingers. Thank you.

Answer 1

Just as with time complexity - the number of operations. Just count the number of bytes used.
Roughly speaking, look at all variables created in the worst case (do not forget that local variables and function arguments are on the stack and are considered separately for each function call throughout the call depth).
You get some formula like 10*n+16*m+n*m/2 + 100500*log n. Then apply asymptotic analysis.
For example, the DFS algorithm. there is a graph with n vertices and m edges. Let be given in the form of incidence lists.
Then you have n lists that together contain m elements. Those. your input data is n*8+m(4+8) bytes. n pointers to the beginning of the list and m elements - each containing a value and a pointer. But you don’t have to count each byte thoroughly, you can just figure out n + m.
The algorithm itself still requires an array to mark passed vertices: +n to memory consumption.
The function requires some local variables and parameters. There are several of them and it does not depend on n or m. In recursion, the function can be called n times if you go all the way down. In total, these functions will eat n * C on the stack, where C is some kind of constant.
The total space complexity is n+m+n*C. Or O(n+m).
Local variables, if they are not arrays, can usually not be counted at all, because they are either factors before the number of function calls or just a constant extra, which is ignored by the asymptotics.