1.2.9 為算法寫代碼
1.2.9 為算法寫代碼
絕大多數(shù)算法注定最終以計(jì)算機(jī)程序的形式實(shí)現(xiàn)。為算法編程既是挑戰(zhàn)，也是機(jī)遇。挑戰(zhàn)在于，為算法編寫的程序可能出現(xiàn)錯(cuò)誤或者效率低下。一些有影響的計(jì)算機(jī)科學(xué)家堅(jiān)信，除非計(jì)算機(jī)程序的正確性能夠以數(shù)學(xué)的嚴(yán)密性來(lái)證明，否則我們不能認(rèn)為程序是正確的。他們開發(fā)了一些特殊的技術(shù)來(lái)實(shí)現(xiàn)這種證明（[Gri81]），但到目前為止，這些形式化驗(yàn)證技術(shù)只能處理一些非常小型的程序。
就實(shí)用性來(lái)說(shuō)，對(duì)程序的驗(yàn)證還是要依賴測(cè)試。測(cè)試計(jì)算機(jī)程序與其說(shuō)是一門科學(xué)，還不如說(shuō)是一門藝術(shù)。但這并不意味著我們就無(wú)需學(xué)習(xí)這方面的知識(shí)。我們可以查看一些專門講述測(cè)試和調(diào)試技術(shù)的書籍，但更重要的是，無(wú)論我們實(shí)現(xiàn)何種算法，都要對(duì)程序進(jìn)行徹底的測(cè)試及調(diào)試。
另一個(gè)需要注意的問題是，本書自始至終都假設(shè)算法的輸入都在事先確定的范圍內(nèi)，從而不進(jìn)行檢驗(yàn)。當(dāng)算法的程序?qū)崿F(xiàn)用于實(shí)際應(yīng)用時(shí)，這樣的檢驗(yàn)還是必不可少的。
當(dāng)然，算法的正確實(shí)現(xiàn)是必要的，但它還不是全部：我們當(dāng)然不愿意用缺乏效率的實(shí)現(xiàn)來(lái)削弱算法的威力。現(xiàn)代編譯器的確為這種需求提供了一定的保障，尤其當(dāng)它們處于代碼優(yōu)化模式時(shí)。但我們?nèi)匀恍枰莆找恍?biāo)準(zhǔn)的技巧，例如：在循環(huán)之外計(jì)算循環(huán)中的不變式（表達(dá)式的值不會(huì)隨情況而改變）；合并公共的子表達(dá)式；用低開銷操作代替高開銷操作等（參見[Ker99]和[Ben00]，它們對(duì)代碼優(yōu)化和算法編程的其他相關(guān)問題做了很好的討論）。一般來(lái)說(shuō)，這樣的改進(jìn)對(duì)算法速度的影響僅僅是一個(gè)常數(shù)因子，而一個(gè)更好的算法會(huì)使運(yùn)行時(shí)間產(chǎn)生數(shù)量級(jí)的差異。對(duì)于一個(gè)已選定的算法，如果能提高10%～50%的速度，上述努力將是值得的。
對(duì)于實(shí)際程序，我們還可以利用經(jīng)驗(yàn)分析來(lái)研究它內(nèi)在算法的效率。這種分析的基本原理是：提供若干輸入，計(jì)算程序的運(yùn)行時(shí)間，然后對(duì)結(jié)果進(jìn)行分析。我們將在2.6節(jié)討論經(jīng)驗(yàn)分析方法的利與弊。
最后，我們?cè)購(gòu)?qiáng)調(diào)一下圖1.2中過(guò)程的主要含義：
一個(gè)好的算法是不懈努力和反復(fù)修正的結(jié)果，這是一條規(guī)律。
所以，即使夠運(yùn)氣，獲得了一個(gè)看似完美的算法思路，也應(yīng)該嘗試著改進(jìn)它。
實(shí)際上，這是一件好事，因?yàn)檫@會(huì)讓最終結(jié)果充滿更多的樂趣（的確，我曾經(jīng)考慮將這本書命名為《算法的樂趣》）。但另一方面，我們?cè)趺粗篮螘r(shí)應(yīng)該停止這種努力呢？現(xiàn)實(shí)生活中，迫使我們停下來(lái)的往往是項(xiàng)目進(jìn)度表和老板的耐心。其實(shí)原本也該如此，完美的代價(jià)往往是高昂的，而且并不總是提倡的。設(shè)計(jì)算法是一種工程行為，需要在資源有限的情況下，在互斥的目標(biāo)之間做權(quán)衡，設(shè)計(jì)者的時(shí)間就是這樣一種資源。
在學(xué)術(shù)領(lǐng)域，算法的最優(yōu)性（optimality）問題引發(fā)了有趣而又艱苦的研究。實(shí)際上，該問題與某一算法的效率無(wú)關(guān)，而與所解決問題的復(fù)雜度有關(guān)：對(duì)于給定的問題，任一算法最少需要花費(fèi)多少氣力呢？有些時(shí)候，上述問題的答案是已知的。例如，對(duì)于長(zhǎng)度為n的數(shù)組，任何用比較元素值來(lái)對(duì)數(shù)組進(jìn)行排序的算法，都需要做大約n log2n次比較（參見11.2節(jié)）。但對(duì)于許多貌似簡(jiǎn)單的問題，計(jì)算機(jī)科學(xué)家還無(wú)法給出一個(gè)最終答案，例如矩陣的乘法。
算法問題求解的另一個(gè)重要疑問是：是不是每個(gè)問題都能夠用算法的方法來(lái)解決？我們當(dāng)然不是在討論問題無(wú)解的情況，例如在判別式為負(fù)時(shí)求二次方程的實(shí)根。在這種情況下，我們能得到的結(jié)果，或者說(shuō)期望得到的結(jié)果，應(yīng)該是算法指出該問題無(wú)解。我們也不是在討論定義模糊的問題。我們所說(shuō)的是，即使是一些明確定義的問題，它們只要求回答“是”或“否”，可能也是“不可判定”的，即不能用任何算法解決。11.3節(jié)將介紹這種問題的一個(gè)重要例子。幸運(yùn)的是，在實(shí)際計(jì)算中，絕大多數(shù)問題都能夠用算法來(lái)解決。
圖1.2的流程圖可能過(guò)于呆板了，但在結(jié)束這一節(jié)之前，我們希望讀者不要誤以為設(shè)計(jì)算法很無(wú)聊。一個(gè)千真萬(wàn)確的事實(shí)是：發(fā)明（或者發(fā)現(xiàn)）算法是一個(gè)非常有創(chuàng)造性和非常值得付出的過(guò)程。本書的目的就是證明這個(gè)事實(shí)。