1.2.8　算法的分析

我們常常希望算法具有許多良好的特性。除了正確性，最重要的特性就是效率（efficiency）了。實際上，有兩種算法效率：時間效率（time efficiency），指出算法運行有多快；空間效率（space efficiency），說明算法需要多少額外的存儲空間。第2章提出了一個分析算法效率的通用框架和一些特殊技術。

算法應該具有的另一個特性是簡單性（simplicity）。和效率不同，效率能夠用數學的嚴密性進行精確定義和研究論證，而簡單性就像“美”一樣，很大程度上取決于審視者的眼光。舉例來說，大多數人都承認，在計算gcd（m, n）時，歐幾里得算法比中學里的計算過程更簡單，但歐幾里得算法是否比連續整數檢驗算法更簡單則不是那么一目了然的。然而簡單性仍然是一個重要的算法特性，值得我們孜孜以求。為什么？因為簡單的算法更容易理解和實現，因而相應的程序也往往包含較少的bug。當然，對于簡單性的美學訴求也是讓人無法抗拒的。對于同樣的問題，有時簡單算法的效率比復雜算法更高。遺憾的是，情況并不總是如此，在這種情況下，我們就需要進行謹慎的權衡。

我們希望擁有的另一個算法特性是一般性（generality）。其實，它包含兩層意思：算法所解決問題的一般性和算法所接受輸入的一般性。對于第一個方面，我們應該注意到，有時候以更一般的形式出現的問題，反而更容易解決。考慮一個兩個整數互質的例子，即判斷它們是否只擁有唯一的公約數1。實際上這樣做更容易：設計一個更一般的算法，用它來計算兩個整數的最大公約數，然后解決前面的問題——檢查一下最大公約數是否為1。然而，有些情況下，設計一個更一般的算法不僅沒有必要，甚至可能是困難的或是完全不可能的。例如，沒有必要為了找出n個數字的中值（即其中第至于輸入的范圍，我們主要關心的是設計這樣一個算法，它能夠很自然地處理問題可能涉及的輸入。例如，對于一個最大公約數算法來說，不把等于1的整數作為可能的輸入就很不自然。另一方面，雖然解二次方程根的標準公式能夠處理系數是復數的情況，但一般情況下，我們不會將它推廣到這種程度，除非明確要求這樣做。

如果我們對于某個算法的效率、簡單性或一般性不滿意，則必須重新設計算法。其實，即使我們對算法做出了肯定的評價，再去探尋另一種算法仍然是有意義的。回想一下前一節中用來計算最大公約數的三種不同算法。一般來說，不要指望依靠一次嘗試就能找到最好的算法，最起碼，我們應該試著對已有的算法進行優化。例如，相對于1.1節中的最初版本，我們已經對“埃拉托色尼篩選法”的實現做了不少改進（你知道是哪些改進嗎？）。法國作家、飛行員和飛機設計師安東尼·德·圣埃克蘇佩里（Antoine de Saint-Exupéry）有一句名言，如果我們把它記在心中，就會更上一層樓：“不是在無以復加，而是在無以復減的時候，設計師才知道他已經達到了完美的境界。”