目錄

一、引入空間復雜度的原因

二、空間復雜度的分析

? 2.1?程序運行時內存大小 ~ 程序本身大小

? 2.2 程序運行時內存大小 ~ 算法運行時內存大小

? 2.3 算法運行時內存大小

? 2.4?不考慮算法全部運行空間的原因

三、空間復雜度

? 3.1空間復雜度的定義

? 3.2?空間復雜度不能準確算出空間大小的原因

? 3.3 最關注差空間復雜度的原因

四、空間復雜度的計算

五、常見空間復雜度舉例

? 5.1 常數階

? 5.2 線性階

? 5.3 平方階

六、遞歸與非遞歸空間復雜度

? 6.1 常規函數空間復雜度不重點算棧空間大小的原因

? 6.2 遞歸函數空間復雜度需要算棧空間大小的原因

七、權衡時間與空間效率

---

一、引入空間復雜度的原因

1. 我們知道，一個算法的好壞主要從算法的執行時間和所需要占用的存儲空間這兩個方面來進行衡量。
2. 當一個算法在執行過程中存儲數據所需要占用的內存空間的大小，就是空間復雜度。它和時間復雜度一樣，是衡量算法性能的重要指標之一。
3. 在開發程序之前，分析算法的空間復雜度有助于開發者提前預估程序運行時所需的內存空間，從而合理地規劃硬件資源。

二、空間復雜度的分析

? 2.1?程序運行時內存大小 ~ 程序本身大小

首先我們先弄清楚什么是程序本身內存的大小，什么是程序運行時內存的大小？有什么關系？

1. 程序本身內存的大小：指的是程序文件存儲在磁盤等存儲設備上所占用的存儲空間大小。它主要取決于程序的源代碼經過編譯、鏈接等操作后生成的可執行文件所包含的內容，包括代碼段、數據段等。
2. 程序運行時內存的大小：指的是程序在計算機內存中運行時所占用的存儲空間的量。它涉及到程序運行過程中各個方面對內存的使用，包括代碼區、數據區（如全局變量、靜態變量、常量）、棧區（存儲函數調用信息和局部變量）和堆區（用于動態內存分配）等所占用的內存總和。

程序運行時的內存大小是包含程序本身的大小的。

• 通俗來講，程序本身的大小好比一顆種子，而程序運行的大小就像生長后的植株。
• 程序本身就像一顆種子，其大小是固定的，蘊含著生長的潛力和信息。
• 當種子種下并開始生長后，就如同程序開始運行。當種子長成大樹后，會有粗壯的樹干和茂密的枝葉，需要占據很大的空間。這就像程序運行時，會在系統中展開龐大的運行架構，占用大量的內存、CPU 等資源，其運行時占據的 “空間” 和要比程序本身所占用的大得多，也有可能會隨著業務的發展和數據量的增加不斷擴展。

? 2.2 程序運行時內存大小 ~ 算法運行時內存大小

程序運行時內存大小和算法運行時內存大小有什么關系？

程序是一個更為寬泛的概念，它由多個部分組成，算法只是程序實現特定功能的核心邏輯。程序運行時，其內存占用除了算法運行所需的內存外，還包括其他諸多方面。算法運行的內存主要用于存儲算法執行過程中使用的數據結構、中間變量、遞歸調用棧等。而程序運行內存還包含程序代碼本身占用的空間（代碼段）、全局和靜態變量占用的空間（數據段）、程序與外部交互的輸入輸出緩沖區、加載的庫文件所占用的內存等。

在一些非常簡單的程序中，如果程序的主要功能就是執行一個單一的算法，且沒有其他復雜的功能模塊、全局變量、輸入輸出操作等，那么算法運行的內存大小可能與程序運行內存大小非常接近。例如，一個簡單的控制臺程序，其唯一的功能就是實現一個簡單的遞歸算法計算斐波那契數列，此時程序運行內存主要就是算法運行所需的內存。

但在大多數實際應用中，程序運行時內存的大小通常會大于算法運行時內存的大小。

? 2.3 算法運行時內存大小

算法運行時內存大小主要分為以下幾個部分：

輸入數據空間：存儲算法的輸入數據

輸出數據空間：存儲算法的輸出數據

