热门问题
时间线
聊天
视角
空間複雜度
来自维基百科,自由的百科全书
Remove ads
在電腦科學中,一個演算法或程式的空間複雜度定性地描述該演算法或程式執行所需要的儲存空間大小。空間複雜度是相應計算問題的輸入值的長度的函數,它表示一個演算法完全執行所需要的儲存空間大小。[1]
和時間複雜度類似,空間複雜度通常也使用大O記號來漸進地表示,例如、、、等;其中n用來表示輸入的長度,該值可以影響演算法的空間複雜度。
就像時間複雜度的計算不考慮演算法所使用的空間大小一樣,空間複雜度也不考慮演算法執行需要的時間長短。
Remove ads
空間複雜度類別
複雜度類別是漸進複雜度相同的一類問題的集合。與時間複雜度類別DTIME(f(n))、NTIME(f(n))相似,空間複雜度類別DSPACE(f(n))和NSPACE(f(n))分別表示可以被確定型和非確定型圖靈機上使用大小的空間可以決定的語言的集合。此外,與P、NP類似,如果令可以是任意多項式,就得到複雜度類別PSPACE和NPSPACE。具體的定義為
和
Remove ads
複雜度類別之間的關係
根據空間層次定理,對於任意的空間可構函數,總存在這樣一個問題,它可以被一個圖靈機使用儲存空間求解,但不能被任何圖靈機用漸進少於的儲存空間求解。
以下複雜度類別之間的包含關係是成立的[2]:
另外,根據薩維奇定理,如果,則
上邊結果的一個直接推論是。這個推論意味著對於一個問題而言,非確定性可以為圖靈機節省的儲存空間是相當有限的。作為對比,在時間複雜度理論中,指數時間假說猜想,對於時間複雜度而言,非確定型和確定型空間複雜度類別之間的差距可能是指數級的。
根據Immerman–Szelepcsényi定理,對於,在取反操作下閉合(即若一個語言,則其反語言也在中)。這可能意味著空間和時間複雜度類別在複雜度類別關係上的另一個差別,因為一般認為非確定空間複雜度類別在取反操作下不閉合,例如有猜想NP≠co-NP。[3][4]
Remove ads
對數空間複雜度類別
對數空間複雜度類別L(或寫作LOGSPACE)是指確定性圖靈機相對於輸入僅需儲存空間就可以解決的問題的集合。考慮到一個最大取值為輸入大小的計數器也需要個位元,也即的儲存空間;LOGSPACE中的一個演算法至多只能使用常數個計數器或其它複雜度相同的變數。
LOGSPACE以及其它次線性空間複雜度的演算法在處理輸入大到存不進電腦的隨機存取記憶體的問題時很有用。解決這類問題的演算法包括資料流演算法;但次線性空間複雜度只考慮所需要的儲存空間,而資料流演算法同時還要考慮輸入資料要怎樣被送入演算法中。 此複雜度類別的演算法在偽隨機性和去隨機化中也有應用,當前的相關開放問題包括L = RL是否成立。[5][6]
與L對應的非確定性空間複雜度類別是NL。
輔助空間複雜度
術語輔助空間是指除被輸入資料占據的空間之外使用的儲存空間。 因此,可以用以下方式來定義輔助空間複雜度:考慮一台擁有兩條紙帶的圖靈機,其中一條「輸入帶」只能讀不能寫,另一條一般的紙帶則可讀可寫。 則輔助空間複雜度只分析第二條紙帶(即作業紙帶,working tape)上的空間使用情況。 例如,對於平衡二元樹的深度優先搜尋演算法,若二元樹有個節點,則其輔助空間複雜度是。
參見
參考資料
Wikiwand - on
Seamless Wikipedia browsing. On steroids.
Remove ads