C++算法效率評(píng)估

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

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

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

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

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

效率評(píng)估方法主要分為兩種：實(shí)際測(cè)試、理論估算。

實(shí)際測(cè)試

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

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

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

理論估算

由于實(shí)際測(cè)試具有較大的局限性，我們可以考慮僅通過(guò)一些計(jì)算來(lái)評(píng)估算法的效率。這種估算方法被稱(chēng)為「漸近復(fù)雜度分析 asymptotic complexity analysis」，簡(jiǎn)稱(chēng)「復(fù)雜度分析」。

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

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

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

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

Tip

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

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

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

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