空間複雜度

在電腦科學中，一個演算法或程式的空間複雜度定性地描述該演算法或程式執行所需要的儲存空間大小。空間複雜度是相應計算問題的輸入值的長度的函數，它表示一個演算法完全執行所需要的儲存空間大小。

和時間複雜度類似，空間複雜度通常也使用大O記號來漸進地表示，例如$O(n)$、$O(n\log n)$、$O(n^{\alpha })$、$O(2^{n})$等；其中n用來表示輸入的長度，該值可以影響演算法的空間複雜度。

就像時間複雜度的計算不考慮演算法所使用的空間大小一樣，空間複雜度也不考慮演算法執行需要的時間長短。

空間複雜度類別

複雜度類別是漸進複雜度相同的一類問題的集合。與時間複雜度類別DTIME(f(n))、NTIME(f(n))相似，空間複雜度類別DSPACE(f(n))和NSPACE(f(n))分別表示可以被確定型和非確定型圖靈機上使用$O(f(n))$大小的空間可以決定的語言的集合。此外，與P、NP類似，如果令$f$可以是任意多項式，就得到複雜度類別PSPACE和NPSPACE。具體的定義為

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

和

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

複雜度類別之間的關係

根據空間層次定理，對於任意的空間可構函數$f(n)$，總存在這樣一個問題，它可以被一個圖靈機使用$f(n)$儲存空間求解，但不能被任何圖靈機用漸進少於$f(n)$的儲存空間求解。

以下複雜度類別之間的包含關係是成立的：

${\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)$

另外，根據薩維奇定理，如果$f\in \Omega (\log(n))$，則

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

上邊結果的一個直接推論是${\mathsf {PSPACE}}={\mathsf {NPSPACE}}$。這個推論意味着對於一個問題而言，非確定性可以為圖靈機節省的儲存空間是相當有限的。作為對比，在時間複雜度理論中，指數時間假說猜想，對於時間複雜度而言，非確定型和確定型空間複雜度類別之間的差距可能是指數級的。

根據Immerman–Szelepcsényi定理，對於$f\in \Omega (\log(n))$，${\mathsf {NSPACE}}(f(n))$在取反操作下閉合(即若一個語言$A\in {\mathsf {NSPACE}}(f(n))$，則其反語言$A^{c}=\{x|x\not \in A\}$也在${\mathsf {NSPACE}}(f(n))$中)。這可能意味着空間和時間複雜度類別在複雜度類別關係上的另一個差別，因為一般認為非確定空間複雜度類別在取反操作下不閉合，例如有猜想NP≠co-NP。

對數空間複雜度類別

對數空間複雜度類別L（或寫作LOGSPACE）是指確定性圖靈機相對於輸入$n$僅需$O(\log n)$儲存空間就可以解決的問題的集合。考慮到一個最大取值為輸入大小的計數器也需要$n$個位元，也即$\log n$的儲存空間；LOGSPACE中的一個演算法至多只能使用常數個計數器或其它複雜度相同的變數。

LOGSPACE以及其它次線性空間複雜度的演算法在處理輸入大到存不進電腦的隨機存取記憶體的問題時很有用。解決這類問題的演算法包括數據流演算法；但次線性空間複雜度只考慮所需要的儲存空間，而數據流演算法同時還要考慮輸入數據要怎樣被送入演算法中。 此複雜度類別的演算法在偽隨機性和去隨機化中也有應用，當前的相關開放問題包括L = RL是否成立。

與L對應的非確定性空間複雜度類別是NL。

輔助空間複雜度

術語輔助空間是指除被輸入數據佔據的空間之外使用的儲存空間。 因此，可以用以下方式來定義輔助空間複雜度：考慮一台擁有兩條紙帶的圖靈機，其中一條「輸入帶」只能讀不能寫，另一條一般的紙帶則可讀可寫。 則輔助空間複雜度只分析第二條紙帶（即作業紙帶，working tape）上的空間使用情況。 例如，對於平衡二叉樹的深度優先搜尋演算法，若二叉樹有$n$個節點，則其輔助空間複雜度是$\Theta (\log n)$。

參見

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