【久遠(yuǎn)講算法】什么是空間復(fù)雜度？

“閱讀本文大概需要6分鐘”

這周我們繼續(xù)聊算法，接著上次的時(shí)間復(fù)雜度，我們進(jìn)行關(guān)于空間復(fù)雜度的講解。為了，更好的閱讀體驗(yàn)，你也可以選擇點(diǎn)擊閱讀原文。

知識(shí)回顧

首先，我們來對(duì)上周的任務(wù)進(jìn)行大概的復(fù)習(xí)。

算法是什么？

1. 命令安裝從理論層面來講，算法就是我們寫程序?qū)懘a的優(yōu)化手冊(cè)，它教會(huì)我們?cè)趺醋尨a運(yùn)行起來更快，或者占用的內(nèi)存空間更少。直觀層面來講便是，算法是一系列程序指令，用于處理特定的運(yùn)算和邏輯問題。一個(gè)算法是好是壞，我們通常根據(jù)時(shí)間復(fù)雜度和空間復(fù)雜度去評(píng)價(jià)。

時(shí)間復(fù)雜度是什么？

• 時(shí)間復(fù)雜度是對(duì)一個(gè)算法運(yùn)行時(shí)間長(zhǎng)短的量度，用大 O 表示，常見的時(shí)間復(fù)雜度按照從低到高的順序，包括

時(shí)間復(fù)雜度的要點(diǎn)包括以下內(nèi)容：

• 基本操作執(zhí)行次數(shù)。即每行代碼的執(zhí)行次數(shù)，我們通過這個(gè)來計(jì)算我們所寫的代碼詳細(xì)的執(zhí)行次數(shù)。
• 漸進(jìn)時(shí)間復(fù)雜度。計(jì)算基本操作執(zhí)行次數(shù)固然是一種求解時(shí)間復(fù)雜度的方法，但是我們平時(shí)寫的代碼是千奇百怪的，因此通過計(jì)算基本操作執(zhí)行次數(shù)得到的數(shù)字或函數(shù)大多都比較復(fù)雜，并不適合直接充當(dāng)我們的時(shí)間復(fù)雜度，因此我們引入了漸進(jìn)時(shí)間復(fù)雜度的概念，漸進(jìn)時(shí)間復(fù)雜度常用大 O 符號(hào)表述，不包括這個(gè)函數(shù)的低階項(xiàng)和首項(xiàng)系數(shù)。使用漸進(jìn)時(shí)間復(fù)雜度可保證我們算出的時(shí)間復(fù)雜度函數(shù)相比起基本執(zhí)行操作次數(shù)總和更加簡(jiǎn)潔。

空間復(fù)雜度和時(shí)間復(fù)雜度的關(guān)系

空間復(fù)雜度和時(shí)間復(fù)雜度，這兩個(gè)東西長(zhǎng)得非常的像，但到底有什么區(qū)別呢？

從文字的角度，我們可以聯(lián)想到，時(shí)間一般是我們摸不著的，比較抽象的東西。而空間一般是現(xiàn)實(shí)存在的，我們能摸到的，比較具體的東西。

再?gòu)钠匠Ｎ覀兯伎嫉慕嵌戎v，我們?nèi)シ治鲆患虑?，一般要從理論和?shí)際兩種層面上進(jìn)行分析。比如我想去旅游，理論上我只要有錢，有時(shí)間，我就可以出去旅游。但是從現(xiàn)實(shí)的層面去考慮這件事就很繁瑣，我們要想到：當(dāng)前季節(jié)上是否適合旅游，自己是否要先向?qū)W?；蛘呱习嗟牡胤秸?qǐng)假報(bào)備，然后再考慮訂哪天的機(jī)票，以及目的地的選取等等瑣事。

編程也并不是一件虛擬的事情，它是切實(shí)存在且在生活中被頻繁使用的，因此我們有必要從理論和實(shí)際兩種方面考慮自己所寫的代碼的可行性。

時(shí)間復(fù)雜度就是我們對(duì)自己代碼的“理論分析”。從我們個(gè)人編程的角度而言，我們的代碼僅用于個(gè)人電腦使用，并不參與企業(yè)開發(fā)，所以我們一般不去考慮計(jì)算機(jī)的性能。單純的考慮了，怎么寫這段代碼，它不會(huì)出錯(cuò)，可以正確執(zhí)行。在進(jìn)行數(shù)據(jù)結(jié)構(gòu)和算法的學(xué)習(xí)之后，我們慢慢的開始考慮自己代碼的時(shí)間復(fù)雜度。即如何讓自己寫的代碼運(yùn)行速度的更快一些。

