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

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

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

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

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

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

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