1.2.7　算法的正確性證明

一旦完成對算法的描述，我們就必須證明它的正確性（correctness）。也就是說，我們必須證明對于每一合法輸入，該算法都會在有限的時間內輸出一個需要的結果。舉例來說，計算最大公約數的歐幾里得算法的正確性依賴于以下條件：等式gcd（m, n）=gcd（n, m mod n）的正確性（這需要證明，參見習題1.1的第7題）；該算法每做一次循環，第二個數字就會變得更??；算法會在第二個數字變為0時停止。

對于某些算法來說，正確性證明是十分簡單的；而對于另一些算法來說，卻可能是十分復雜的。證明正確性的一般方法是使用數學歸納法，因為算法的迭代過程原本就符合這種證明所需要的一系列步驟。值得一提的是，雖然根據一些特定輸入來追蹤算法操作的做法很有意義，但它并不能最終證明該算法的正確性。而為了證明算法是不正確的，則只需給出一個算法不能正確處理的輸入實例就足夠了。

對近似算法的正確性定義則沒有精確算法那么直接。對于一個近似算法來說，我們常常試圖證明該算法所產生的誤差不超出預定義的范圍。第12章會對這方面的研究舉一些例子。