C++算法效率評估

在算法設計中，我們先后追求以下兩個層面的目標。

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

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

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

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

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

實際測試

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

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

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

理論估算

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

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

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

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

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

Tip

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

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

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

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