空间复杂度

在计算机科学中，一个算法或程序的空间复杂度定性地描述该算法或程序运行所需要的存储空间大小。空间复杂度是相应计算问题（英语：Computational problem）的输入值的长度的函数，它表示一个算法完全执行所需要的存储空间大小。^[1]

和时间复杂度类似，空间复杂度通常也使用大O记号来渐进地表示，例如${\displaystyle O(n)}$、${\displaystyle O(n\log n)}$、${\displaystyle O(n^{\alpha })}$、${\displaystyle O(2^{n})}$等；其中n用来表示输入的长度，该值可以影响算法的空间复杂度。

就像时间复杂度的计算不考虑算法所使用的空间大小一样，空间复杂度也不考虑算法运行需要的时间长短。

空间复杂度类

复杂度类是渐进复杂度相同的一类问题的集合。与时间复杂度类DTIME(f(n))、NTIME(f(n))相似，空间复杂度类DSPACE(f(n))（英语：DSPACE）和NSPACE(f(n))分别表示可以被确定型和非确定型图灵机上使用${\displaystyle O(f(n))}$大小的空间可以决定的语言的集合。此外，与P、NP类似，如果令${\displaystyle f}$可以是任意多项式，就得到复杂度类PSPACE和NPSPACE。具体的定义为

${\displaystyle {\mathsf {PSPACE}}=\bigcup _{c\in \mathbb {Z} ^{+}}{\mathsf {DSPACE}}(n^{c})}$

和

${\displaystyle {\mathsf {NPSPACE}}=\bigcup _{c\in \mathbb {Z} ^{+}}{\mathsf {NSPACE}}(n^{c})}$

复杂度类之间的关系

根据空间层次定理，对于任意的空间可构函数${\displaystyle f(n)}$，总存在这样一个问题，它可以被一个图灵机使用${\displaystyle f(n)}$存储空间求解，但不能被任何图灵机用渐进少于${\displaystyle f(n)}$的存储空间求解。

以下复杂度类之间的包含关系是成立的^[2]：

${\displaystyle {\mathsf {DTIME}}\left(f\left(n\right)\right)\subseteq {\mathsf {DSPACE}}\left(f\left(n\right)\right)\subseteq {\mathsf {NSPACE}}\left(f\left(n\right)\right)\subseteq {\mathsf {DTIME}}\left(2^{O\left(f\left(n\right)\right)}\right)}$

另外，根据萨维奇定理，如果${\displaystyle f\in \Omega (\log(n))}$，则

${\displaystyle {\mathsf {NSPACE}}\left(f\left(n\right)\right)\subseteq {\mathsf {DSPACE}}\left(\left(f\left(n\right)\right)^{2}\right).}$

上边结果的一个直接推论是${\displaystyle {\mathsf {PSPACE}}={\mathsf {NPSPACE}}}$。这个推论意味着对于一个问题而言，非确定性可以为图灵机节省的存储空间是相当有限的。作为对比，在时间复杂度理论中，指数时间假说（英语：exponential time hypothesis）猜想，对于时间复杂度而言，非确定型和确定型空间复杂度类之间的差距可能是指数级的。

根据Immerman–Szelepcsényi定理（英语：Immerman–Szelepcsényi theorem），对于${\displaystyle f\in \Omega (\log(n))}$，${\displaystyle {\mathsf {NSPACE}}(f(n))}$在取反操作下闭合(即若一个语言${\displaystyle A\in {\mathsf {NSPACE}}(f(n))}$，则其反语言${\displaystyle A^{c}=\{x|x\not \in A\}}$也在${\displaystyle {\mathsf {NSPACE}}(f(n))}$中)。这可能意味着空间和时间复杂度类在复杂度类关系上的另一个差别，因为一般认为非确定空间复杂度类在取反操作下不闭合，例如有猜想NP≠co-NP。^[3][4]

对数空间复杂度类

对数空间复杂度类L（或写作LOGSPACE）是指确定性图灵机相对于输入${\displaystyle n}$仅需${\displaystyle O(\log n)}$存储空间就可以解决的问题的集合。考虑到一个最大取值为输入大小的计数器也需要${\displaystyle n}$个二进制位，也即${\displaystyle \log n}$的存储空间；LOGSPACE中的一个算法至多只能使用常数个计数器或其它复杂度相同的变量。

LOGSPACE以及其它次线性空间复杂度的算法在处理输入大到存不进计算机的随机存取存储器的问题时很有用。解决这类问题的算法包括数据流算法（英语：Streaming algorithm）；但次线性空间复杂度只考虑所需要的存储空间，而数据流算法同时还要考虑输入数据要怎样被送入算法中。 此复杂度类的算法在伪随机性和去随机化（英语：Derandomization）中也有应用，当前的相关开放问题包括L = RL是否成立。^[5][6]

与L对应的非确定性空间复杂度类是NL。

辅助空间复杂度

术语辅助空间是指除被输入数据占据的空间之外使用的存储空间。 因此，可以用以下方式来定义辅助空间复杂度：考虑一台拥有两条纸带的图灵机，其中一条“输入带”只能读不能写，另一条一般的纸带则可读可写。 则辅助空间复杂度只分析第二条纸带（即作业纸带，working tape）上的空间使用情况。 例如，对于平衡二叉树的深度优先搜索算法，若二叉树有${\displaystyle n}$个节点，则其辅助空间复杂度是${\displaystyle \Theta (\log n)}$。

参见

• 计算复杂性理论
• 时间复杂度
• 空间阶层定理

参考资料

1. Kuo, Way; Zuo, Ming J., Optimal Reliability Modeling: Principles and Applications, John Wiley & Sons: 62, 2003 [2021-08-11], ISBN 9780471275459, （原始内容存档于2021-08-11）
2. Arora, Sanjeev; Barak, Boaz, Computational Complexity : A Modern Approach (PDF) draft: 76, 2007 [2021-08-11], ISBN 9780511804090, （原始内容 (PDF)存档于2021-03-20）
3. Immerman, Neil, Nondeterministic space is closed under complementation (PDF), SIAM Journal on Computing, 1988, 17 (5): 935–938 [2021-08-11], MR 0961049, doi:10.1137/0217058, （原始内容 (PDF)存档于2012-02-07）
4. Szelepcsényi, Róbert, The method of forcing for nondeterministic automata, Bulletin of the EATCS, 1987, 33: 96–100
5. Nisan, Noam, RL ⊆ SC, Proceedings of the 24th ACM Symposium on Theory of computing (STOC '92), Victoria, British Columbia, Canada: 619–623, 1992, doi:10.1145/129712.129772.
6. Reingold, Omer; Trevisan, Luca; Vadhan, Salil, Pseudorandom walks on regular digraphs and the RL vs. L problem (PDF), STOC'06: Proceedings of the 38th Annual ACM Symposium on Theory of Computing, New York: ACM: 457–466, 2006 [2021-08-11], MR 2277171, doi:10.1145/1132516.1132583, （原始内容 (PDF)存档于2021-06-13）