《算法分析導(dǎo)論》評介

蘇運霖

本文對由兩位著名計算機科學(xué)家羅伯特·基德格維克（Robert Sedgewick）和菲律比·弗拉約列特（Philippe Flajolet）合著的《算法分析導(dǎo)論》一書進行介紹和評論，既指出它的突出特點和優(yōu)點，也指出其中美中不足處。

由于種種原因，我很晚才獲知關(guān)于《算法分析導(dǎo)論》一書在大洋彼岸出版的消息。但得知它在我國翻譯和影印出版，則相對地較早些，而且很榮幸，得到華章圖文信息有限公司的盛情邀請，要我寫一篇書評。這是一件很有意義的事情。因此我欣然命筆。

首先，要說一說本書的兩位作者。第一作者羅伯特·基德格維克是著名計算機科學(xué)家唐納德·歐·克努特的博士生，可以說是克努特的一位得意門生。在獲得博士學(xué)位之后，他繼承克努特的衣缽，從事計算機算法設(shè)計和分析的研究，而且成績斐然。除已發(fā)表了許多頗有建樹的有關(guān)算法的論文外，還發(fā)表了《算法》(Algorithms) 、《C語言下的算法》(Algorithms in C)等多部著作?；赂窬S克現(xiàn)在在美國長青藤大學(xué)之一的普林斯頓大學(xué)計算機科學(xué)系任教，也就是同世界首位榮獲計算機界最高獎的姚期智教授同在一個學(xué)校一個系內(nèi)，并且還是美國著名的Adobe System公司的董事?；赂窬S克還曾是另一家著名公司Xerox PARC的研究人員，她也是姚期智教授的夫人，著名計算機科學(xué)家姚儲楓教授長期任職的公司。基德格維克還曾就職于美國國防部防御分析研究所及INRIA等。而菲律比·弗拉約列特也非等閑之輩，他的多項成果被克努特在《計算機程序設(shè)計藝術(shù)》一書中所引用。作為法國科學(xué)院的院士，他現(xiàn)在是INRIA的高級研究主任，也在普林斯頓大學(xué)和Ecole Polytechnique任教，并且在斯坦福大學(xué)、智利大學(xué)和弗吉尼亞理工學(xué)院都擁有客座教授的席位。因此，克努特為本書所寫的序言中，指出兩位作者都是這一領(lǐng)域的世界級領(lǐng)軍人物，也是闡述問題的能手，并非只是贊美吹捧之詞。而由他們兩位來寫這么一本書，乃是適得其所的。

其次，本書確實具有里程碑式的意義。把它看做算法分析這樣一個嶄新領(lǐng)域的頭一本經(jīng)典著作，是絲毫不過分的。正如克努特在序言中所說，在30多年的發(fā)展之后，算法分析已經(jīng)相當成熟，可以單獨作為標準的計算機科學(xué)課程之一。而兩位作者來寫此書，正是當仁不讓地承擔起為這一課程提供一本經(jīng)典教材的使命。輕易不愿為他人的書作序的克努特，卻破例為本書寫序言，而且對它給予極高評價，正是本書價值的佐證。

當然，更雄厚的證據(jù)，還在于此書的內(nèi)容本身。作為本領(lǐng)域的領(lǐng)軍人物，本書的相當一部分內(nèi)容是兩位作者本人的創(chuàng)新性成果，也包括了迄今為止許多本領(lǐng)域的杰出科學(xué)家們的最新成果，而首先就是對于算法分析的工具或子領(lǐng)域的界定。在這方面，他們的見解肯定是權(quán)威性的。他們把它劃分成為遞歸式關(guān)系、生成函數(shù)、漸近近似式、樹形、排列、串和檢索結(jié)構(gòu)以及字和圖等。這種分劃是極其重要的。因為由此開始，在算法分析這一領(lǐng)域，研究的范疇就將包括這些方面。如同人工智能這一領(lǐng)域，也是當年由人工智能的先驅(qū)者們界定出包括：游戲、自動推理、搜索、定理自動證明、神經(jīng)網(wǎng)絡(luò)、模糊邏輯、非單調(diào)推理、自動決策和規(guī)劃、學(xué)習(xí)、記憶、語言產(chǎn)生和理解、語言識別、模式識別、機器人等。因此人工智能的發(fā)展就沿著這樣一些方向繼續(xù)下來。同時，它也說明，在算法分析中所使用的工具大體上屬于這一范疇。當然，同人工智能領(lǐng)域一樣，界定范疇并不妨礙今后的發(fā)展，可能會隨著時間的推移而出現(xiàn)新的領(lǐng)域，或采用別的更新的工具。

更具體地來看作者們的創(chuàng)新點，如在關(guān)于遞歸式關(guān)系的介紹中，他們把遞歸式歸納為：

1)一階遞歸式；

2)非線性一階遞歸式；

3)高階遞歸式；

4)二進制的分而治之遞歸式；

5)一般的分而治之遞歸式。

并把求解遞歸式的方法分為四個：

1)改變變量法；

2)各種技能法；

3)自舉法；

4)振動法。

這些都是作者們在總結(jié)別人和他們自己的工作的基礎(chǔ)上所作出的新貢獻。在這當中，不乏精彩的論述和巧妙的構(gòu)思。

但是，客觀地說，這兩位作者在嚴謹性上似乎還不如他們的導(dǎo)師克努特。他們的書中還是出現(xiàn)了少許技術(shù)性錯誤，這里僅列舉第2章遞歸關(guān)系中的數(shù)個。首先，在原書47～48頁中，考慮

a_n=3a_n-1-2a_n-2

依照作者們給出的辦法，這可通過解

x²-3x+2=0

來求出此方程的兩個解x=2和x=1。從而原遞歸式的解應(yīng)為

a·2ⁿ+b·1ⁿ

再由初始條件a₀=0和a₁=1，確定a和b。但是作者卻把該方程寫成

1-3x+2x²=0

因此，解當然就錯了。

其次，在原書60～61頁中，作者們指出，考慮求解

的解。他們引進了遞歸式

a_n+1≈2a_n

并考慮

b_n+1=2b_n

由此，給出

但是他們接著就得出了

這是無論如何也不可能成立的式子，很顯然，他們把ρn同an混為一談了。

第三個例子是表述的問題，在原書43頁上的定理2中，作者們給出：對于n>0和a₀=0

a_n=x_na_n-a+y_n

有

的顯式解。在證明中，他們提出兩邊除以xnxn-1Kx1并迭代。說得非常含糊不清，而實際上，如果直接通過數(shù)學(xué)歸納法，就可以非常直觀地得到解。

不過，盡管有這些問題，它們并不對本書的價值造成大的影響。這本書必然會作為算法分析的經(jīng)典著作而為舉世所公認。因此，我愿鄭重地向廣大有興趣的讀者推薦它。你如對該領(lǐng)域有興趣，就來讀它吧，保證你會大有收獲的！