小結

演算法效率評估

時間複雜度

時間複雜度用於衡量演算法執行時間隨資料量增長的趨勢，可以有效評估演算法效率，但在某些情況下可能失效，如在輸入的資料量較小或時間複雜度相同時，無法精確對比演算法效率的優劣。
最差時間複雜度使用大 $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：函式和方法這兩個術語的區別是什麼？

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

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

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

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

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

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

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

Q 是否存在根據實際使用場景，選擇犧牲時間（或空間）來設計演算法的情況？

在實際應用中，大部分情況會選擇犧牲空間換時間。例如資料庫索引，我們通常選擇建立 B+ 樹或雜湊索引，佔用大量記憶體空間，以換取 $O(\log n)$ 甚至 $O(1)$ 的高效查詢。

在空間資源寶貴的場景，也會選擇犧牲時間換空間。例如在嵌入式開發中，裝置記憶體很寶貴，工程師可能會放棄使用雜湊表，選擇使用陣列順序查詢，以節省記憶體佔用，代價是查詢變慢。