《趣題學算法》—第0章0.4節算法的正确性

本節書摘來自異步社群《趣題學算法》一書中的第0章0.4節算法的正确性，作者徐子珊,更多章節内容可以通路雲栖社群“異步社群”公衆号檢視。

0.4　算法的正确性

解決一個計算問題的算法是正确的，指的是對問題中任意合法的輸入均應得到對應的正确輸出。大多數情況下，問題的合法輸入無法窮盡，當然就無法窮盡輸出是否正确的驗證。即使合法輸入是有限的，窮盡所有輸出正确的驗證，在實踐中也許是得不償失的。但是，無論如何，我們需要保證設計出來的算法的正确性。否則，算法設計就是去了它的應用意義。是以，對設計出來的算法在送出應用之前，應當說明它的正确性。這就需要借助我們對問題的認識與了解，利用數學、科學及邏輯推理來證明算法是正确的。例如，對于解決“計算逆序數”問題的算法0-1，其正确性可以表述為如下命題：

當第3～7行的for循環結束時，count已記錄下了序列a[1..n]中的逆序數。

如果我們能說明上述命題是真的，那就說明了算法0-1是正确的。由于數組a[1..n]的長度n是任意正整數，是以這是一個與正整數相關的命題。數學中要證明一個與正整數相關的命題有一個有力的工具——數學歸納法。下面我們對本命題中的n進行歸納。

當n=1時第3～7行的for循環重複0次。count保持初始值0，這與a[1..n]=a[1]沒有任何逆序相符，結論顯然為真。

設n>1且可用算法計算出a[1..n−1]的逆序數count。在此假設下，我們來證明對a[1..n]利用算法0-1也能得到正确的逆序數count。

考慮算法中第3～7行的for循環在j=n時的第一次重複的操作：第4～6行内嵌的for循環從i=1開始到j−1為止，逐一檢測是否a[i]>a[j]。若是，意味着找到一個關于a[n]的逆序，第6行count自增1。當此循環結束時count中累積了關于a[n]的逆序數。由于n>1，故第3～6行的外圍for循環必定會繼續對a[1..n−1]做同樣的操作。根據歸納假設，我們知道第3～6行的for循環接下來的重複操作能将a[1..n−1]中個元素的逆序數累加到count中。是以第3～6行for循環結束時，count已記錄下了序列a[1..n]中的逆序數。

這樣，我們就從邏輯上證明了算法0-1能正确地解決“計算逆序數”問題的一個案例，即算法0-1是正确的。

應當指出，解決一個計算問題時，算法不必唯一。資料的組織方式、解題思路的不同，會導緻不同的算法。

例如，将計數器count設定為全局變量，并初始化為0。解決“計算逆序數”問題一個案例的算法還可以表示為如下的形式。

算法0-2　解決“計算逆序數”問題一個案例的遞歸算法僞代碼過程

這是一個“遞歸”算法，它在定義的内部（第6行）進行了一次自我調用。受上述算法0-1正确性命題證明的啟發，這個算法的思想是基于先計算出a[1..n-1]中關于a[n]的逆序數count，然後将問題歸結為計算a[1..n-1]的逆序數的子問題。用相同的方法解決子問題（遞歸調用自身，注意表示a的長度的第2個參數變成n-1）把子問題的解與count合并就可得到原問題的解。其實，算法0-2與算法0-1僅僅是表達形式不同，本質上等價的：後者用末尾遞歸（第6行遞歸調用自身）隐式地替代算法0-1中第3～6行的外層for循環。是以，算法0-2也是正确的。