《算法分析導論》評介

蘇運霖

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

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

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

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

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

更具體地來看作者們的創新點，如在關于遞歸式關系的介紹中，他們把遞歸式歸納為：

1)一階遞歸式；

2)非線性一階遞歸式；

3)高階遞歸式；

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

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

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

1)改變變量法；

2)各種技能法；

3)自舉法；

4)振動法。

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

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

a_n=3a_n-1-2a_n-2

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

x²-3x+2=0

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

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并迭代。說得非常含糊不清，而實際上，如果直接通過數學歸納法，就可以非常直觀地得到解。

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