空間復(fù)雜度便是我們對(duì)自己代碼的“實(shí)際分析”。可能我們個(gè)人寫代碼體會(huì)不到空間復(fù)雜度的重要性。假設(shè)你在大型企業(yè)上班，你的老板要求你開發(fā)一個(gè)手機(jī)應(yīng)用，這個(gè)時(shí)候，我們要考慮的就不僅僅是，我寫的代碼能不能正常運(yùn)行起來這件事了，因?yàn)槟阋驹谟脩舻慕嵌热タ紤]，你的體驗(yàn)度是怎么樣的，作為手機(jī)應(yīng)用的使用者，我們自然會(huì)想到，我希望這個(gè)手機(jī)應(yīng)用能夠秒開，而不是點(diǎn)進(jìn)去半天才能加載出來，同時(shí)也希望這個(gè)手機(jī)應(yīng)用占手機(jī)的內(nèi)存少一點(diǎn)。而作為老板，讓員工開發(fā)應(yīng)用的時(shí)候，也希望公司提供的電腦能安全完成開發(fā)，不希望出現(xiàn)因?yàn)榇a運(yùn)行時(shí)間過長(zhǎng)而消耗電腦硬件，導(dǎo)致電腦壞掉拖延項(xiàng)目進(jìn)展的事情發(fā)生。

空間復(fù)雜度有著類似于時(shí)間復(fù)雜度的概念：一個(gè)算法或程序的空間復(fù)雜度定性地描述該算法或程序運(yùn)行所需要的存儲(chǔ)空間大小?？臻g復(fù)雜度是相應(yīng)計(jì)算問題的輸入值的長(zhǎng)度的函數(shù)，它表示一個(gè)算法完全執(zhí)行所需要的存儲(chǔ)空間大小。和時(shí)間復(fù)雜度類似，空間復(fù)雜度通常也使用大 O 記號(hào)來漸進(jìn)地表示，即空間復(fù)雜度也有漸進(jìn)空間復(fù)雜度一說。例如、 、

、 等；其中 n 用來表示輸入的長(zhǎng)度，該值可以影響算法的空間復(fù)雜度。

就像時(shí)間復(fù)雜度的計(jì)算不考慮算法所使用的空間大小一樣，空間復(fù)雜度也不考慮算法運(yùn)行需要的時(shí)間長(zhǎng)短。

空間復(fù)雜度

從整個(gè)程序來討論的話，程序的空間復(fù)雜度可以完全用程序代碼本身所占用的存儲(chǔ)空間多少來表示。

首先，程序自身所占用的存儲(chǔ)空間取決于其包含的代碼量，我們只要在編程環(huán)境下輸入代碼進(jìn)行運(yùn)行，那么這段代碼必定會(huì)占用電腦的存儲(chǔ)空間。想要壓縮這部分存儲(chǔ)空間，就要求我們?cè)趯?shí)現(xiàn)功能的同時(shí)，盡可能編寫足夠短的代碼，但從這一方面來講，過于龐大，畢竟我們編寫一段代碼，其中包含著很多內(nèi)容，我們將繼續(xù)將代碼拆分分析為以下兩種情況去推算空間復(fù)雜度。

一般一段代碼的空間復(fù)雜度涉及到的空間類型有：

• 輸入、輸出空間。程序中如果需要輸入輸出數(shù)據(jù)，也會(huì)占用一定的存儲(chǔ)空間。程序運(yùn)行過程中輸入輸出的數(shù)據(jù)，往往由要解決的問題而定，即便所用算法不同，程序輸入輸出所占用的存儲(chǔ)空間也是相近的。即，無論是我們使用 10 行代碼還是三行代碼去實(shí)現(xiàn)同一個(gè)問題，他們最終輸出的東西一樣的話，即使二者代碼長(zhǎng)度不盡相同，但是輸出所占的存儲(chǔ)空間是差不多大的。

• 暫存空間。程序在運(yùn)行過程中，可能還需要臨時(shí)申請(qǐng)更多的存儲(chǔ)空間。事實(shí)上，對(duì)算法的空間復(fù)雜度影響最大的，往往是程序運(yùn)行過程中所申請(qǐng)的臨時(shí)存儲(chǔ)空間。不同的算法所編寫出的程序，其運(yùn)行時(shí)申請(qǐng)的臨時(shí)存儲(chǔ)空間通常會(huì)有較大不同。

