空間復(fù)雜度（Space Complexity）是對一個算法在運行過程中臨時占用存儲空間大小的量度，記作S(n)=O(f(n))，其中，n為問題的規(guī)模，f(n)為語句關(guān)于n的所占存儲空間的函數(shù)。常見的空間復(fù)雜度有O(1)、O(n)和O(n2)等，當(dāng)算法運行時占用的臨時空間不隨某一變量n的改變而改變時，即空間復(fù)雜度為常量，表示為O(1)；當(dāng)算法運行時占用的臨時空間隨n的改變而改變時，空間復(fù)雜度即為O(n)；當(dāng)算法運行時占用的臨時空間隨n2的改變而改變時，空間復(fù)雜度則為O(n2)，以此類推。
一個算法的優(yōu)劣主要從算法的執(zhí)行時間和所需要占用的存儲空間兩個方面來衡量，即用空間復(fù)雜度和時間復(fù)雜度來衡量程序的效率。一個算法的空間復(fù)雜度是指程序從開始運行到結(jié)束所需的存儲空間大小，遞歸算法一般都比較簡短，算法本身所占用的存儲空間較小，但運行時需要一個附加堆棧，會占用較多的臨時存儲空間；非遞歸算法一般較長，因此存儲算法本身的空間較大，但運行時需要的存儲空間較小。
空間復(fù)雜度是算法運行時所占用空間的一個量度，而不是計算具體的占用空間，一般以數(shù)量級的形式給出，如O(1)、O(n)、O(n2)和O(log2n)等。算法的空間復(fù)雜度比較容易計算，主要包括局部變量（算法范圍內(nèi)定義的變量）所占用的存儲空間和系統(tǒng)為實現(xiàn)遞歸（如果算法是遞歸的話）所使用的堆?？臻g兩個部分。
簡介
類似于時間復(fù)雜度的討論，一個算法的空間復(fù)雜度(Space Complexity)S(n)定義為該算法所耗費的存儲空間，它也是問題規(guī)模n的函數(shù)。漸近空間復(fù)雜度也常常簡稱為空間復(fù)雜度?？臻g復(fù)雜度(SpaceComplexity)是對一個算法在運行過程中臨時占用存儲空間大小的量度。一個算法在計算機存儲器上所占用的存儲空間，包括存儲算法本身所占用的存儲空間，算法的輸入輸出數(shù)據(jù)所占用的存儲空間和算法在運行過程中臨時占用的存儲空間這三個方面。算法的輸入輸出數(shù)據(jù)所占用的存儲空間是由要解決的問題決定的，是通過參數(shù)表由調(diào)用函數(shù)傳遞而來的，它不隨本算法的不同而改變。存儲算法本身所占用的存儲空間與算法書寫的長短成正比，要壓縮這方面的存儲空間，就必須編寫出較短的算法。算法在運行過程中臨時占用的存儲空間隨算法的不同而異，有的算法只需要占用少量的臨時工作單元，而且不隨問題規(guī)模的大小而改變，我們稱這種算法是“就地\"進(jìn)行的，是節(jié)省存儲的算法，如這一節(jié)介紹過的幾個算法都是如此；有的算法需要占用的臨時工作單元數(shù)與解決問題的規(guī)模n有關(guān)，它隨著n的增大而增大，當(dāng)n較大時，將占用較多的存儲單元，例如將在第九章介紹的快速排序和歸并排序算法就屬于這種情況。
分析
分析一個算法所占用的存儲空間要從各方面綜合考慮。如對于遞歸算法來說，一般都比較簡短，算法本身所占用的存儲空間較少，但運行時需要一個附加堆棧，從而占用較多的臨時工作單元；若寫成非遞歸算法，一般可能比較長，算法本身占用的存儲空間較多，但運行時將可能需要較少的存儲單元。
一個算法的空間復(fù)雜度只考慮在運行過程中為局部變量分配的存儲空間的大小，它包括為參數(shù)表中形參變量分配的存儲空間和為在函數(shù)體中定義的局部變量分配的存儲空間兩個部分。若一個算法為遞歸算法，其空間復(fù)雜度為遞歸所使用的堆棧空間的大小，它等于一次調(diào)用所分配的臨時存儲空間的大小乘以被調(diào)用的次數(shù)(即為遞歸調(diào)用的次數(shù)加1，這個1表示開始進(jìn)行的一次非遞歸調(diào)用)。算法的空間復(fù)雜度一般也以數(shù)量級的形式給出。如當(dāng)一個算法的空間復(fù)雜度為一個常量，即不隨被處理數(shù)據(jù)量n的大小而改變時，可表示為O(1)；當(dāng)一個算法的空間復(fù)雜度與以2為底的n的對數(shù)成正比時，可表示為O(log2n)；當(dāng)一個算法的空間復(fù)雜度與n成線性比例關(guān)系時，可表示為O(n).若形參為數(shù)組，則只需要為它分配一個存儲由實參傳送來的一個地址指針的空間，即一個機器字長空間；若形參為引用方式，則也只需要為其分配存儲一個地址的空間，用它來存儲對應(yīng)實參變量的地址，以便由系統(tǒng)自動引用實參變量。
比較
對于一個算法，其時間復(fù)雜度和空間復(fù)雜度往往是相互影響的。當(dāng)追求一個較好的時間復(fù)雜度時，可能會使 空間復(fù)雜度的性能變差，即可能導(dǎo)致占用較多的 存儲空間；反之，當(dāng)追求一個較好的空間復(fù)雜度時，可能會使 時間復(fù)雜度的性能變差，即可能導(dǎo)致占用較長的運行時間。另外，算法的所有性能之間都存在著或多或少的相互影響。因此，當(dāng)設(shè)計一個算法(特別是大型算法)時，要綜合考慮算法的各項性能，算法的使用頻率，算法處理的數(shù)據(jù)量的大小，算法描述語言的特性，算法運行的機器系統(tǒng)環(huán)境等各方面因素，才能夠設(shè)計出比較好的算法。算法的時間復(fù)雜度和 空間復(fù)雜度合稱為算法的復(fù)雜度。
參考資料 >