大师小传：唐·克努特，算法分析之父

ieee文章测试－0012

【摘要】一些算法能够编出“更优秀”的程序，即这些程序的执行时间更短、需要的内存更少。我们要如何量化算法之间的区别，确定哪些算法更优秀？对于这个问题，唐·克努特（Don Knuth）给出了最佳答案，他被称为“算法分析之父”。

【正文】当克努特在密尔沃基读大学预科时，他就已经展现出了特殊的才华，他在凯斯理工学院的大学生涯中的表现非常优异，被校方授予双联硕士学位。他在加州理工学院数学系继续研究生学业，于1963年获博士学位。随后克努特留在加州理工大学任教，直到1968年来到斯坦福大学，目前仍担任该校名誉教授。

1962年，还只是个数学专业研究生的克努特决定写一本关于编程语言和编译器的著作，他当时已经对这一领域的发展做出了重要贡献。著作的前8章将涵盖计算的“初步”，后4章着力解决目标学科的问题。但是，他在收集资料的过程中注意到，这部著作的篇幅会变得非常长。他决定采用全面解决的办法，这要比简短的解决方案更好，于是“初步”部分成为一套丛书，书中定义了对算法的分析。这套丛书名为《计算机编程的艺术》（The Art of Computer Programming）1，因为克努特将计算机编程视作艺术与科学的结合。三卷本包括内容的前六章，于1968年至1974年出版（此三卷的最后一版出版于1997和1998年）。值得一提的是，第4卷的第一部分直到2011年才出版。

笔者在这里介绍前三卷的一些内容，给出出版时间中断的一个原因，并说明克努特对未来几卷的写作意图。

第1卷 基础算法

第一章中涉及到的基本概念将统计学和数学加以汇编，用于各卷中对算法的分析。这些分析包括算法的内存需求和执行时间。关于执行时间，克努特处理了最坏情况下的时间（由最坏情况下的输入决定），以及平均时间（由可能输出的统计分布决定）。在展示数学工具后，克努特定义了一台名为MIX的假想中的计算机，考虑在MIX上进行汇编语言编程。即使在上世纪60年代晚期，汇编语言编程也已经开始过时，但他为了对执行时间进行细致分析而维护了这一选择。他还对每种待分析的算法进行了高级描述。最后，他定义了MIX模拟器，可以原样运行写出的MIX程序。

第二章中描述的信息结构已被证明是接下来的许多算法和数据结构文本的基础。这里使用的基本信息结构是线性表和树。实现技术为顺序和链接分配。顺序分配线性表又名数组。树的通常实现方式是通过指针将子树和母节点相连。这些结构和实现技术的多样化组合，是构建复杂的数据结构的基础。但是，对于给定的数据结构，有必要强调在该结构上的操作方式，即实现数据结构的最佳方式依赖于应用程序中使用的操作方式的混合。

第二章的末尾讨论了存储分配方式：创建用于建立数据结构的1比特内存。遗憾的是，即使在今天，为新数据分配空白地址时没有检查“缓存溢出”（即分配空间超出了保留空间），仍然是程序员们会犯的常见错误之一。不法骇客经常利用这一漏洞向计算机注入恶意代码。

第2卷：半数值算法

第3章的标题是随机数的生成。克努特明确指出，他讨论的是伪随机序列：即具有随机性的确定序列。确定性很重要。因为这样才能对程序除错，否则程序就将以同样的（伪）随机序列作为输入再次运行。由于对真实系统的建模和模拟在当时和现在都是非常重要的计算应用，而且这些模拟经常涉及到对取值分布的随机选择，所以能否正确地进行随机化，可能就成为优秀模拟和垃圾模拟的区分标准。

克努特分析了线性同余法，Xi + 1 = (a × Xi + b) 余c。即下一个随机数Xi + 1由前一个随机数Xi算出，即表达式a × Xi + b被c除的余数。如果小心选定a、b、c的值，这一简单技术就可以返回一个伪随机序列数，在0-1间呈均匀分布。接着，他论述了这种序列如何能够转化为其他多种概率分布的随机序列。

第4章的标题为计算机算法。一位聪明的第2卷的评论者曾说过：“哦，不！我不想了解这么多关于计算机算法的内容。”但是，一些计算机程序员需要理解如何将抽象的数值操作与真实的计算机联系起来（因此书中的设计为半数值算法）。比如，怎样实现求幂？如果一个人天真地假设求x64需要做63次相乘（幂的定义就是如此），那么阅读本章是有启发意义的。如果变量x被x2替换6次，那么计算x64实际上就只须6次相乘了。这一平方过程可推广至任意整数次幂。如果指数部分长度为n个比特，那么该算法最多需要计算2n次乘法。

