企业官网建设流程全解析

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

本文是《Hello 算法》计算复杂度章节的总结篇，系统梳理演算法效率評估的兩大維度、時間複雜度與空間複雜度的核心概念與推算方法，並結合倉庫內多語言可執行示例，幫助你建立一套可應用於日常程式設計與面試的複雜度分析框架。讀完本文，你將掌握大 $O$ 記號的數學含義、複雜度推算的兩步法、常見複雜度型別的判別，以及「以空間換時間」等工程取捨的判斷依據。

演算法效率評估：時間與空間兩個維度

在演算法設計中，我們先後追求兩個層面的目標：找到問題解法（在規定輸入範圍內可靠地求得正確解），以及尋求最優解法（在同問題的多種解法中，找到儘可能高效的一種）。在能解決問題的前提下，演算法效率成為衡量演算法優劣的主要評價指標，它包含兩個維度：

• 時間效率：演算法執行時間的長短。
• 空間效率：演算法佔用記憶體空間的大小。

簡而言之，目標是設計「既快又省」的資料結構與演算法。效率評估方法主要分為兩種：實際測試與理論估算，對應的詳細論述可參見演算法效率評估。

實際測試的侷限性

假設演算法A和B都能解決同一問題，最直接的對比方式是找一臺計算機執行兩者，監控執行時間與記憶體佔用。但這種方式存在兩大弊端：

1. 難以排除測試環境的干擾：硬體配置影響效能表現——並行度高的演算法更適合多核 CPU，記憶體操作密集的演算法在高效能記憶體上表現更好。演算法在不同機器上的測試結果可能不一致，意味著需要在各種機器上統計平均效率，這不現實。
2. 完整測試非常耗費資源：輸入資料量變化時演算法效率不同。資料量小時演算法A可能更快，資料量大時可能相反。為得到有說服力的結論，需要測試各種規模的輸入資料，耗費大量計算資源。

理論估算：複雜度分析

由於實際測試侷限性大，可以僅透過計算評估演算法效率，這種方法稱為漸近複雜度分析（asymptotic complexity analysis），簡稱複雜度分析。它描述隨著輸入資料規模的增加，演算法執行所需時間和空間的增長趨勢，有三個重點：

• 「時間和空間資源」分別對應時間複雜度（time complexity）與空間複雜度（space complexity）；
• 「隨著輸入資料規模的增加」意味著複雜度反映效率與輸入規模之間的關係；
• 「增長趨勢」表示複雜度分析關注的不是具體值，而是增長「快慢」。

複雜度分析克服了實際測試的弊端：無需實際執行程式碼、獨立於測試環境（結果適用於所有執行平臺）、能體現不同資料量（尤其大資料量）下的演算法效率。

時間複雜度：衡量執行時間的增長趨勢

時間複雜度用於衡量演算法執行時間隨資料量增長的趨勢，可以有效評估演算法效率，但在某些情況下可能失效——例如輸入資料量較小、或兩個演算法時間複雜度相同時，無法精確對比效率優劣。

為何不直接統計執行時間

理論上可以透過「確定執行平臺 → 評估各計算操作執行時間 → 統計所有操作時間求和」三步得到執行時間。例如某平臺下a = 2需 1 ns、a = a * 2需 10 ns、迴圈內print(0)需 5 ns，一個含n次迴圈的函式執行時間為 $(6n + 12)$ ns。但這樣做既不合理也不現實：

• 不希望將預估時間與執行平臺繫結（演算法需在多種平臺執行）；
• 很難獲知每種操作的執行時間。

因此時間複雜度分析統計的不是執行時間，而是執行時間隨資料量變大時的增長趨勢。

大 O 記號與漸近上界

設操作數量是關於輸入資料大小 $n$ 的函式 $T(n)$，例如 $T(n) = 3 + 2n$ 是一次函式，說明執行時間呈線性增長，其時間複雜度為線性階，記為 $O(n)$。這個數學符號稱為大 $O$ 記號（big-$O$ notation），表示函式 $T(n)$ 的漸近上界（asymptotic upper bound），反映當 $n$ 趨向正無窮時操作數量 $T(n)$ 的增長級別。

其數學定義為：若存在正實數 $c$ 和實數 $n_0$，使得對於所有 $n > n_0$ 均有 $T(n) \leq c \cdot f(n)$，則 $f(n)$ 給出了 $T(n)$ 的一個漸近上界，記為 $T(n) = O(f(n))$。最差時間複雜度使用大 $O$ 符號表示。

推算方法：統計操作數量 + 判斷漸近上界

推算時間複雜度分為兩步：首先統計操作數量，然後判斷漸近上界。

第一步：統計操作數量。逐行從上到下計算，由於 $c \cdot f(n)$ 中常數係數 $c$ 可任意取大小，因此 $T(n)$ 中的係數、常數項都可忽略，總結出三條計數簡化技巧：

