空间复杂度

本章将讨论计算问题在算法所需空间量方面的复杂度。

空间复杂度与时间复杂度有很多共同特征，并作为根据计算难度对问题进行分类的另一种方法。

什么是空间复杂度？

空间复杂度是一个函数，它描述了算法根据算法的输入量所占用的内存（空间）量。

我们经常谈论的是所需的**额外内存**，不包括存储输入本身所需的内存。同样，我们使用自然（但固定长度）单位来测量它。

我们可以使用字节，但更容易使用，例如，使用的整数个数，固定大小结构的个数等。

最终，我们得出的函数将与表示该单位所需的实际字节数无关。

有时会忽略空间复杂度，因为使用的空间很少和/或很明显，但是有时它变得和时间复杂度一样重要。

定义

设**M**为一个在所有输入上都停止的确定性**图灵机(TM)**。**M**的空间复杂度是函数$f \colon N \rightarrow N$，其中**f(n)**是**M**扫描任何长度为**M**的输入时使用的磁带单元格的最大数量。如果**M**的空间复杂度为**f(n)**，我们可以说**M**在空间**f(n)**内运行。

我们使用渐近符号来估计图灵机的空间复杂度。

设$f \colon N \rightarrow R^+$为一个函数。空间复杂度类可以定义如下：

SPACE = {L | L是由O(f(n))空间确定性TM决定的语言}

SPACE = {L | L是由O(f(n))空间非确定性TM决定的语言}

**PSPACE**是在确定性图灵机上可以用多项式空间解决的语言的集合。

换句话说，**PSPACE = U_k SPACE (n^k)**

Savitch定理

与空间复杂度相关的最早定理之一是Savitch定理。根据该定理，确定性机器可以使用少量空间来模拟非确定性机器。

对于时间复杂度，这种模拟似乎需要时间呈指数增长。对于空间复杂度，该定理表明，任何使用**f(n)**空间的非确定性图灵机都可以转换为使用**f²(n)**空间的确定性TM。

因此，Savitch定理指出，对于任何函数$f \colon N \rightarrow R^+$，其中$f(n) \geqslant n$

NSPACE(f(n)) ⊆ SPACE(f(n))

复杂度类之间的关系

下图描述了不同复杂度类之间的关系。

到目前为止，我们还没有在本教程中讨论P类和NP类。这些将在稍后讨论。