算法正確性是對任意一個合法的輸入經過有限步執行之後算法應給出正確的結果。算法正確性證明包括兩個方面：①證明關於輸入與輸出之關係的命題是正確的；②證明算法中的公式及計算方法是正確的。
正確性是對算法最基本、最重要的要求。
基本介紹
- 中文名：算法正確性
- 外文名：Algorithm correctness
- 屬性：算法設計最基本，最重要的要求
- 定義：對任意一個合法輸入給出正確結果
- 套用學科：計算機原理
- 套用：計算機數據處理
定義,證明,算法設計其他要求,可讀性,健壯性,高效率和低存儲量,
定義
算法是可供計算機執行的對數據進行處理的一個有窮步驟，是解決問題的一個邏輯順序，是解題方法的精確描述，它有一些精確定義的操作規則，每條規則是確定的、能行的，不能有二義性。算法有一個初始輸入，它給出最原始的條件，並且有一個最終的算法輸出，它給出算法的目標，同時每個算法需有一個算法名。
算法正確性是對任意一個合法的輸入經過有限步執行之後算法應給出正確的結果。其中“正確”的含義包括以下三個方面：
(1)算法對幾組不同的輸人數據能夠得出滿足要求的結構。
(2)算法對於精心選擇的典型、苛刻而帶有刁難性的輸入數據能夠得出滿足要求的結果。
(3)算法對於一切合法的輸入數據都產生滿足要求的結果。
算法正確性證明包括兩個方面：①證明關於輸入與輸出之關係的命題是正確的；②證明算法中的公式及計算方法是正確的。
正確性是對算法最基本、最重要的要求。
證明
如果一個算法對於所有合法的輸入，都能在有限時間內輸出預期的結果，那么此算法是正確的。確認一個算法是否正確的活動稱為算法確認(algorithm validation）算法確認的目的在於確認一個算法能否正確無誤地工作。使用數學方法證明算法的正確性，稱為算法證明(algorithm proof ）對於有些算法，正確性證明十分簡單，但對於另一些算法，卻可能十分困難。
證明算法正確性常用的方法是數學歸納法。若要表明算法是不正確的，只需給出能導致算法不能正確處理的輸入實例即可。
到目前為止，算法的正確性證明仍是一項很有挑戰性的工作。在大多數情況下，人們通過程式測試和調試來排錯。程式測試(program testing)是指對程式模組或程式總體，輸入事先準備好的樣本數據(稱為測試用例，test case)，檢查該程式的輸出，來發現程式存在的錯誤及判定程式是否滿足其設計要求的一項積極活動。測試的目的是為了“發現錯誤”而不是“證明程式正確”。程式經過測試暴露了錯誤，需要進一步診斷錯誤的準確位置，分析錯誤的原因，糾正錯誤。
算法設計其他要求
可讀性
算法主要是為了方便程式設計師的閱讀與交流，其次才是便於機器執行。可讀性好有利於程式設計師對算法的理解；晦澀難懂的程式易隱藏較多錯誤，難以調試和修改。
健壯性
健壯性即指算法對於非法輸入的抵抗能力，它強調了即使輸入了非法數據，算法應能夠識別並做出正確處理，而不是產生莫名其妙的輸出結果。例如，一個求凸多邊形面積的算法是採用求各三角形面積之和的策略來解決問題，當輸入的坐標值集合表示的是一個凹多邊形時，則不應繼續計算，而應報告輸入出錯。並且，處理錯誤的方法是返回一個表示錯誤或錯誤性質的值，而不是列印錯誤信息或異常，並同時終止程式的執行，以便在更高的抽象層次上進行處理。
高效率和低存儲量
算法的效率通常是指算法的執行時間。對於一個具體的問題，通常有多個算法可以解決，執行時間短的算法其效率就高。所謂存儲量，是指算法在執行過程中所需要的最大存儲空間。效率與低存儲量需求這兩者與問題的規模有關。
