馮舜璽

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

——D．E．Knuth

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

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

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

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

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

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