C語(yǔ)言 如何衡量算法的優(yōu)劣

如何來(lái)衡量一個(gè)算法的好壞，通常要從以下幾個(gè)方面來(lái)分析，如圖所示。

1.正確性

    正確性是指所寫(xiě)的算法能滿足具體問(wèn)題的要求，即對(duì)任何合法的輸入，算法都會(huì)得出正確的結(jié)果。

2.可讀性

    可讀性是指算法被寫(xiě)好之后，該算法被理解的難易程度。一個(gè)算法可讀性的好壞十分重要，如果一個(gè)算法比較抽象，難于理解，那么這個(gè)算法就不易交流和推廣，對(duì)于修改、擴(kuò)展、維護(hù)都十分不利。所 以在寫(xiě)算法的時(shí)候，要盡量將該算法寫(xiě)得簡(jiǎn)明易懂。

3.健壯性

    —個(gè)程序完成后，運(yùn)行該程序的用戶對(duì)程序的理解因人而異，并不能保證每個(gè)人都能按照要求進(jìn)行輸入，健壯性就是指當(dāng)輸入的數(shù)據(jù)非法時(shí)，算法也會(huì)做出相應(yīng)的判斷，而不會(huì)因?yàn)檩斎氲腻e(cuò)誤造成程序癱瘓。

4.時(shí)間復(fù)雜度與空間復(fù)雜度

    時(shí)間復(fù)雜度，簡(jiǎn)單地說(shuō)就是算法運(yùn)行所需要的時(shí)間。一個(gè)程序在計(jì)算機(jī)中運(yùn)行時(shí)間的長(zhǎng)短與很多因素相關(guān)，這些因素主要有：

    ?問(wèn)題規(guī)模的大小。例如，求10的階乘和求100的階乘所花費(fèi)的時(shí)間是有明顯差異的，顯然，求100的階乘所花費(fèi)的時(shí)間要比求10的階乘花費(fèi)的時(shí)間多得多。

    ?源程序編譯功能的強(qiáng)弱以及經(jīng)過(guò)編譯后產(chǎn)生的機(jī)器代碼質(zhì)量的優(yōu)劣。

    ?機(jī)器執(zhí)行一條目標(biāo)指令所需要的時(shí)間。這個(gè)因素是與計(jì)算機(jī)系統(tǒng)的硬件息息相關(guān)的，隨著硬件技術(shù)的提高，硬件性能越來(lái)越好，執(zhí)行一條目標(biāo)指令所花費(fèi)的時(shí)間也會(huì)相應(yīng)地越來(lái)越少。

    ?程序中語(yǔ)句的執(zhí)行次數(shù)。這個(gè)因素與算法本身有直接關(guān)系，一個(gè)好的算法應(yīng)該使程序中語(yǔ)句執(zhí)行次數(shù)盡量少。

由于同一個(gè)算法使用不同的計(jì)算機(jī)語(yǔ)言實(shí)現(xiàn)的效率會(huì)不相同，使用不同的編譯器編譯效率也不相同，運(yùn)行于不同的計(jì)算機(jī)系統(tǒng)中效率也不相同，因此使用前3個(gè)因素來(lái)衡量一個(gè)算法的時(shí)間復(fù)雜度通常是不恰當(dāng)?shù)?。因此我們使用?個(gè)因素，即將程序中語(yǔ)句的執(zhí)行次數(shù)作為一個(gè)算法的時(shí)間復(fù)雜度的度量。

    不同的算法具有不同的時(shí)間復(fù)雜度，當(dāng)一個(gè)程序較小時(shí)，往往感覺(jué)不到時(shí)間復(fù)雜度的重要性，當(dāng)一個(gè)程序特別大時(shí)，便會(huì)察覺(jué)到時(shí)間復(fù)雜度實(shí)際上是十分重要的，所以如何寫(xiě)出更高速的算法一直是算法不斷改進(jìn)的目標(biāo)。

    空間復(fù)雜度是指算法運(yùn)行所需的存儲(chǔ)空間的大小。一個(gè)算法在計(jì)算機(jī)存儲(chǔ)器上所占用的存儲(chǔ)空間包括算法本身所占的存儲(chǔ)空間、算法的輸入/輸出數(shù)據(jù)所占的存儲(chǔ)空間，以及算法運(yùn)行過(guò)程中所占用的臨時(shí)存儲(chǔ)空間。隨著計(jì)算機(jī)硬件的發(fā)展，空間復(fù)雜度已經(jīng)顯得不再那么重要了，但在編程時(shí)也應(yīng)該注意。