1. 忽略常數：與 $n$ 無關的項不影響時間複雜度；
2. 省略所有係數：迴圈 $2n$ 次、$5n + 1$ 次都簡化記為 $n$ 次；
3. 迴圈巢狀時使用乘法：總操作數量等於外層與內層迴圈操作數量之積。

以一個含單層迴圈與雙層巢狀迴圈的函式為例，完整統計 $T(n) = 2n^2 + 7n + 3$，簡化後 $T(n) = n^2 + n$，兩者推算出的時間複雜度均為 $O(n^2)$。

第二步：判斷漸近上界。時間複雜度由 $T(n)$ 中最高階的項決定，因為 $n$ 趨於無窮大時最高階項發揮主導作用。下表展示不同操作數量對應的時間複雜度（強調「係數無法撼動階數」）：

常見時間複雜度型別

常見時間複雜度從低到高排列為：$O(1)$、$O(\log n)$、$O(n)$、$O(n \log n)$、$O(n^2)$、$O(2^n)$、$O(n!)$。核心特徵如下：

• 常數階 $O(1)$：操作數量與 $n$ 無關。即使size很大（如迴圈 100000 次），只要與 $n$ 無關，複雜度仍為 $O(1)$。
• 線性階 $O(n)$：單層迴圈，或走訪陣列、鏈結串列（$n$ 為陣列/鏈結串列長度）。注意輸入資料大小 $n$ 需根據輸入資料型別具體確定。
• 平方階 $O(n^2)$：巢狀迴圈。以泡沫排序為例，外層迴圈 $n-1$ 次，內層平均 $n/2$ 次，時間複雜度 $O((n-1)n/2) = O(n^2)$。
• 指數階 $O(2^n)$：如「細胞分裂」模擬與一分為二的遞迴。增長極快，常出現於窮舉法（暴力搜尋、回溯），大規模資料下不可接受，通常需動態規劃或貪婪演算法。
• 對數階 $O(\log n)$：反映「每輪縮減到一半」。注意底數可透過換底公式轉換：$O(\log_m n) = O(\log_k n / \log_k m) = O(\log_k n)$，因此通常省略底數直接記為 $O(\log n)$。增長緩慢，僅次於常數階。
• 線性對數階 $O(n \log n)$：巢狀迴圈（$O(\log n)$ × $O(n)$）或二元樹分層操作。快速排序、合併排序、堆積排序等主流排序演算法均為此複雜度。
• 階乘階 $O(n!)$：對應全排列問題，$n! = n \times (n-1) \times \dots \times 2 \times 1$，通常以遞迴實現。因 $n \geq 4$ 時恆有 $n! > 2^n$，比指數階增長更快。

最差、最佳與平均時間複雜度

演算法時間效率往往不固定，而是與輸入資料分佈有關。以在長度為 $n$ 的亂序陣列中查找元素 $1$ 的索引為例：

• 元素 $1$ 在陣列末尾時需完整走訪，達到最差時間複雜度 $O(n)$；
• 元素 $1$ 在陣列首部時立即返回，達到最佳時間複雜度 $\Omega(1)$。

「最差時間複雜度」對應漸近上界（大 $O$ 記號），「最佳時間複雜度」對應漸近下界（$\Omega$ 記號）。實際中很少使用最佳時間複雜度——只有很小機率能達到，可能帶來誤導；最差時間複雜度更實用，因為它給出效率安全值。

平均時間複雜度反映演算法在隨機資料輸入下的執行效率，用 $\Theta$ 記號表示，最接近實際應用效能，但計算平均時間複雜度需要統計輸入資料分佈以及綜合後的數學期望，對複雜演算法往往較困難。例如上述查找示例中，元素 $1$ 出現在任意索引機率相等，平均迴圈次數為 $n/2$，平均時間複雜度為 $\Theta(n)$。注意：因 $O$ 符號朗朗上口，常被用來表示平均時間複雜度，嚴格意義上應理解為 $\Theta$。

在倉庫中，worst_best_time_complexity.py 完整實現了上述場景：random_numbers()生成打亂順序的陣列，find_one()從頭掃描返回元素1的索引，其註釋明確指出「元素 1 在陣列頭部時達到最佳時間複雜度 O(1)，在尾部時達到最差時間複雜度 O(n)」。你可以直接執行該文件觀察多次隨機結果。

空間複雜度：衡量記憶體佔用的增長趨勢

空間複雜度（space complexity）用於衡量演算法佔用記憶體空間隨資料量變大時的增長趨勢，與時間複雜度概念類似，只需將「執行時間」替換為「佔用記憶體空間」。

演算法相關空間的組成

