我們面對一個 Problem，如排序問題時，我們會想到相應(yīng)的候選算法如快速排序（Quicksort），歸并排序（Merge sort）和堆排序（Heapsort）等，然后我們會去分析它們相應(yīng)的時間復(fù)雜度和空間復(fù)雜度，以選取符合我們應(yīng)用場景和需求的一個作為 Solution。

但在我們實現(xiàn)算法后，往往我們不知道或者不會去做的一步是證明算法的正確性。

為什么要證明算法的正確性

假設(shè)計算機運行速度無限快，內(nèi)存無限大，那么是否還有必要學(xué)習(xí)算法呢？答案是肯定的，我們必須確保算法的正確性，否則無論你的算法運行得多么快，如果是錯誤的算法，得到錯誤的答案，那么一點用處都沒有。

在實現(xiàn)算法后，我們可以寫單元測試去驗證它是否如期運行，寫多種情況下的 test case。但對于某些算法我們不可能寫出所有輸入-期望輸出對，例如一個排序算法接受一個 list 的參數(shù)，這個 list 的長度是為自然數(shù)的，也就是它可以為無窮大，因此單元測試實際上不可能覆蓋所有輸入-期望輸出對。
而正確性可以從理論層面上證明算法在接受 domain 內(nèi)任意輸入后，能產(chǎn)生期望的正確的輸出。

證明算法正確性的方法

算法內(nèi)部計算使用的方式，一般有循環(huán)和遞歸，分別可以使用循環(huán)不變量和結(jié)構(gòu)歸納來證明它的正確性，在未來幾篇文章里會講解它們的概念和用法。