通常情況下，空間復(fù)雜度指在輸入數(shù)據(jù)大小為 N 時(shí)，算法運(yùn)行所使用的「暫存空間」+「輸出空間」的總體大小。

先來看幾種常見的空間復(fù)雜度。我們根據(jù)代碼來進(jìn)行詳細(xì)分析。

常量空間

當(dāng)算法的存儲(chǔ)空間大小固定，和輸入規(guī)模沒有直接的關(guān)系時(shí)，空間復(fù)雜度記為?? .

void fun1(int n){
    int var = 3;
    ...
}

def fun1(n):
    var = 3
    ...

講解 python 代碼：

我們定義了 fun1() 函數(shù)，當(dāng)我們調(diào)用這個(gè)函數(shù)的時(shí)候，我們要向其中傳入一個(gè)參數(shù) n ，但是n傳入后，函數(shù) ?fun1() 做了一件事，它里層引入了一個(gè) var 變量 并給它賦值 3 ，但這一切并沒有改變我們輸入的參數(shù) n 的值和類型。根據(jù)上文第二條 “ 程序中如果需要輸入輸出數(shù)據(jù)，也會(huì)占用一定的存儲(chǔ)空間 ”，我們輸入的參數(shù) n 從頭至尾沒有發(fā)生改變，因此程序所占的存儲(chǔ)空間也沒有發(fā)生改變。所以該程序的空間復(fù)雜度為? .

線性空間

當(dāng)算法分配的空間是一個(gè)線性的集合（如列表或數(shù)組），并且集合大小和輸入規(guī)模 n 成正比時(shí)，空間復(fù)雜度記作 .

void fun2(int n){
    int[] array = new int[n];
    ...
}

def fun2(n:int):
    array_list = [for x in range(1,n)]
    ...

講解 python 代碼：

我們定義了 ?fun2() 函數(shù)，當(dāng)我們調(diào)用這個(gè)函數(shù)的時(shí)候，我們向其中傳入一個(gè)參數(shù) n ，參數(shù) n 的類型為 ?int （整數(shù)類型），然后 n 被傳入后，函數(shù) ?fun2() 利用 n 做了一件事：定義了一個(gè)長(zhǎng)度為 n ，元素為從1到 n 的列表 array_list 。我們本來的輸入規(guī)模為 n ，由上文中“ 程序在運(yùn)行過程中，可能還需要臨時(shí)申請(qǐng)更多的存儲(chǔ)空間 ”可知，在函數(shù)內(nèi)我們引入了長(zhǎng)度為 n 的列表。即在這個(gè)程序中，我們額外申請(qǐng)了 n 長(zhǎng)度的一維列表，與輸入規(guī)模 n 成正比，所以該程序的空間復(fù)雜度記為?.

二維空間

當(dāng)算法分配的空間是一個(gè)二維列表或數(shù)組集合，并且集合的長(zhǎng)度和寬度都與輸入規(guī)模 n 成正比時(shí)，空間復(fù)雜度記作?.

void fun3(int n){
    int[][] matrix = new int[n][n];
    ...
}

def fun3(n:int):
    matrix_list = []
    for i in range(n):
        matrix_list.append([0]*n)
    ...

對(duì) python 代碼進(jìn)行講解：

我們新建了一個(gè)函數(shù)fun3() ,它的目的是新建一個(gè)? 的二維列表，我們的做法是：首先新建一個(gè)空的列表 matrix_list 然后對(duì) matrix_list 進(jìn)行一維列表的迭代和添加，最后生成二維列表。首先我們從生成一維列表開始，將 n 傳入 fun3() 中，我們首先新建一個(gè)空列表，為之后向列表中添加元素做準(zhǔn)備，然后我們要稍微動(dòng)一下腦子，當(dāng)新建一個(gè)長(zhǎng)度為 n 元素全為 0 的一維列表時(shí)，我們使用了循環(huán)來進(jìn)行列表的初始化，所以在新建二維列表時(shí)，我們可以用類似的方法，同樣使用循環(huán)來進(jìn)行初始化，在一維列表初始化過程中，我們是不是將0元素挨個(gè)添加到列表中，以實(shí)現(xiàn)有 n 個(gè) 0 的列表，那現(xiàn)在我們要生成擁有? 個(gè) 0 的列表，那是不是將[0] 做 n 次循環(huán)添加到 matrix_list 中就可以了。然后我們根據(jù)“ 程序在運(yùn)行過程中，可能還需要臨時(shí)申請(qǐng)更多的存儲(chǔ)空間?！边@一點(diǎn)可知，我們傳入的參數(shù) n 與二維列表 ? 的長(zhǎng)度成正比。所以該代碼空間復(fù)雜度即為.

