查看“︁空间复杂度”︁的源代码

{{NoteTA
|G1=IT
|G2=Math
}}
在[[计算机科学]]中，一个[[算法]]或[[电脑程序|程序]]的'''空间复杂度'''定性地描述该算法或程序运行所需要的存储空间大小。空间复杂度是相应{{tsl|en|Computational problem|计算问题}}的[[算法#特征|输入值]]的长度的函数，它表示一个算法完全执行所需要的存储空间大小。<ref>{{citation|title=Optimal Reliability Modeling: Principles and Applications|first1=Way|last1=Kuo|first2=Ming J.|last2=Zuo|publisher=John Wiley & Sons|year=2003|isbn=9780471275459|url=https://books.google.com/books?id=vdZ4Bm-LnHMC&pg=PA62|page=62|accessdate=2021-08-11|archive-date=2021-08-11|archive-url=https://web.archive.org/web/20210811221315/https://books.google.com/books?id=vdZ4Bm-LnHMC&pg=PA62}}</ref>

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

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

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

:<math>\mathsf{PSPACE} = \bigcup_{c \in \Z^+} \mathsf{DSPACE}(n^c)</math>

和

:<math>\mathsf{NPSPACE} = \bigcup_{c \in \mathbb{Z}^+} \mathsf{NSPACE}(n^c)</math>

==复杂度类之间的关系==
根据[[空间层次定理]]，对于任意的[[可構函數#空間可構函數|空間可構函數]]<math>f(n)</math>，总存在这样一个问题，它可以被一个图灵机使用<math>f(n)</math>存储空间求解，但不能被任何图灵机用渐进少于<math>f(n)</math>的存储空间求解。

以下复杂度类之间的包含关系是成立的<ref>{{citation|title=Computational Complexity : A Modern Approach|edition=draft|year=2007|first1=Sanjeev|last1=Arora|first2=Boaz|last2=Barak|isbn=9780511804090|page=76|url=https://theory.cs.princeton.edu/complexity/book.pdf|accessdate=2021-08-11|archive-date=2021-03-20|archive-url=https://web.archive.org/web/20210320063140/https://theory.cs.princeton.edu/complexity/book.pdf}}</ref>：

:<math>\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)</math>

另外，根据[[萨维奇定理]]，如果<math>f\in\Omega(\log(n))</math>，则

:<math>\mathsf{NSPACE}\left(f\left(n\right)\right) \subseteq \mathsf{DSPACE}\left(\left(f\left(n\right)\right)^2\right).</math>

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

根据{{tsl|en|Immerman–Szelepcsényi theorem|Immerman–Szelepcsényi定理}}，对于<math>f\in\Omega(\log(n))</math>，<math>\mathsf{NSPACE}(f(n))</math>在{{tsl|en|Complement_(complexity)|取反}}操作下[[闭包_(数学)|闭合]](即若一个语言<math>A\in\mathsf{NSPACE}(f(n))</math>，则其反语言<math>A^c=\{x|x\not\in A\}</math>也在<math>\mathsf{NSPACE}(f(n))</math>中)。这可能意味着空间和时间复杂度类在复杂度类关系上的另一个差别，因为一般认为非确定空间复杂度类在取反操作下不闭合，例如有猜想NP≠[[co-NP]]。<ref>{{citation
 | last = Immerman
 | first = Neil
 | doi = 10.1137/0217058
 | issue = 5
 | journal = SIAM Journal on Computing
 | mr = 961049
 | pages = 935–938
 | title = Nondeterministic space is closed under complementation
 | url = http://www.cs.umass.edu/~immerman/pub/space.pdf
 | volume = 17
 | year = 1988
 | accessdate = 2021-08-11
 | archive-date = 2012-02-07
 | archive-url = https://web.archive.org/web/20120207091217/http://www.cs.umass.edu/~immerman/pub/space.pdf
 }}</ref><ref>{{citation
 | last = Szelepcsényi | first = Róbert 
 | journal = Bulletin of the EATCS
 | pages = 96–100
 | title = The method of forcing for nondeterministic automata
 | volume = 33
 | year = 1987}}</ref>

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

LOGSPACE以及其它次线性空间复杂度的算法在处理输入大到存不进计算机的[[随机存取存储器]]的问题时很有用。解决这类问题的算法包括{{tsl|en|Streaming algorithm|数据流算法}}；但次线性空间复杂度只考虑所需要的存储空间，而数据流算法同时还要考虑输入数据要怎样被送入算法中。
此复杂度类的算法在[[伪随机性]]和{{tsl|en|Derandomization|去随机化}}中也有应用，当前的相关开放问题包括[[L (复杂度)|L]] = [[RL (复杂度)|RL]]是否成立。<ref>{{citation
 | last = Nisan | first = Noam
 | contribution = RL ⊆ SC
 | doi = 10.1145/129712.129772
 | location = Victoria, British Columbia, Canada
 | pages = 619–623
 | title = Proceedings of the 24th ACM Symposium on Theory of computing (STOC '92)
 | year = 1992}}.</ref><ref>{{citation
 | last1 = Reingold
 | first1 = Omer
 | last2 = Trevisan
 | first2 = Luca
 | last3 = Vadhan
 | first3 = Salil
 | contribution = Pseudorandom walks on regular digraphs and the RL vs. L problem
 | contribution-url = http://people.seas.harvard.edu/~salil/research/regular.pdf
 | doi = 10.1145/1132516.1132583
 | mr = 2277171
 | pages = 457–466
 | publisher = ACM
 | location = New York
 | title = STOC'06: Proceedings of the 38th Annual ACM Symposium on Theory of Computing
 | year = 2006
 | accessdate = 2021-08-11
 | archive-date = 2021-06-13
 | archive-url = https://web.archive.org/web/20210613220404/http://people.seas.harvard.edu/~salil/research/regular.pdf
 }}</ref>

与L对应的非确定性空间复杂度类是[[NL (复杂度)|NL]]。

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

==参见==
* [[计算复杂性理论]]
* [[时间复杂度]]
* [[空间阶层定理]]

== 参考资料 ==
{{reflist|45em}}

{{复杂度类}}

[[Category:算法分析]]
[[Category:計算複雜性理論]]