演算法執行過程中的相關記憶體空間可分為三類：

• 輸入空間：儲存演算法的輸入資料。通常情況下輸入空間不納入空間複雜度計算。
• 暫存空間：儲存執行過程中的變數、物件、函式上下文等資料，可進一步劃分為：
  • 暫存資料：執行過程中的各種常數、變數、物件；
  • 堆疊幀空間：每次呼叫函式時在堆疊頂部建立的上下文資料，函式返回後釋放，通常僅在遞迴函式中影響空間複雜度；
  • 指令空間：儲存編譯後的程式指令，實際統計中通常忽略。
• 輸出空間：儲存輸出資料。

一般情況下，空間複雜度的統計範圍是「暫存空間」加上「輸出空間」，即統計暫存資料、堆疊幀空間和輸出資料三部分。

推算方法：只關注最差空間複雜度

空間複雜度推算方法與時間複雜度大致相同，只需將統計物件從「操作數量」轉為「使用空間大小」。與時間複雜度不同的是，通常只關注最差空間複雜度，因為記憶體空間是硬性要求，必須確保在所有輸入資料下都有足夠的記憶體預留。「最差」有兩層含義：

1. 以最差輸入資料為準：當 $n < 10$ 時空間複雜度為 $O(1)$；但 $n > 10$ 時初始化的陣列nums佔用 $O(n)$ 空間，因此最差空間複雜度為 $O(n)$。
2. 以演算法執行中的峰值記憶體為準：程式執行最後一行之前佔用 $O(1)$ 空間；初始化陣列nums時佔用 $O(n)$ 空間。

遞迴函式中需注意統計堆疊幀空間。對比迴圈與遞迴：函式loop()在迴圈中呼叫 $n$ 次function()，每輪返回即釋放堆疊幀空間，空間複雜度仍為 $O(1)$；而遞迴函式recur()執行過程中會同時存在 $n$ 個未返回的呼叫，佔用 $O(n)$ 堆疊幀空間。

常見空間複雜度型別

常見空間複雜度從低到高排列為：$O(1)$、$O(\log n)$、$O(n)$、$O(n^2)$、$O(2^n)$。

• 常數階 $O(1)$：數量與 $n$ 無關的常數、變數、物件。迴圈中初始化變數或呼叫函式佔用的記憶體，進入下一迴圈後即釋放，不會累積，空間複雜度仍為 $O(1)$。
• 線性階 $O(n)$：元素數量與 $n$ 成正比的陣列、鏈結串列、堆疊、佇列；遞迴深度為 $n$ 時同時存在 $n$ 個未返回的函式，使用 $O(n)$ 堆疊幀空間。
• 平方階 $O(n^2)$：矩陣和圖。遞迴深度為 $n$、每層初始化長度為 $n, n-1, \dots, 1$ 的陣列，平均長度 $n/2$，總體佔用 $O(n^2)$ 空間。
• 指數階 $O(2^n)$：二元樹。層數為 $n$ 的滿二元樹節點數為 $2^n - 1$。
• 對數階 $O(\log n)$：分治演算法。例如合併排序每輪從中點劃分陣列，形成高度為 $\log n$ 的遞迴樹；又如正整數 $n$ 轉字串，位數為 $\lfloor \log_{10} n \rfloor + 1$，空間複雜度 $O(\log_{10} n + 1) = O(\log n)$。

程式碼層面的實際印證

《Hello 算法》的每章節都配備了可一鍵執行的多語言代碼，計算複雜度章節的 Python 實現集中在 chapter_computational_complexity，是驗證上述理論的最佳工具。

時間複雜度示例的執行效果

time_complexity.py 依次實現了常數階constant()、線性階linear()與array_traversal()、平方階quadratic()與bubble_sort()、指數階exponential()與exp_recur()、對數階logarithmic()與log_recur()、線性對數階linear_log_recur()、階乘階factorial_recur()，並在Driver Code中以n = 8統一執行並列印各複雜度的操作數量。你可以修改n執行，直觀體會不同複雜度下操作數量的增長差異：

• constant(8)恆返回 100000，與n無關；
• linear(8)返回 8，隨n線性增長；
• quadratic(8)返回 64，呈平方增長；
• exponential(8)返回 $2^8 - 1 = 255$，增長遠超線性；
• factorial_recur(8)對應全排列數量，增長最為劇烈。

其中bubble_sort()的實現值得注意：內迴圈在nums[j] > nums[j + 1]時交換元素並count += 3（元素交換包含 3 個單元操作），完整詮釋了平方階操作數量的統計過程。

空間複雜度示例的執行效果

space_complexity.py 依次實現了常數階constant()、線性階linear()與linear_recur()、平方階quadratic()與quadratic_recur()、指數階build_tree()（建立滿二元樹）。以n = 5執行時：

