怎樣理解算法的空間復(fù)雜度？

空間復(fù)雜度是對一個算法在運行過程中所占存儲空間大小的度量，一般也作為問題規(guī)模n的函數(shù)，以數(shù)量級形式給出，格式如下所示：

S(n)=O(f(n))

一個算法的存儲量包括輸人數(shù)據(jù)所占空間、程序本身所占空間和輔助變量所占空間。在對算法進行分析時，只考慮輔助變量所占空間。

若所需輔助空間相對于輸入數(shù)據(jù)量來說是常數(shù)，則稱此算法為原地工作。若所用空間量依賴于特定的輸入，則除了有特殊說明外，均按最壞情況考慮。

有時候，在寫代碼時可以用空間來換取時間，例如，寫一個算法來判斷某年是否是閏年，這樣每輸人一個年份都要調(diào)用算法去判斷一下，在時間上就有點復(fù)雜。為了提高效率，可以用空間來換取時間，即建立一個大小合適的數(shù)據(jù)，編號從0到n，如果是閏年，則存人數(shù)據(jù)1，否則存入微據(jù)0。這樣只要通過判斷年份編號上存儲的是0還是1就知道該年份是否是閏年了。

用空間換取時間可以將運算最小化，但這兩種情況哪種更好，要結(jié)合具體情況而定。一般情況下，都是用時間復(fù)雜度來度量算法，當不加限定地使用“復(fù)雜度”這一術(shù)語時，都是指時間復(fù)雜度。