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

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

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

IT培訓(xùn)班

空間復(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ù)雜度來度量算法,當(dāng)不加限定地使用“復(fù)雜度”這一術(shù)語時,都是指時間復(fù)雜度。

分享到:
在線咨詢 我要報名
和我們在線交談!