Space complexity

The space complexity of a problem is understood as the (minimal) storage space requirement of an algorithm to solve this problem, depending on the length of the input. So it is not the memory requirement of a specific program on a particular computer that is of interest , but rather how the memory requirement grows when more data has to be processed. For example, the space complexity answers the question of whether the required memory doubles or squares with twice the amount of input data (see also scalability ). It is therefore also known as storage complexity.

notation

The space complexity is always given in relation to a machine model . As a rule, the reference model is the Turing machine . The following notations apply:

• With all the problems are referred to by a deterministic may be decided Turing machine on input of length at most memory cells has used for the calculation. ${\displaystyle {\text{DSPACE}}(f)}$ ${\displaystyle n}$ ${\displaystyle f(n)}$
• With designates all the problems of a non-deterministic Turing machine can be decided that at an input of length at most has used memory cells for the calculation. ${\displaystyle {\text{NSPACE}}(f)}$ ${\displaystyle n}$ ${\displaystyle f(n)}$

From these classes, u. a. form the following space complexity classes:

• ${\displaystyle {\text{L}}:=\bigcup _{f\in O(\log(n))}{{\text{DSPACE}}(f)}}$
• ${\displaystyle {\text{NL}}:=\bigcup _{f\in O(\log(n))}{{\text{NSPACE}}(f)}}$
• ${\displaystyle {\text{PSPACE}}:=\bigcup _{f\in O(n^{k}),k\in \mathbb {N} }{{\text{DSPACE}}(f)}}$
• ${\displaystyle {\text{NPSPACE}}:=\bigcup _{f\in O(n^{k}),k\in \mathbb {N} }{{\text{NSPACE}}(f)}}$

There are also other space complexity classes that relate to exponential or even over-exponential storage space requirements.

Relationships

It is known as a real subset relation between space complexity classes of deterministic Turing machines . ${\displaystyle {\text{L}}\subsetneq {\text{PSPACE}}}$

The complexity classes of time complexity are related to those of space complexity as follows:

${\displaystyle {\text{L}}\subseteq {\text{NL}}\subseteq {\text{P}}\subseteq {\text{NP}}\subseteq {\text{PSPACE}}={\text{NPSPACE}}}$

Others

In complexity theory , the complexity of space is an important measure of the “difficulty” (or complexity ) of problems in addition to the time complexity . The time complexity of an algorithm can never be less than its space complexity, since one computation step is required for each writing of a memory cell.

Formally, problems are divided into complexity classes according to their space complexity or time complexity .

See also

• Time complexity
• Complexity (computer science)
• Efficiency
• DSPACE