暫存數據空間：用于存儲算法在運行過程中的變量、對象、函數上下文等數據

暫存數據空間又可以分為：

• 暫存數據：保存算法運行過程中的各種常量、變量、對象等
• 棧幀空間：保存調用函數的上下文數據
• 指令空間：保存編譯后的程序指令，但在統計空間復雜度時通常忽略不計

空間復雜度通常統計的是暫存數據和棧幀空間。

? 2.4?不考慮算法全部運行空間的原因

• 輸入數據空間：

輸入數據所占用的空間通常不納入空間復雜度的考量范圍。因為輸入數據是算法處理的對象，它的規模是由問題本身決定的，并非算法為完成任務而額外使用的空間。

例：對一個包含n個元素的數組進行排序，數組本身占用的存儲空間與算法的空間使用效率并無直接關聯，所以不包含在空間復雜度的計算中。

• 程序代碼空間：

程序代碼本身所占用的存儲空間也不影響算法的空間復雜度。代碼大小是固定的，不隨輸入規模的變化而變化，它與算法在處理不同規模輸入時的內存需求增長特性沒有直接聯系。無論輸入規模如何，程序代碼的空間占用都是恒定的，因此不將其納入空間復雜度的計算。

• 輸出數據空間：

通常而言，輸出數據一般不計入空間復雜度。像常規算法的單一返回值，或是排序、查找算法的輸出結果，其占用空間固定或由輸入決定，不反映額外開銷，可不考慮。

但當輸出規模與輸入緊密相關、或優化目標是輸出空間時，則可能計入。

因為空間復雜度更專注于算法本身的邏輯實現對存儲空間的需求，即專注于為了完成算法任務，除輸入數據本身所占空間之外，算法額外需要的輔助空間大小。所以空間復雜度不考慮算法全部運行空間。

三、空間復雜度

? 3.1空間復雜度的定義

空間復雜度（Space Complexity）也是一個數學表達式，是對一個算法在運行過程中臨時占用存儲空間大小的量度。

注意：函數運行時所需要的棧空間(存儲參數、局部變量、一些寄存器信息等)在編譯期間已經確定好了，因此空間復雜度主要通過函數在運行時候顯式申請的額外空間來確定。

? 3.2?空間復雜度不能準確算出空間大小的原因

1. 空間復雜度是對一個算法在運行過程中臨時占用存儲空間大小的量度，是一種漸近分析，使用大O表示法描述算法在問題規模趨于無窮大時，額外存儲空間隨問題規模增長的趨勢，而不是精確的內存使用量。
2. 此外，程序運行時所占用的內存還受到很多與算法本身無關的因素影響，不同的計算機硬件環境（如內存架構、字長等）和軟件環境（如操作系統的內存管理機制、編譯器的優化程度等）會導致同一算法在不同環境下的實際內存占用有所不同。這會影響程序的實際內存使用，但空間復雜度分析通常不會考慮這些具體環境因素。

? 3.3 最關注差空間復雜度的原因

與時間復雜度不同的是，一般情況下，我們只關注最差空間復雜度，因為內存空間是有限的，我們要確保在所有輸入數據下都有足夠的內存空間。

四、空間復雜度的計算

空間復雜度直接計算變量個數即可，不需要程序占用了多少字節的空間。

計算變量個數的原因：

因為空間復雜度計算規則基本跟時間復雜度類似，也是使用大O漸進表示法來表示空間復雜度。

我們知道，大O漸進表示法表示的是估算值，而不是真實值，主要目的是為了算出空間復雜度屬于哪個量級。

舉例：

• 一個int型變量，占用空間大小是4bit，4的大小是屬于常數階的，那么它的空間復雜度為O(1)
• n個int型變量的數組，占用的空間大小是4nbit，4n的大小是屬于線性階的，那么它的空間復雜度為O(N)

所以說，為了方便計算空間復雜度的大小，我們可以直接計算變量個數。

五、常見空間復雜度舉例

? 5.1 常數階

常數階的空間復雜度為：O(1)

• 當空間復雜度為O(1)的情況下，也稱算法為原地工作或者就地工作。
• 原地工作（就地工作）：指的是算法的執行過程中不使用額外的存儲空間，或者使用的額外空間相對輸入數據量是常數。即所使用的額外空間量不隨問題規模（即輸入數據的大小）的變化而變化。