第3卷：排序与搜索

第5章的标题是排序，分为内部排序和外部排序。内部排序是指文件被排序载入计算机的主内存。外部排序在磁盘或磁带需要保留文件时进行。克努特表示，排序算法是最早期的计算机上最先开发的技术之一。他认为，学习排序算法可以教会我们算法之外的很多东西。比如可以教我们如何分析算法、如何从多个方向解决一个计算机问题。速度最慢的排序算法之一被称为“冒泡排序”，最快的算法叫做“快速排序”。克努特的分析表明，在一台gigaop计算机上对10亿个数进行排序，快速排序算法的平均耗时约为6分钟，而在同一台计算机上使用冒泡排序则需要大约192年！

第6章的标题为搜索，搜索主要分三大技术：关键词比较搜索、数字化搜索和散列法。关键词比较搜索对n个关键词有序排列文件的搜索次数不会超过log2 n次。在数字化搜索中，将搜索关键词视作一组小数字的序列，其作用相当于数组的索引，其中包含指针，指向文件中可能出现关键词的部分。在散列法中，关键词被视作一个数字。在一种散列法中，关键词被包含关键词的数组长度相除。数组长度应为质数，除式的余数产生一个对数组的随机索引，无需搜索即可确定关键词的位置。

两个关键词偶尔会产生相同的索引，称为“冲突”。克努特讨论了解决冲突的技术。每种搜索方法都可用于内部和外部搜索应用。关于排序，好的算法将是实现快速搜索的基础，就像谷歌和其他搜索引擎做到的那样。

TeX和元字体

第3卷和第4卷第一部分的出版时间相隔了很长时间，其中一个原因是克努特对他的书稿的排版技术产生了兴趣。上世纪70年代，排版开始走向数字化，但技术还不够成熟。克努特发现没有符合自己标准的数字化系统，他决定自己建立一套系统。也许是他父亲曾经营过一家小型打印店，为他的计划提供了支持。他将自己的系统称为TeX，该名字源自三个希腊字母，其发音与tech相同。2一位热心的观察家称之为古腾堡发明活版印刷以来最伟大的技术进步。印刷、出版和学术群体也对这一系统给予类似的赞誉。

在一项相关开发中，克努特创立了元字体，这是一个数字化字体的开发系统，他使用该系统定义了一种字体，他称其为“现代计算机”，在他的书中（和其他地方）使用。TeX经历了几十年的开发，现在的最终版本已经稳定。新版本的TeX组件包名为TeXML，为TeX系统提供了XML前端。克努特退休很早（1992年，54岁），因为他觉得自己需要大约20年时间全力完成《计算机编程的艺术》。他计划第4卷（内容包括组合搜索和递归）和第5卷（内容包括词汇扫描和语法技术）将于2020年完成（届时他已82岁）。他在自己的网页上（(http://www-cs-faculty.stanford.edu/~uno）表示：

在第5卷完成之后，我对1-3卷进行了重新修订，以跟上时代发展......接下来我会出版一本1-5卷的“读者文摘”版，将最重要的内容浓缩进一本书。在1-5卷完成后，如果情况允许，我打算出版第6卷（关于语境自由理论）和第7卷（关于编译器技术），但前提是我想写的关于这些主题的内容仍然有意义，而且别人还没写过。1-5卷所述是时序机计算机编程的核心内容，第6卷和第7卷更加专门化的重要内容。

尽管是一部尚未完成的著作，许多人仍认为《计算机编程的艺术》是计算机编程方面里程碑式的丛书。1999年底，该书被《美国科学家》提名为20世纪物理-科学12部最佳专著之一。4克努特同样获得了诸多荣誉，包括1974年的图灵奖和1979年的美国国家科学奖章。

文章的最后我想提一下比尔·盖茨，他曾在该书第三版第1卷的书封上写道：“如果你觉得自己是个不错的程序员，去读读《计算机编程的艺术》吧......如果你能从头到尾读懂，那你绝对应该给我发一份简历。”

• 相关文章

• 加密到底应该是什么？2015-11-22 18:34:39
• 访谈：吉多·范·罗素：Pyth2015-11-22 18:34:33