设计和分析空间复杂性

---

在本章中，我们将讨论计算问题的复杂性与算法所需空间量的关系。

空间复杂度具有时间复杂度的许多特征，并且可以作为根据计算难度对问题进行分类的进一步方法。

什么是空间复杂度？

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

我们经常谈论需要额外的内存，而不是计算存储输入本身所需的内存。同样，我们使用自然（但固定长度）单位来衡量这一点。

我们可以使用字节，但使用起来更容易，比如使用的整数数量、固定大小结构的数量等。

最后，我们提出的函数将独立于表示该单元所需的实际字节数。

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

定义

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

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

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

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

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

PSPACE是在确定性图灵机上的多项式空间中可判定的一类语言。

换句话说，PSPACE = U _k SPACE (n ^k )

萨维奇定理

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

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

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

NSPACE(f(n)) ⊆ 空间(f(n))

复杂性类别之间的关系

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

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