在算法設(shè)計中，我們先后追求以下兩個層面的目標(biāo)。

1. 找到問題解法：算法需要在規(guī)定的輸入范圍內(nèi)，可靠地求得問題的正確解。
2. 尋求最優(yōu)解法：同一個問題可能存在多種解法，我們希望找到盡可能高效的算法。

也就是說，在能夠解決問題的前提下，算法效率已成為衡量算法優(yōu)劣的主要評價指標(biāo)，它包括以下兩個維度。

• 時間效率：算法運行速度的快慢。
• 空間效率：算法占用內(nèi)存空間的大小。

簡而言之，我們的目標(biāo)是設(shè)計“既快又省”的數(shù)據(jù)結(jié)構(gòu)與算法。而有效地評估算法效率至關(guān)重要，因為只有這樣我們才能將各種算法進(jìn)行對比，從而指導(dǎo)算法設(shè)計與優(yōu)化過程。

效率評估方法主要分為兩種：實際測試、理論估算。

實際測試

假設(shè)我們現(xiàn)在有算法 A 和算法 B ，它們都能解決同一問題，現(xiàn)在需要對比這兩個算法的效率。最直接的方法是找一臺計算機(jī)，運行這兩個算法，并監(jiān)控記錄它們的運行時間和內(nèi)存占用情況。這種評估方式能夠反映真實情況，但也存在較大局限性。

一方面，難以排除測試環(huán)境的干擾因素。硬件配置會影響算法的性能表現(xiàn)。比如在某臺計算機(jī)中，算法 A 的運行時間比算法 B 短；但在另一臺配置不同的計算機(jī)中，我們可能得到相反的測試結(jié)果。這意味著我們需要在各種機(jī)器上進(jìn)行測試，統(tǒng)計平均效率，而這是不現(xiàn)實的。

另一方面，展開完整測試非常耗費資源。隨著輸入數(shù)據(jù)量的變化，算法會表現(xiàn)出不同的效率。例如，在輸入數(shù)據(jù)量較小時，算法 A 的運行時間比算法 B 更少；而輸入數(shù)據(jù)量較大時，測試結(jié)果可能恰恰相反。因此，為了得到有說服力的結(jié)論，我們需要測試各種規(guī)模的輸入數(shù)據(jù)，而這需要耗費大量的計算資源。

理論估算

由于實際測試具有較大的局限性，我們可以考慮僅通過一些計算來評估算法的效率。這種估算方法被稱為「漸近復(fù)雜度分析 asymptotic complexity analysis」，簡稱「復(fù)雜度分析」。

復(fù)雜度分析體現(xiàn)算法運行所需的時間（空間）資源與輸入數(shù)據(jù)大小之間的關(guān)系。它描述了隨著輸入數(shù)據(jù)大小的增加，算法執(zhí)行所需時間和空間的增長趨勢。這個定義有些拗口，我們可以將其分為三個重點來理解。

• “時間和空間資源”分別對應(yīng)「時間復(fù)雜度 time complexity」和「空間復(fù)雜度 space complexity」。
• “隨著輸入數(shù)據(jù)大小的增加”意味著復(fù)雜度反映了算法運行效率與輸入數(shù)據(jù)體量之間的關(guān)系。
• “時間和空間的增長趨勢”表示復(fù)雜度分析關(guān)注的不是運行時間或占用空間的具體值，而是時間或空間增長的“快慢”。

復(fù)雜度分析克服了實際測試方法的弊端，體現(xiàn)在以下兩個方面。

• 它獨立于測試環(huán)境，分析結(jié)果適用于所有運行平臺。
• 它可以體現(xiàn)不同數(shù)據(jù)量下的算法效率，尤其是在大數(shù)據(jù)量下的算法性能。

Tip

如果你仍對復(fù)雜度的概念感到困惑，無須擔(dān)心，我們會在后續(xù)章節(jié)中詳細(xì)介紹。

復(fù)雜度分析為我們提供了一把評估算法效率的“標(biāo)尺”，使我們可以衡量執(zhí)行某個算法所需的時間和空間資源，對比不同算法之間的效率。

復(fù)雜度是個數(shù)學(xué)概念，對于初學(xué)者可能比較抽象，學(xué)習(xí)難度相對較高。從這個角度看，復(fù)雜度分析可能不太適合作為最先介紹的內(nèi)容。然而，當(dāng)我們討論某個數(shù)據(jù)結(jié)構(gòu)或算法的特點時，難以避免要分析其運行速度和空間使用情況。

綜上所述，建議你在深入學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法之前，先對復(fù)雜度分析建立初步的了解，以便能夠完成簡單算法的復(fù)雜度分析。