空間複雜度

在計算機科學中，一個算法或程序的空間複雜度定性地描述該算法或程序運行所需要的存儲空間大小。空間複雜度是相應計算問題（英語：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)}$。

參見

• 計算複雜性理論
• 時間複雜度
• 空間階層定理