• constant()中迴圈內的變數c與函式function()每輪即釋放，空間複雜度為 $O(1)$；
• linear_recur()遞迴深度為 $n$，同時存在 $n$ 個未返回呼叫，佔用 $O(n)$ 堆疊幀空間；
• quadratic_recur()每層初始化長度遞減的陣列，總體 $O(n^2)$；
• build_tree()建立滿二元樹，節點數 $2^n - 1$，佔用 $O(2^n)$ 空間。

總結與常見問題解答

重點回顧

• 時間效率和空間效率是衡量演算法優劣的兩個主要評價指標；實際測試難以消除測試環境影響且耗費資源，複雜度分析結果適用於所有執行平臺，並能揭示演算法在不同資料規模下的效率。
• 時間複雜度衡量執行時間隨資料量增長的趨勢；最差時間複雜度使用大 $O$ 符號表示（漸近上界）；推算分「統計操作數量」與「判斷漸近上界」兩步；某些演算法時間複雜度與輸入資料分佈有關，分為最差、最佳、平均三種，最佳幾乎不用。
• 平均時間複雜度反映隨機資料輸入下的執行效率，最接近實際應用；計算需統計輸入資料分佈及綜合後的數學期望。
• 空間複雜度作用類似時間複雜度；相關記憶體分為輸入空間、暫存空間、輸出空間，輸入空間通常不納入計算；通常只關注最差空間複雜度。

尾遞迴的空間複雜度是 O(1) 嗎？

理論上，尾遞迴函式的空間複雜度可以最佳化至 $O(1)$。不過絕大多數程式語言（如 Java、Python、C++、Go、C# 等）不支援自動最佳化尾遞迴，因此通常認為空間複雜度是 $O(n)$。關於遞迴與迭代的深入對比，可參見迭代與遞迴，其中 recursion.py 提供了普通遞迴、顯式棧模擬、尾遞迴tail_recur()與費氏數列四種實現，便於對照觀察呼叫棧的差異。

函式與方法這兩個術語的區別是什麼？

函式（function）可以被獨立執行，所有參數都以顯式傳遞。方法（method）與一個物件關聯，被隱式傳遞給呼叫它的物件，能對類別實例中的資料進行操作。以幾種常見程式語言為例：

• C 語言是程序式語言，沒有物件導向概念，所以只有函式。但可透過建立結構體（struct）模擬物件導向程式設計，與結構體相關聯的函式相當於其他語言中的方法。
• Java 和 C#是物件導向語言，程式碼塊（方法）通常作為類別的一部分。靜態方法行為類似函式，因為它繫結在類別上，不能訪問特定例項變數。
• C++ 和 Python既支援程序式程式設計（函式），也支援物件導向程式設計（方法）。

複雜度圖反映的是佔用空間的絕對大小嗎？

不是。「常見的空間複雜度型別」圖展示的是增長趨勢，而非絕對大小。假設取 $n = 8$，你可能發現每條曲線的值與函式對不上，這是因為每條曲線都包含一個常數項，用於將取值範圍壓縮到視覺舒適的範圍。實際中通常不知道每個方法的「常數項」複雜度，因此一般無法僅憑複雜度選擇 $n = 8$ 之下的最優解法；但對於 $n = 8^5$ 就很好選了，此時增長趨勢已佔主導。

是否存在犧牲時間（或空間）來設計演算法的情況？

存在，這是工程中的常見取捨：

• 以空間換時間：實際應用中大部分情況選擇此策略。例如資料庫索引通常建立 B+ 樹或雜湊索引，佔用大量記憶體空間，以換取 $O(\log n)$ 甚至 $O(1)$ 的高效查詢。
• 以時間換空間：在空間資源寶貴的場景採用。例如嵌入式開發中裝置記憶體寶貴，工程師可能放棄雜湊表，改用陣列順序查詢以節省記憶體，代價是查詢變慢。

理想情況下希望時間與空間複雜度都達最優，但同時最佳化通常非常困難：降低時間複雜度往往以提升空間複雜度為代價，反之亦然。選擇哪種思路取決於更看重哪個方面——多數情況下時間比空間更寶貴，「以空間換時間」更常用；而資料量很大時，控制空間複雜度也非常重要。

延伸學習

本章還提供了習題用於鞏固，以及完整的章節入口。除 Python 外，同一套示例還覆蓋 C、C++、Java、C#、Go、Swift、JavaScript、TypeScript、Dart、Rust、Kotlin、Ruby 等多種語言（如 chapter_computational_complexity 下的 C++ 實現），便於在不同技術棧中對照學習。建議在深入學習各資料結構與演算法之前，先對複雜度分析建立初步瞭解，以便能獨立完成簡單演算法的複雜度分析。

【免费下载链接】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