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

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

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

知識回顧

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

算法是什么？

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

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

• 時間復(fù)雜度是對一個算法運行時間長短的量度，用大 O 表示，常見的時間復(fù)雜度按照從低到高的順序，包括

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

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

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

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

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

再從平常我們思考的角度講，我們?nèi)シ治鲆患虑?，一般要從理論和實際兩種層面上進行分析。比如我想去旅游，理論上我只要有錢，有時間，我就可以出去旅游。但是從現(xiàn)實的層面去考慮這件事就很繁瑣，我們要想到：當(dāng)前季節(jié)上是否適合旅游，自己是否要先向?qū)W?；蛘呱习嗟牡胤秸埣賵髠?，然后再考慮訂哪天的機票，以及目的地的選取等等瑣事。

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

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

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

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

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

就像時間復(fù)雜度的計算不考慮算法所使用的空間大小一樣，空間復(fù)雜度也不考慮算法運行需要的時間長短。

空間復(fù)雜度

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

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

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

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

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

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

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

常量空間

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

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

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

講解 python 代碼：

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

線性空間

當(dāng)算法分配的空間是一個線性的集合（如列表或數(shù)組），并且集合大小和輸入規(guī)模 n 成正比時，空間復(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)用這個函數(shù)的時候，我們向其中傳入一個參數(shù) n ，參數(shù) n 的類型為 ?int （整數(shù)類型），然后 n 被傳入后，函數(shù) ?fun2() 利用 n 做了一件事：定義了一個長度為 n ，元素為從1到 n 的列表 array_list 。我們本來的輸入規(guī)模為 n ，由上文中“ 程序在運行過程中，可能還需要臨時申請更多的存儲空間 ”可知，在函數(shù)內(nèi)我們引入了長度為 n 的列表。即在這個程序中，我們額外申請了 n 長度的一維列表，與輸入規(guī)模 n 成正比，所以該程序的空間復(fù)雜度記為?.

二維空間

當(dāng)算法分配的空間是一個二維列表或數(shù)組集合，并且集合的長度和寬度都與輸入規(guī)模 n 成正比時，空間復(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)
    ...

對 python 代碼進行講解：

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

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

程序調(diào)用函數(shù)是基于棧實現(xiàn)的，函數(shù)在調(diào)用期間，引入一個棧并進行入棧操作，將調(diào)用來的函數(shù)以及其參數(shù)信息全都壓入棧中，當(dāng)函數(shù)進行 return 操作時，執(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

對 python 代碼進行分析：

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

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

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

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

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

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

總結(jié)

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

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

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

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