空间复杂度

阐述

空间复杂度可以归为空间复杂度类以描述一组类似的问题。

设 $M$ 是一个确定性的 Turing 机且对所有输入停机，则它的空间复杂度是函数 $f:\mathbb N\to\mathbb N$ ，其中 $f(n)$ 是输入长度为 $n$ 时 $M$ 使用的最大可能空间数。等价的表述为：

设 $M$ 是一个非确定性的 Turing 机且对所有输入停机，则它的空间复杂度是函数 $f:\mathbb N\to\mathbb N$ ，其中 $f(n)$ 是输入长度为 $n$ 时 $M$ 在所有分支上使用的最大可能空间数。