新書推薦：《算法分析導論》

馮舜璽

分析算法的人享有雙重的幸福。首先，他們體驗到優雅數學模式純粹的美，這種模式存在于優美的計算過程之中。其次，當他們的理論使得其他工作能夠做得更快和更經濟時，他們得到的是實際的褒獎……因此，我們盼望已久的這部著作備受歡迎。該書作者不僅是算法領域在世界范圍內的領袖，而且還是闡述的大師。

——D．E．Knuth

在計算機科學中，算法猶如國之利器，無疑是永恒的基石和主題。今天，隨著計算機的應用越來越廣，算法的影響也日漸增加。從傳統的數學、物理學直至現在的因特網搜索引擎，算法都在其中扮演著重要的角色。

算法分析一般包括兩種不同的方法。第一種方法研究確定最壞情形的性能，有時稱之為計算復雜性。當面對一種新的算法時，用此方法能夠形成一種粗略的認識：新算法能夠有多好？它比其他算法性能大致如何？就算法分析來說，這種復雜性分析由于拋棄了一些次要因素因而會喪失不少精度，它提供不了算法具體實現的性能特征以及與其他算法具體比較所需的足夠信息。不過，我們可以把它看成是形成更精練、更準確分析過程的第一步。第二種方法通過確定最佳情形、最壞情形以及平均情形的性能來精確地刻畫算法的性能，在需要的時候，能夠通過可以精化的方法準確地預測特定算法的性能特征，其中最常見的是對時間和空間這樣一些基本資源的消耗，尤其是時間。算法分析表示整個分析過程，它提供任意精度的解決方案。

《算法分析導論》（機械工業出版社出版）一書對算法的數學分析中使用的基本方法提供了全面的介紹。本書涉及的內容十分豐富，既有經典的數學素材，包括離散數學、初等實分析、組合數學，還不乏經典的計算機科學素材（包括算法和數據結構）。雖然書中論述了“最壞情形”和“復雜性問題”分析所需的基本數學工具，但重點還是討論“平均情形”或“概率”分析。論題涉及遞歸、生成函數、漸近性、樹、串、映射等內容，以及對排序、樹查找、串查找和散列諸算法的分析。

盡管人們極為關注算法的數學分析，但是廣泛使用的方法和模型方面的基本信息尚不能為諸多工作和研究所直接使用。作者在本書中積極處理這種需求，把算法領域出現的挑戰以及為跟上新的研究以迎接這些挑戰所必需的背景資料完美地結合在一起。

本書語言簡煉，推導緊湊，它能夠很好地鍛煉我們獨立的閱讀能力。在驗證書中的結論和求解練習的結果時，若能使用像Matlab、Mathematica或MAPLE這樣的計算機軟件，則可幫助我們擺脫繁瑣的演算，節省寶貴的時間。本書的另一大特點是課文中以及各章末尾所列出的參考文獻，對于有心深造的讀者，這是十分寶貴的財富。

經過近幾十年的發展，算法分析已經十分成熟，并能夠在標準的計算機課程中占有一席之地。本書不僅適用于編程人員和計算機科學專業的學生，也適用于想讓計算機運行得快一些或想解決一些實際問題的計算機用戶，為那些徘徊在該領域之外卻苦于不得其門而入的新手指出通往研究之門的捷徑。高年級本科生和研究生在先修有關數學和計算機的相應知識的基礎上，可以將本書用于算法分析的導論性課程。數學和計算機領域中不同專業的學生，選修本書可以各有側重，對此，作者在前言中給出了指導性的建議。