如果你被困在一个沙漠黄岛上，并且只能选择一本算法书，我们推荐 Donald Knuth 的《计算机程序设计艺术》（1998）
第一部分
第1章：算法真的很重要
Graham决定编写-一个库，以包装操作系统的内存分配以及回收函数，例如m alloc().
free(),还有他自己的函数。Graharn的函数将每次内存的分配以及回收都记录在一一个
特定的数据结构中，这样在程序结束之后，程序员能够查询到这些记录。这些包装函数
记录这些信息，并且调用操作系统函数来进行内存管理。Graham只花了几个小时就实现
了这个库而且能够正常被调用执行。但是现在有- -个问题:调用了Graham的库的程序运
行得如此缓慢，以至于没有人会去使用它。这是真的名副其实地缓慢。你可以先启动程
序，然后离开去喝一杯咖啡，或许喝- -壶咖啡也可以，然后回来，你会看到程序还在缓
慢地运行着。这种速度当然不能够接受。
理解问题
解决问题最好从大局观开始:理解问题，找出潜在原因，然后深入挖掘细节。如果你觉
得你知道原因，然后决定解决这个问题，那么你可能会出错，或者你也许不会发现其他
更好的答案。Gary 首先希望Graham能够描述这个问题以及他的解决方案。
如果需要，尽可能用实践检验
在继续深入之前，Gary希望能够较好地了解程序的运行状况。他和Graham坐下来一起写
了一些小程序，通过调用这个库来检查这些程序是如何运行的。也许他们能够更好地明
白是什么导致了这个诡异的问题。
解决问题的算法
如果- -棵二叉查找树的根节点到任意-一个叶子节点的路径长度都基本相等，那么这棵树
就是二叉平衡查找树。定义depth(L)为从根节点到叶子节点L的路径长度。如果-棵_
叉树具有良好的平衡度，那么对任意两个叶子节点L和L2来说，depth(L2)和depth(L)的
差的绝对值，即ldepth(L2) - depth(L)ls1;同样对于任何一个叶子节点L;来说，depth(L)
slog(n)。Gary翻阅了他的算法书籍，决定对Graham的代码进行修改，用更加平衡的红
黑树记录内存的分配。红黑树(Cormen, 2001)是一个平衡二叉树的高效实现。在红黑
树中，给定两个叶子节点L和L2, depth(L2)/depth(L)s2; 同样对任意叶子节点L来说，
depth(L)s2*log(r+1)。也就是说，- -棵红黑树是大致地平衡的，这确保了在红黑树中，
不存在- -条路径，其长度是另外一条路径的两倍。
第2章 算法的数学原理
在解决问题之前，我们可以试着猜测下，在这个问题所依赖的平台(或者平台家族)和
数据上，哪个算法将会获得最好的性能。计算-一个算法的期望运行时间本质上是一个数
学运算过程。在本章，我们将透过现象看本质，阐述隐藏在这些复杂计算内的数学工具
以及使用方法。通过本章的阅读，读者应该能够理解本书将要使用的数学术语。
贯穿本章(实际上是贯穿整本书)的一个共同主题就是所有的假设和近似操作都会花费
常数时间，但是最终我们得到抽象结论的时候，都会忽略这些常数时间。在所有的平台
.上，相比影响本书所述的算法性能的其他因素来说，这些常数都是小到可以忽略不计
的。
样本编码
给你一个很大的数字x，要求计算x的二进制形式中1的个数的奇偶性(也就是说，1
的个数是奇数还是偶数)。例如，如果x=15 137 300 128，其二进制表示是:
x2=11100001 10010000001101111010100000
可以看到1的个数是偶数，我们考虑下面两种可行的编码策略:
x的编码1: 11 10000110010000001101111010100000
x的这个二进制表示方法使用了34个字节。注意到log2(x)的值是33.82，因此这个
编码方式是最理想的。但是为了计算1的个数的奇偶性，需要检查每一个位。这种
编码方式下，计算奇偶性的最佳时间的增长与x的长度n (x的对数)增长呈线性关
系。
x也能够用下面的方式来表示，使用n个位，再加上一一个额外的校检位来表示1的数
目的奇偶性。
x的编码2: 11 10000110010000001101111010100000[0]
我们可以看到x的这种编码方式的最后一个位是0，这表示1的个数为偶数个(偶数
用0表示)。对于这种表示法，需要35个字节。在两种编码方式中，样本编码的规
模都随x的值对数增长。但是，在第一种编码方式中，计算奇偶性最佳算法的时间.
增长情况与x的编码规模的增长呈对数关系，但是第二种编码方式中，最佳算法只
需要花费常数的时间，而且与x编码规模无关。