《Hello 算法》空間複雜度全解析統計範圍、推算方法與常見型別實戰【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo空間複雜度space complexity用於衡量演算法佔用記憶體空間隨資料量變大時的增長趨勢與時間複雜度並列為演算法複雜度分析的兩大支柱。本文基於《Hello 算法》繁體中文版 空間複雜度章節 展開結合倉庫內 Python、C、Java 等語言的完整可執行源碼系統講解空間的構成與統計範圍、最差空間複雜度的推算方法、五種常見空間複雜度型別以及「以空間換時間」與「以時間換空間」的取捨思路。讀完本文你將能獨立對任意演算法進行準確的空間複雜度分析並能直接執行倉庫中的配套程式碼驗證結論。什麼是空間複雜度空間複雜度space complexity用於衡量演算法佔用記憶體空間隨著資料量變大時的增長趨勢。這個概念與時間複雜度非常類似只需將「執行時間」替換為「佔用記憶體空間」。它回答的核心問題是當輸入資料規模 $n$ 增大時演算法所需的記憶體以什麼樣的速率增長與時間複雜度一樣空間複雜度同樣使用大 $O$ 記號漸近上界來描述關注的是增長趨勢而非絕對位元組數因此可以忽略常數因子與低階項。例如某演算法佔用 $3n 100$ 個單位空間其空間複雜度記為 $O(n)$。演算法相關空間統計範圍是「暫存 輸出」演算法在執行過程中使用的記憶體空間主要包括以下幾種輸入空間用於儲存演算法的輸入資料暫存空間用於儲存演算法在執行過程中的變數、物件、函式上下文等資料輸出空間用於儲存演算法的輸出資料。一般情況下空間複雜度的統計範圍是「暫存空間」加上「輸出空間」不包含輸入空間——因為輸入資料往往是問題本身給定的不屬於演算法決策的範疇。暫存空間可以進一步劃分為三個部分暫存資料用於儲存演算法執行過程中的各種常數、變數、物件等堆疊幀空間用於儲存呼叫函式的上下文資料。系統在每次呼叫函式時都會在堆疊頂部建立一個堆疊幀函式返回後堆疊幀空間會被釋放指令空間用於儲存編譯後的程式指令在實際統計中通常忽略不計。因此在分析一段程式的空間複雜度時我們通常統計暫存資料、堆疊幀空間和輸出資料三部分見上圖。下面以 Python 為例展示這幾類空間在程式碼中的對應關係完整多語言版本見倉庫 space_complexity.pyclass Node: 類別 def __init__(self, x: int): self.val: int x # 節點值 self.next: Node | None None # 指向下一節點的引用 def function() - int: 函式 # 執行某些操作... return 0 def algorithm(n) - int: # 輸入資料 A 0 # 暫存資料常數一般用大寫字母表示 b 0 # 暫存資料變數 node Node(0) # 暫存資料物件 c function() # 堆疊幀空間呼叫函式 return A b c # 輸出資料從 C 實作 與 Java 實作 可以看出無論語言差異這四類空間的劃分邏輯完全一致C 語言版本中func()的呼叫同樣對應堆疊幀空間見 space_complexity.c。這說明空間分類是跨語言通用的分析框架。空間複雜度的推算方法空間複雜度的推算方法與時間複雜度大致相同只需將統計物件從「操作數量」轉為「使用空間大小」。而與時間複雜度不同的是我們通常只關注最差空間複雜度。這是因為記憶體空間是一項硬性要求我們必須確保在所有輸入資料下都有足夠的記憶體空間預留。以極端輸入為例若某演算法在正常輸入下需要 10 MB但在某種輸入下需要 1 GB我們就必須按 1 GB 來預留記憶體否則程式會因記憶體不足而崩潰。「最差」的兩層含義觀察以下程式碼最差空間複雜度中的「最差」有兩層含義以最差輸入資料為準當 $n 10$ 時空間複雜度為 $O(1)$但當 $n 10$ 時初始化的陣列nums佔用 $O(n)$ 空間因此最差空間複雜度為 $O(n)$。以演算法執行中的峰值記憶體為準例如程式在執行最後一行之前佔用 $O(1)$ 空間當初始化陣列nums時程式佔用 $O(n)$ 空間因此最差空間複雜度為 $O(n)$。def algorithm(n: int): a 0 # O(1) b [0] * 10000 # O(1)常數大小與 n 無關 if n 10: nums [0] * n # O(n)注意即使b是一個長度為 10000 的陣列只要其大小與輸入 $n$ 無關就仍屬於 $O(1)$。空間複雜度衡量的永遠是增長趨勢而不是絕對大小。遞迴中的堆疊幀統計loop 與 recur 的關鍵差異在遞迴函式中需要注意統計堆疊幀空間。觀察以下程式碼def function() - int: # 執行某些操作 return 0 def loop(n: int): 迴圈的空間複雜度為 O(1) for _ in range(n): function() def recur(n: int): 遞迴的空間複雜度為 O(n) if n 1: return return recur(n - 1)函式loop()和recur()的時間複雜度都為 $O(n)$但空間複雜度不同函式loop()在迴圈中呼叫了 $n$ 次function()每輪中的function()都返回並釋放了堆疊幀空間因此空間複雜度仍為 $O(1)$遞迴函式recur()在執行過程中會同時存在 $n$ 個未返回的recur()從而佔用 $O(n)$ 的堆疊幀空間。這是一對非常經典的對比迭代版本在任意時刻最多只有一個活動的函式呼叫而遞迴版本在觸底之前所有層級的呼叫都「懸掛」在呼叫堆疊上。相同的時間複雜度截然不同的空間複雜度——這正是分析遞迴演算法時最容易忽略的地方。對應實作同樣可在 space_complexity.cpplinearRecur與 space_complexity.javalinearRecur中找到兩者行為一致。常見的空間複雜度型別設輸入資料大小為 $n$常見的空間複雜度型別從低到高排列如下$$ \begin{aligned} O(1) O(\log n) O(n) O(n^2) O(2^n) \newline \text{常數階} \text{對數階} \text{線性階} \text{平方階} \text{指數階} \end{aligned} $$常數階 $O(1)$常數階常見於數量與輸入資料大小 $n$ 無關的常數、變數、物件。需要注意的是在迴圈中初始化變數或呼叫函式而佔用的記憶體在進入下一迴圈後就會被釋放因此不會累積佔用空間空間複雜度仍為 $O(1)$。對應源碼見 space_complexity.py 的constant()函式其中a 0、nums [0] * 10000、node ListNode(0)以及迴圈內的c 0與function()呼叫全部屬於 $O(1)$ 空間。def constant(n: int): 常數階 # 常數、變數、物件佔用 O(1) 空間 a 0 nums [0] * 10000 node ListNode(0) # 迴圈中的變數佔用 O(1) 空間 for _ in range(n): c 0 # 迴圈中的函式佔用 O(1) 空間 for _ in range(n): function()線性階 $O(n)$線性階常見於元素數量與 $n$ 成正比的陣列、鏈結串列、堆疊、佇列等。在 Python 實作 中長度為 $n$ 的列表nums、裝入 $n$ 個鍵值對的雜湊表hmap都佔用 $O(n)$ 空間C 版本space_complexity.cpp中則體現在vectorint nums(n)、vectorListNode nodes與unordered_mapint, string map。此外遞迴深度為 $n$ 的函式同樣產生 $O(n)$ 空間如下圖所示linear_recur()遞迴深度為 $n$即同時存在 $n$ 個未返回的linear_recur()函式使用 $O(n)$ 大小的堆疊幀空間平方階 $O(n^2)$平方階常見於矩陣和圖元素數量與 $n$ 成平方關係。典型例子是 $n \times n$ 的二維矩陣num_matrix [[0] * n for _ in range(n)]佔用 $O(n^2)$ 空間見 Python 實作。更值得關注的是遞迴版本quadratic_recur()該函式的遞迴深度為 $n$在每個遞迴函式中都初始化了一個陣列長度分別為 $n$、$n-1$、$\dots$、$2$、$1$平均長度為 $n / 2$因此總體佔用$$ \frac{n(n1)}{2} O(n^2) $$空間。也就是說即使每一層遞迴只分配一個 $O(n)$ 的陣列疊加起來也會形成 $O(n^2)$ 的總空間——這是遞迴空間分析中典型的「累積效應」陷阱def quadratic_recur(n: int) - int: 平方階遞迴實作 if n 0: return 0 # 陣列 nums 長度為 n, n-1, ..., 2, 1 nums [0] * n return quadratic_recur(n - 1)指數階 $O(2^n)$指數階常見於二元樹。層數為 $n$ 的「滿二元樹」的節點數量為$$ 2^0 2^1 \dots 2^{n-1} 2^n - 1 $$佔用 $O(2^n)$ 空間。build_tree()透過遞迴建立滿二元樹每個節點呼叫兩次build_tree(n - 1)分別建立左右子樹最終形成完整的指數級節點結構見 Python 實作 與 C 實作def build_tree(n: int) - TreeNode | None: 指數階建立滿二元樹 if n 0: return None root TreeNode(0) root.left build_tree(n - 1) root.right build_tree(n - 1) return root對數階 $O(\log n)$對數階常見於分治演算法。例如合併排序輸入長度為 $n$ 的陣列每輪遞迴將陣列從中點處劃分為兩半形成高度為 $\log n$ 的遞迴樹使用 $O(\log n)$ 堆疊幀空間。再例如將數字轉化為字串輸入一個正整數 $n$它的位數為 $\lfloor \log_{10} n \rfloor 1$即對應字串長度為 $\lfloor \log_{10} n \rfloor 1$因此空間複雜度為 $O(\log_{10} n 1) O(\log n)$。與線性階遞迴不同對數階遞迴每次問題規模減半遞迴樹高度僅為 $\log n$堆疊幀數量遠小於 $n$——這是分治策略在空間上的一大優勢。權衡時間與空間理想情況下我們希望演算法的時間複雜度和空間複雜度都能達到最優。然而在實際情況中同時最佳化時間複雜度和空間複雜度通常非常困難。降低時間複雜度通常需要以提升空間複雜度為代價反之亦然。我們將犧牲記憶體空間來提升演算法執行速度的思路稱為「以空間換時間」反之則稱為「以時間換空間」。經典例子是《Hello 算法》其他章節中的以雜湊表取代線性搜尋replace_linear_by_hashing.md透過額外建立一個 $O(n)$ 的雜湊表將兩數之和的查詢從 $O(n^2)$ 降到 $O(n)$正是以空間換時間的典型應用。選擇哪種思路取決於我們更看重哪個方面。在大多數情況下時間比空間更寶貴因此「以空間換時間」通常是更常用的策略例如快取、記憶化搜尋、動態規劃表。當然在資料量很大的情況下控制空間複雜度也非常重要——當 $n$ 達到百萬、千萬級別時$O(n^2)$ 的空間開銷會迅速耗盡記憶體此時空間約束反而成為演算法設計的首要瓶頸。動手實作與驗證倉庫為本章提供了完整的可執行源碼可以直接執行驗證上述所有結論Python運行 space_complexity.py其Driver Code依序呼叫constant(n)、linear(n)、linear_recur(n)、quadratic(n)、quadratic_recur(n)與build_tree(n)預設 $n 5$並透過print_tree輸出滿二元樹結構C編譯運行 space_complexity.cpp其 CMake 目標已配置於 chapter_computational_complexity/CMakeLists.txtmain()中還呼叫freeMemoryTree(root)演示了樹的記憶體釋放Java運行 space_complexity.javamain()中透過PrintUtil.printTree(root)列印樹結構C 語言版本可參見 space_complexity.cCMake 目標配置於 chapter_computational_complexity/CMakeLists.txt。建議動手修改n的值觀察遞迴深度與樹節點數量的變化體會空間隨 $n$ 增長的實際速率也可以將loop()與recur()對比運行親自驗證「時間相同、空間不同」的結論。小結空間複雜度是演算法分析不可或缺的另一半視角統計範圍為暫存空間加輸出空間其中暫存空間由暫存資料、堆疊幀空間與指令空間構成推算時以最差輸入與峰值記憶體為準並特別警惕遞迴呼叫帶來的堆疊幀累積常見型別按 $O(1) O(\log n) O(n) O(n^2) O(2^n)$ 遞增各有其典型資料結構與演算法場景。掌握了空間複雜度再結合《Hello 算法》時間複雜度章節 與 迭代與遞迴章節你就能從時間與空間兩個維度完整評估任意演算法的優劣為後續的資料結構與演算法學習打下堅實基礎。【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考