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

1.   重點(diǎn)回顧

算法效率評(píng)估

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

時(shí)間復(fù)雜度

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

空間復(fù)雜度

• 空間復(fù)雜度的作用類似于時(shí)間復(fù)雜度，用于衡量算法占用空間隨數(shù)據(jù)量增長(zhǎng)的趨勢(shì)。
• 算法運(yùn)行過(guò)程中的相關(guān)內(nèi)存空間可分為輸入空間、暫存空間、輸出空間。通常情況下，輸入空間不計(jì)入空間復(fù)雜度計(jì)算。暫存空間可分為指令空間、數(shù)據(jù)空間、棧幀空間，其中棧幀空間通常僅在遞歸函數(shù)中影響空間復(fù)雜度。
• 我們通常只關(guān)注最差空間復(fù)雜度，即統(tǒng)計(jì)算法在最差輸入數(shù)據(jù)和最差運(yùn)行時(shí)間點(diǎn)下的空間復(fù)雜度。
• 常見(jiàn)空間復(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) 。不過(guò)絕大多數(shù)編程語(yǔ)言（例如 Java、Python、C++、Go、C# 等）都不支持自動(dòng)優(yōu)化尾遞歸，因此通常認(rèn)為空間復(fù)雜度是 O(n) 。

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

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

下面以幾個(gè)常見(jiàn)的編程語(yǔ)言來(lái)說(shuō)明。

• C 語(yǔ)言是過(guò)程式編程語(yǔ)言，沒(méi)有面向?qū)ο蟮母拍睿灾挥泻瘮?shù)。但我們可以通過(guò)創(chuàng)建結(jié)構(gòu)體（struct）來(lái)模擬面向?qū)ο缶幊蹋c結(jié)構(gòu)體相關(guān)聯(lián)的函數(shù)就相當(dāng)于其他語(yǔ)言中的方法。
• Java 和 C# 是面向?qū)ο蟮木幊陶Z(yǔ)言，代碼塊（方法）通常都是作為某個(gè)類的一部分。靜態(tài)方法的行為類似于函數(shù)，因?yàn)樗唤壎ㄔ陬惿希荒茉L問(wèn)特定的實(shí)例變量。
• C++ 和 Python 既支持過(guò)程式編程（函數(shù)），也支持面向?qū)ο缶幊蹋ǚ椒ǎ?/li>

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

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

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

在實(shí)際中，因?yàn)槲覀兺ǔ２恢烂總€(gè)方法的“常數(shù)項(xiàng)”復(fù)雜度是多少，所以一般無(wú)法僅憑復(fù)雜度來(lái)選擇 n=8 之下的最優(yōu)解法。但對(duì)于 n=8^5 就很好選了，這時(shí)增長(zhǎng)趨勢(shì)已經(jīng)占主導(dǎo)了。