例題1：

//計算BubbleSort的空間復雜度
void BubbleSort(int* a, int n)
{assert(a);for (size_t end = n; end > 0; --end){int exchange = 0;for (size_t i = 1; i < end; ++i){if (a[i - 1] > a[i]){Swap(&a[i - 1], &a[i]);exchange = 1;}}if (exchange == 0)break;}
}

這段冒泡排序的代碼中，分別有end，i，exchange這3個新的變量出現，也就是為這3個變量開辟了空間，因為3是常數，所以冒泡排序的空間復雜度為：O(1)

例題2：

void fun()
{return 0;
}void tmp(int n)
{int i = 0;for (i = 0; i < n; i++){fun();}}

注意：在循環中初始化變量或調用函數而占用的內存，在進入下一循環后就會被釋放，因此不會累積占用空間，空間復雜度仍為?𝑂(1)

? 5.2 線性階

線性階的空間復雜度為：O(N)

例題：

// 計算階乘遞歸Factorial的空間復雜度
long long Fac(int N)
{if (N == 0)return 1;return Fac(N - 1) * N;
}

Fac遞歸函數Fac用于計算階乘。

函數遞歸調用的深度為N，開辟了N個棧幀，每個棧幀使用了常數個空間。所以空間復雜度為O(N）

? 5.3 平方階

平方階的空間復雜度為：O(N^2)

例題：

long long Fac(int N)
{if (N == 0)return 1;int arr[N];return Fac(N - 1) * N;
}

在每個遞歸函數中都初始化了一個數組，總長度為1+2+...+（N-1）+ N?= N(N+1) /?2

因為空間復雜度算的是所處的量級，所以是O(N^2)

六、遞歸與非遞歸空間復雜度

? 6.1 常規函數空間復雜度不重點算棧空間大小的原因

在編譯階段，編譯器會根據函數的定義，分析函數中的參數、局部變量以及可能保存的寄存器信息等，從而確定函數調用時一個棧幀所需要的空間大小和布局。

例：

int add(int a, int b)
{int result;result = a + b;return result;
}

編譯器知道需要為兩個int類型的參數a，b，一個int類型的局部變量result，以及返回地址等分配空間。

這是對單個棧幀而言的，是一個固定的模式，不隨輸入規模或函數執行過程發生顯著變化。在大O表示法這種漸進分析中，這部分固定大小的空間被視為常數項。

空間復雜度主要關注的是隨著問題規模的增長，算法所需空間的增長趨勢。對于常規函數，顯式申請的額外空間，如動態分配的數組或對象等，才是隨著問題規模可能呈線性、對數等不同趨勢增長的部分，是影響空間復雜度的關鍵因素。

? 6.2 遞歸函數空間復雜度需要算棧空間大小的原因

棧在編譯期間確定的是單個棧幀的空間布局，但在遞歸函數運行時會不斷產生新的棧幀。

• 在編譯時，無法確定遞歸函數會被調用多少次，只有在程序運行時，隨著遞歸函數的不斷調用和返回，才會實際地在棧上創建和釋放棧幀，從而動態地占用和釋放棧空間。
• 棧幀數量與遞歸深度直接相關，而遞歸深度往往與問題規模有關。

例：在5.2的遞歸計算階乘函數，遞歸深度與輸入的n成正比，每一層遞歸都要占用一定棧空間存儲當前層的參數、局部變量等，所以棧空間占用會隨著遞歸深度增加而顯著增加。

總言之，遞歸棧空間中單個棧幀的結構和大小在編譯時期是可以確定的，但遞歸過程中棧空間的實際創建和使用是在運行時動態進行的，并不是完全在編譯時期就確定好的。空間復雜度關注的是運行時內存的大小。

七、權衡時間與空間效率

• 實際情況下，算法的時間效率和空間效率同時達到最優非常困難。
• 通常情況下，我們不太關注算法的空間效率，更注重時間效率。
• 但是，像互聯網、嵌入式等行業對空間效率也是較為注重的。
• 所以，選擇優化時間復雜度或者空間復雜度取決于我們的側重方面。