復(fù)雜度分析小結(jié)

1.   重點回顧

算法效率評估

• 時間效率和空間效率是衡量算法優(yōu)劣的兩個主要評價指標。
• 我們可以通過實際測試來評估算法效率，但難以消除測試環(huán)境的影響，且會耗費大量計算資源。
• 復(fù)雜度分析可以克服實際測試的弊端，分析結(jié)果適用于所有運行平臺，并且能夠揭示算法在不同數(shù)據(jù)規(guī)模下的效率。

時間復(fù)雜度

• 時間復(fù)雜度用于衡量算法運行時間隨數(shù)據(jù)量增長的趨勢，可以有效評估算法效率，但在某些情況下可能失效，如在輸入的數(shù)據(jù)量較小或時間復(fù)雜度相同時，無法精確對比算法效率的優(yōu)劣。
• 最差時間復(fù)雜度使用大 O 符號表示，對應(yīng)函數(shù)漸近上界，反映當 n 趨向正無窮時，操作數(shù)量 T(n) 的增長級別。
• 推算時間復(fù)雜度分為兩步，首先統(tǒng)計操作數(shù)量，然后判斷漸近上界。
• 常見時間復(fù)雜度從小到大排列有 O(1)、O(log? n)、O(n)、O(nlog?n)、O(n2)、O(2^n) 和 O(n!) 等。
• 某些算法的時間復(fù)雜度非固定，而是與輸入數(shù)據(jù)的分布有關(guān)。時間復(fù)雜度分為最差、最佳、平均時間復(fù)雜度，最佳時間復(fù)雜度幾乎不用，因為輸入數(shù)據(jù)一般需要滿足嚴格條件才能達到最佳情況。
• 平均時間復(fù)雜度反映算法在隨機數(shù)據(jù)輸入下的運行效率，最接近實際應(yīng)用中的算法性能。計算平均時間復(fù)雜度需要統(tǒng)計輸入數(shù)據(jù)分布以及綜合后的數(shù)學期望。

空間復(fù)雜度

• 空間復(fù)雜度的作用類似于時間復(fù)雜度，用于衡量算法占用空間隨數(shù)據(jù)量增長的趨勢。
• 算法運行過程中的相關(guān)內(nèi)存空間可分為輸入空間、暫存空間、輸出空間。通常情況下，輸入空間不計入空間復(fù)雜度計算。暫存空間可分為指令空間、數(shù)據(jù)空間、棧幀空間，其中棧幀空間通常僅在遞歸函數(shù)中影響空間復(fù)雜度。
• 我們通常只關(guān)注最差空間復(fù)雜度，即統(tǒng)計算法在最差輸入數(shù)據(jù)和最差運行時間點下的空間復(fù)雜度。
• 常見空間復(fù)雜度從小到大排列有 O(1)、O(log?n)、O(n)、O(n2) 和 O(2^n) 等。

2.   Q & A

尾遞歸的空間復(fù)雜度是 O(1) 嗎？

理論上，尾遞歸函數(shù)的空間復(fù)雜度可以被優(yōu)化至 O(1) 。不過絕大多數(shù)編程語言（例如 Java、Python、C++、Go、C# 等）都不支持自動優(yōu)化尾遞歸，因此通常認為空間復(fù)雜度是 O(n) 。

函數(shù)和方法這兩個術(shù)語的區(qū)別是什么？

函數(shù)（function）可以被獨立執(zhí)行，所有參數(shù)都以顯式傳遞。方法（method）與一個對象關(guān)聯(lián)，被隱式傳遞給調(diào)用它的對象，能夠?qū)︻惖膶嵗邪臄?shù)據(jù)進行操作。

下面以幾個常見的編程語言來說明。

• C 語言是過程式編程語言，沒有面向?qū)ο蟮母拍?，所以只有函?shù)。但我們可以通過創(chuàng)建結(jié)構(gòu)體（struct）來模擬面向?qū)ο缶幊?，與結(jié)構(gòu)體相關(guān)聯(lián)的函數(shù)就相當于其他語言中的方法。
• Java 和 C# 是面向?qū)ο蟮木幊陶Z言，代碼塊（方法）通常都是作為某個類的一部分。靜態(tài)方法的行為類似于函數(shù)，因為它被綁定在類上，不能訪問特定的實例變量。
• C++ 和 Python 既支持過程式編程（函數(shù)），也支持面向?qū)ο缶幊蹋ǚ椒ǎ?/li>

圖“常見的空間復(fù)雜度類型”反映的是否是占用空間的絕對大?。?/p>

不是，該圖片展示的是空間復(fù)雜度，其反映的是增長趨勢，而不是占用空間的絕對大小。

假設(shè)取 n=8 ，你可能會發(fā)現(xiàn)每條曲線的值與函數(shù)對應(yīng)不上。這是因為每條曲線都包含一個常數(shù)項，用于將取值范圍壓縮到一個視覺舒適的范圍內(nèi)。

在實際中，因為我們通常不知道每個方法的“常數(shù)項”復(fù)雜度是多少，所以一般無法僅憑復(fù)雜度來選擇 n=8 之下的最優(yōu)解法。但對于 n=8^5 就很好選了，這時增長趨勢已經(jīng)占主導(dǎo)了。