1.4　算法的性能評(píng)價(jià)

算法其實(shí)就是解決問(wèn)題的一種方法，一個(gè)問(wèn)題的解決往往可以采用多種方法，但每種方法所用的時(shí)間和得到的效果往往是不一樣的。從前面的統(tǒng)籌安排的例子可以看出，好的算法執(zhí)行效率高，所耗費(fèi)的時(shí)間短；差的算法則往往需要耗費(fèi)更多的時(shí)間，從而導(dǎo)致效率很低。

算法的一個(gè)重要任務(wù)便是找到合適的、效率最高的解決問(wèn)題的方法，即最好的算法。從理論上來(lái)講，這就需要對(duì)算法的性能有一個(gè)合理的評(píng)價(jià)。一個(gè)算法的優(yōu)劣往往通過(guò)算法復(fù)雜度來(lái)衡量，算法復(fù)雜度包括時(shí)間復(fù)雜度和空間復(fù)雜度兩個(gè)方面。

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

時(shí)間復(fù)雜度即通常所說(shuō)的算法執(zhí)行所需要耗費(fèi)的時(shí)間，時(shí)間越短，算法越好。一個(gè)算法執(zhí)行的時(shí)間往往無(wú)法精確估計(jì)，通常需要在實(shí)際的計(jì)算機(jī)中運(yùn)行才能夠知道。但是，也可以對(duì)算法代碼進(jìn)行估計(jì)，而得到算法的時(shí)間復(fù)雜度。

首先，算法代碼執(zhí)行的時(shí)間往往和算法代碼中語(yǔ)句執(zhí)行的數(shù)量有關(guān)。由于每條語(yǔ)句執(zhí)行都需要時(shí)間，語(yǔ)句執(zhí)行的次數(shù)越多，整個(gè)程序所耗費(fèi)的時(shí)間就越長(zhǎng)。因此，簡(jiǎn)短、精悍的算法程序往往執(zhí)行速度快。

另外，算法的時(shí)間復(fù)雜度還與問(wèn)題的規(guī)模有關(guān)。這方面在專門(mén)的算法分析中有詳細(xì)的分析，這里限于篇幅就不再詳述了。有興趣的讀者可以參閱算法分析相關(guān)的書(shū)籍。

1.4.2　空間復(fù)雜度

空間復(fù)雜度指的是算法程序在計(jì)算機(jī)中執(zhí)行所需要消耗的存儲(chǔ)空間?？臻g復(fù)雜度其實(shí)可以分為如下兩個(gè)方面：

?程序保存所需要的存儲(chǔ)空間，即程序的大小。

?程序在執(zhí)行過(guò)程中所需要消耗的存儲(chǔ)空間資源，如程序在執(zhí)行過(guò)程中的中間變量等。

一般來(lái)說(shuō)，程序的大小越小，執(zhí)行過(guò)程中消耗的資源越少，這個(gè)程序就越好。在算法分析中，空間復(fù)雜度有更為詳細(xì)的度量，這里限于篇幅就不再贅述了，有興趣的讀者可以閱讀相關(guān)的書(shū)籍。