算法正確性

算法是可供計算機執行的對數據進行處理的一個有窮步驟，是解決問題的一個邏輯順序，是解題方法的精確描述，它有一些精確定義的操作規則，每條規則是確定的、能行的，不能有二義性。算法有一個初始輸入，它給出最原始的條件，並且有一個最終的算法輸出，它給出算法的目標，同時每個算法需有一個算法名。

算法正確性是對任意一個合法的輸入經過有限步執行之後算法應給出正確的結果。其中“正確”的含義包括以下三個方面：

(1)算法對幾組不同的輸人數據能夠得出滿足要求的結構。

(2)算法對於精心選擇的典型、苛刻而帶有刁難性的輸入數據能夠得出滿足要求的結果。

(3)算法對於一切合法的輸入數據都產生滿足要求的結果。 ^[2] 

算法正確性證明包括兩個方面：①證明關於輸入與輸出之關係的命題是正確的；②證明算法中的公式及計算方法是正確的。

正確性是對算法最基本、最重要的要求。 ^[1] 

如果一個算法對於所有合法的輸入，都能在有限時間內輸出預期的結果，那麼此算法是正確的。確認一個算法是否正確的活動稱為算法確認(algorithm validation）算法確認的目的在於確認一個算法能否正確無誤地工作。使用數學方法證明算法的正確性，稱為算法證明（algorithm proof ）對於有些算法，正確性證明十分簡單，但對於另一些算法，卻可能十分困難。

證明算法正確性常用的方法是數學歸納法。若要表明算法是不正確的，只需給出能導致算法不能正確處理的輸入實例即可。

算法的正確性證明仍是一項很有挑戰性的工作。在大多數情況下，人們通過程序測試和調試來排錯。程序測試(program testing)是指對程序模塊或程序總體，輸入事先準備好的樣本數據(稱為測試用例，test case)，檢查該程序的輸出，來發現程序存在的錯誤及判定程序是否滿足其設計要求的一項積極活動。測試的目的是為了“發現錯誤”而不是“證明程序正確”。程序經過測試暴露了錯誤，需要進一步診斷錯誤的準確位置，分析錯誤的原因，糾正錯誤。 ^[3] 

算法主要是為了方便程序員的閲讀與交流，其次才是便於機器執行。可讀性好有利於程序員對算法的理解；晦澀難懂的程序易隱藏較多錯誤，難以調試和修改。

健壯性即指算法對於非法輸入的抵抗能力，它強調了即使輸入了非法數據，算法應能夠識別並做出正確處理，而不是產生莫名其妙的輸出結果。例如，一個求凸多邊形面積的算法是採用求各三角形面積之和的策略來解決問題，當輸入的座標值集合表示的是一個凹多邊形時，則不應繼續計算，而應報告輸入出錯。並且，處理錯誤的方法是返回一個表示錯誤或錯誤性質的值，而不是打印錯誤信息或異常，並同時終止程序的執行，以便在更高的抽象層次上進行處理。

算法的效率通常是指算法的執行時間。對於一個具體的問題，通常有多個算法可以解決，執行時間短的算法其效率就高。所謂存儲量，是指算法在執行過程中所需要的最大存儲空間。效率與低存儲量需求這兩者與問題的規模有關。 ^[2]