以下我們使用了當(dāng) n 為2時(shí)的情況，進(jìn)行了函數(shù)模擬。

程序調(diào)用函數(shù)是基于棧實(shí)現(xiàn)的，函數(shù)在調(diào)用期間，引入一個(gè)棧并進(jìn)行入棧操作，將調(diào)用來的函數(shù)以及其參數(shù)信息全都?jí)喝霔Ｖ?，?dāng)函數(shù)進(jìn)行 return 操作時(shí)，執(zhí)行出棧操作，把上一次調(diào)用的函數(shù)和參數(shù)信息從棧中彈出。從而釋放掉多余的內(nèi)存。

int fun4(int N){
    if(N <= 1){
        return 1;
    }
    return fun4(N - 1) + 1;
}

def fun4(N:int):
    if N <= 1: return 1
    return fun4(N - 1) + 1

對(duì) python 代碼進(jìn)行分析：

當(dāng)我們輸入的? 時(shí)，我們將直接返回 1， 這是我們的遞歸結(jié)束點(diǎn)。當(dāng)我們輸入的 N 大于 1時(shí)，程序會(huì)引入一個(gè)棧，將 fun4(N)放入棧中，而 fun4(N) 又要調(diào)用 fun(N - 1) + 1 因此我們將fun(N - 1) - 1 放入棧中，以此類推直到 N 變?yōu)?1 ，這是 我們找到了遞歸結(jié)束點(diǎn)，將棧內(nèi)的函數(shù)全都挨個(gè)釋放出來即可。由上面函數(shù)的出入棧過程可以看出，執(zhí)行遞歸操作所需要的內(nèi)存空間和遞歸的深度成正比。純粹的遞歸操作的空間復(fù)雜度也是線性，但如果遞歸的深度是 n ，那么空間復(fù)雜度就是.

我們利用了 N = 6 進(jìn)行了程序模擬也給出了遞歸樹，（關(guān)于遞歸，我們之后會(huì)詳細(xì)講解）以便大家更方便理解：

時(shí)間和空間的權(quán)衡

在上文筆者也提到，寫代碼其實(shí)不是一件虛擬的事情，它涉及到了現(xiàn)實(shí)的很多情況，當(dāng)你在企業(yè)工作時(shí)，你所寫的代碼并不是單單滿足你自己的需求即可，而是要考慮各種各樣現(xiàn)實(shí)的限制了。雖然隨著科技的發(fā)展，電腦更新?lián)Q代非常的快，性能也是越來越強(qiáng)大。但電腦的內(nèi)存并不是無限的，它的性能終究是有限的。因此我們?cè)趯懘a的時(shí)候也要 “精打細(xì)算”，選擇更加高效的執(zhí)行辦法。

對(duì)于算法的性能，需要從時(shí)間和空間的使用情況來綜合評(píng)價(jià)。好的算法應(yīng)具備兩個(gè)特性，即時(shí)間和空間復(fù)雜度均比較低。而實(shí)際上，對(duì)于某個(gè)算法問題，正因?yàn)殡娔X的能力是有限的，所以我們的時(shí)間復(fù)雜度和空間空間復(fù)雜度是沒有辦法同時(shí)兼顧的，因此將會(huì)出現(xiàn)，時(shí)間換空間或者空間換時(shí)間的情況發(fā)生。

因?yàn)楝F(xiàn)在科技發(fā)展很快，電腦性能一般比較強(qiáng)大，滿足了我們的日常需求，所以在平常的代碼編寫過程中，我們絕大多數(shù)情況，會(huì)考慮空間換取時(shí)間的操作，多分配一些內(nèi)存空間，讓程序跑到更快。

總結(jié)

• 什么是空間復(fù)雜度？

空間復(fù)雜度是對(duì)一個(gè)算法在運(yùn)行過程中臨時(shí)占用存儲(chǔ)空間大小的量度，用大 O 表示，常見的空間復(fù)雜度按照從低到高的順序，包括

其中遞歸算法的空間復(fù)雜度和遞歸深度成正比。

關(guān)注微信公眾號(hào)：AI悅創(chuàng)，不迷路。下次我們進(jìn)行數(shù)據(jù)結(jié)構(gòu)的講解。流沙團(tuán)隊(duì)長(zhǎng)期招收一對(duì)一學(xué)員，Python 一對(duì)一、數(shù)據(jù)結(jié)構(gòu)與算法一對(duì)一，系統(tǒng)入門掃盲。