首頁(yè)人工智能技術(shù)資訊正文

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

更新時(shí)間:2023-07-26 來源:黑馬程序員 瀏覽量:

IT培訓(xùn)班

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

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

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

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

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

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

分享到:
在線咨詢 我要報(bào)名
和我們?cè)诰€交談!