2.5 小結¶

演算法效率評估

時間複雜度

時間複雜度用於衡量演算法執行時間隨資料量增長的趨勢，可以有效評估演算法效率，但在某些情況下可能失效，如在輸入的資料量較小或時間複雜度相同時，無法精確對比演算法效率的優劣。
最差時間複雜度使用大 \(O\) 符號表示，對應函式漸近上界，反映當 \(n\) 趨向正無窮時，操作數量 \(T(n)\) 的增長級別。
推算時間複雜度分為兩步，首先統計操作數量，然後判斷漸近上界。
常見時間複雜度從低到高排列有 \(O(1)\)、\(O(\log n)\)、\(O(n)\)、\(O(n \log n)\)、\(O(n^2)\)、\(O(2^n)\) 和 \(O(n!)\) 等。
某些演算法的時間複雜度非固定，而是與輸入資料的分佈有關。時間複雜度分為最差、最佳、平均時間複雜度，最佳時間複雜度幾乎不用，因為輸入資料一般需要滿足嚴格條件才能達到最佳情況。
平均時間複雜度反映演算法在隨機資料輸入下的執行效率，最接近實際應用中的演算法效能。計算平均時間複雜度需要統計輸入資料分佈以及綜合後的數學期望。

空間複雜度

空間複雜度的作用類似於時間複雜度，用於衡量演算法佔用記憶體空間隨資料量增長的趨勢。
演算法執行過程中的相關記憶體空間可分為輸入空間、暫存空間、輸出空間。通常情況下，輸入空間不納入空間複雜度計算。暫存空間可分為暫存資料、堆疊幀空間和指令空間，其中堆疊幀空間通常僅在遞迴函式中影響空間複雜度。
我們通常只關注最差空間複雜度，即統計演算法在最差輸入資料和最差執行時刻下的空間複雜度。
常見空間複雜度從低到高排列有 \(O(1)\)、\(O(\log n)\)、\(O(n)\)、\(O(n^2)\) 和 \(O(2^n)\) 等。

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

理論上，尾遞迴函式的空間複雜度可以最佳化至 \(O(1)\) 。不過絕大多數程式語言（例如 Java、Python、C++、Go、C# 等）不支持自動最佳化尾遞迴，因此通常認為空間複雜度是 \(O(n)\) 。

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

函式（function）可以被獨立執行，所有參數都以顯式傳遞。方法（method）與一個物件關聯，被隱式傳遞給呼叫它的物件，能夠對類別的例項中包含的資料進行操作。

下面以幾種常見的程式語言為例來說明。

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

Q：圖解“常見的空間複雜度型別”反映的是否是佔用空間的絕對大小？

不是，該圖展示的是空間複雜度，其反映的是增長趨勢，而不是佔用空間的絕對大小。

假設取 \(n = 8\) ，你可能會發現每條曲線的值與函式對應不上。這是因為每條曲線都包含一個常數項，用於將取值範圍壓縮到一個視覺舒適的範圍內。

在實際中，因為我們通常不知道每個方法的“常數項”複雜度是多少，所以一般無法僅憑複雜度來選擇 \(n = 8\) 之下的最優解法。但對於 \(n = 8^5\) 就很好選了，這時增長趨勢已經佔主導了。