本书被分为四个部分。第一部分介绍了算法的必要数学基础，以便于读者理解本书的描述。第二部分介绍了一系列的算法。这些章节的每个独立部分都是一个完备的算法描述。第三部分为那些感兴趣的读者提供一些较为高深的资源。第四部分包括了一个附录，这个附录描述了本书每章中对算法进行评测的方法以及数学分析。

算法技术手册
Algorithms in a Nutshell
（美）George T. Heineman Gary Pollice Stanley Selkow著
李明 等译
图书在版编目（CIP）数据
本书版权登记号：图字：
Copyright (c) 2009 by O誖eilly Media, Inc.
Simplified Chinese Edition, jointly published by O誖eilly Media, Inc. and China Machine Press, 2009. Authorized translation of the English edition, 2009 O誖eilly Media, Inc., the owner of all rights to publish and sell the same.
All rights reserved including the rights of reproduction in whole or in part in any form.
英文原版由O誖eilly Media, Inc. 出版2008。
简体中文版由机械工业出版社出版2009。英文原版的翻译得到O誖eilly Media, Inc. 的授权。此简体中文版的出版和销售得到出版权和销售权的所有者——O誖eilly Media, Inc. 的许可。
版权所有，未得书面许可，本书的任何部分和全部不得以任何形式重制。
本书法律顾问　北京市展达律师事务所
书　　名/算法技术手册
书　　号/
责任编辑/陈佳媛
封面设计/
出版发行/ 机械工业出版社
地　　址/ 北京市西城区百万庄大街22号（邮政编码 100037）
经　　销/
印　　刷/
开　　本/ 178mm*233mm·　　　 印张
版　　次/ 2009年10月第　1 版　1　次
印　　次/
标准书号：ISBN 978-7-111-
　　　　　　　　　
定　　价/
凡购本书，如有倒页、脱页、缺页，由本社发行部调换
本社购书热线：（010）68326294
前言
就像《黑客帝国》里面的Trinity所说的：
“Neo，是这个问题驱使着我们，是这个问题带你来到这儿。”
你知道这个问题，我也是。
作为本书的作者，我们将回答引领你到此的问题：
我能够使用某个算法解决我的问题吗？如果可以，那么怎么实现呢？
你也许并不需要理解一个算法为什么是正确的。如果你需要，那么请看看其他的资料，例如1180页的算法圣经──《算法导论（第二版）》，作者是Thomas H. Cormen等（2001）。在那本书中你会了解到推论、定理以及证明；你也会从一些练习题和逐步递进的样例中看到算法是如何执行的。也许你会惊奇地发现，在算法导论中你找不到任何的实际代码，仅仅是一些伪代码的片段，伪代码是无数的算法教科书用来阐述算法的高级描述手段。在课堂上，这些教科书是非常重要的，但是在实际软件开发中，它们却起不到应有的作用，因为这些书假定伪代码都能够直接变成实际代码。
我们希望经验丰富的程序员在寻找问题的解决方案时，能够频繁参考本书。作为一名程序员，你每天要解决的问题都能在这里找到解决方案。在软件中，算法是决定成败的关键因素，在这里你能够了解到哪些决定能够改善关键算法的性能，也能够找到适合你的需求和解决方案的实际代码。
所有的算法都有实现，并且都使用测试工具经过仔细测试，以确保正确性。而且，它们有足够的代码文档，能在这本书的代码库附录中找到它们。我们严格地遵照一系列的原则来设计算法、实现算法，以及编写这本书。如果这些原则对你很有意义，那么这本书也会同样有用。
原则：使用实际代码，而不是伪代码
为了计算最大网络流，一个实践者应该做些什么才能将图P-1的Ford-Fulkerson算法描述转换成实际代码呢？
图P-1：教科书中常见的伪代码
图中的算法描述来自于维基百科（http://en.wikipedia.org/wiki/Ford_Fulkerson），这个描述与《算法导论》上的伪代码极其相似。最好还是不要期望一个软件的开发者能够根据这个Ford-Fulkerson算法的描述开发出实际的代码。翻到第8章，对比一下我们的代码。我们只使用有注释的，并且是精心设计过的代码。在你自己写的代码或者软件系统中使用我们提供的现成代码，或者这些代码的逻辑吧。
一些算法教科书确实有完整的C或者Java代码。但是这些教科书的目的通常是教初学者编程语言，或者是解释如何实现抽象数据类型。而且代码都只是在页面的狭窄边栏，作者通常都会忽略注释和错误处理，或者使用在实际应用中不会用到的快捷方法。我们相信程序员能够从有注释的，并且是精心设计过的代码中学到更多的东西，这就是我们为什么做如此多的工作来开发算法的实际解决方案。
原则：将算法和将要解决的问题分开
如果不和具体的问题联系起来，我们很难“泛化地”实现一个算法。我们反对那些给出了算法完全实现的书，这些书上的实现将泛化问题和特定问题纠结在一起，从而很难看出算法的原始结构。更糟糕的是，很多可用的实现依赖于一些特定的数据存储方式，虽然这种方式能够容易被机器理解，但是很难被人理解。
我们将会为泛化的问题和特殊的问题各设计算法的实现。例如，在第7章，当我们描述A*搜索算法的时候，我们用了一个例子，叫做八数码问题（在一个3×3格子的棋盘中移动编号为1～8的小方块）。A*算法的实现依赖于一系列良好定义的接口。因为有良好定义的接口，实现这些接口的类能够清晰地封装八数码这类特定问题的细节。
在本书中，我们使用了大量的编程语言，并且遵循一种严格的设计规范，使得代码可读性高并且生成高效的解决方案。由于我们具备软件工程背景，所以根据泛化的算法和特定领域的解决方案设计一个清晰的接口是一件很容易的事情。按照这样的流程编码，产生的软件是易于测试、维护并且能够根据面临的问题即时扩展。另外一个好处是读者能够更加容易地阅读和理解算法的描述和结果。当选择了一个算法，我们将会告诉读者，如何将我们编写的可读并且高效的代码转换成高度优化（虽然稍稍降低了可读性）并且性能优秀的代码。毕竟，优化是在问题已经解决之后才进行的，而且客户需要的是运行更快的代码。即便如此，我也认为我们需要听从C. A. R. Hoare的建议：“过早的优化是一切问题之源”。
原则：仅仅讲述足够的数学
很多算法注重专门关注于证明算法的正确性，并且抽象地解释其细节。我们关注的却是如何将算法应用到实践中去。最后我们才会介绍一些数学知识，这些数学知识都是为了读者能够更好地理解数据结构和解的控制流程。
例如，一个人需要理解在很多算法中使用的集合和二叉树的性质。但是，没有必要证明二叉树的高度如何得到，并且解释红黑二叉树是如何平衡的。如果你需要了解这些细节，请阅读《算法导论》的第13章。我们仅仅是需要才会解释结果，如果读者需要理解如何证明结论，我们将会告诉读者在哪儿能够找到数学证明。
在这本书你将会学习到使用一些关键术语和分析技术，并且基于数据结构的功能来区分算法行为。
原则：用经验来支持数学分析
在这本书中，我们从数学角度来分析算法的性能，以帮助程序员了解在哪种情况下算法能够得到最好的性能。我们将会提供现成的代码样例，在相关代码库中，有大量的JUnit（http://sourceforge.net/projects/junit）测试样例为每个算法的实现提供了文档。我们也会生成基准性能数据，供分析算法性能时参考。
我们将每个算法归到一个特定的性能族中，并且提供基准测试数据来得到算法的性能，支持我们的分析结论。有一些算法是那些数学背景的算法设计人员证明能够非常高效但是却不可能实现的，我们需要避免使用这样的算法。具有我们将在各种平台上执行我们的算法，以证明算法的高效并不依赖于特定平台，而是由于其优秀的设计。
附录包含了我们采用的基准测试方法的全部细节，并且这个基准测试能够独立地验证书中描述的所有性能结论。我们能够给你的建议在开源社区非常常见：“你得到的利益也许会不一样”。虽然你不可能准确地复制我们的结论，但是你能看出我们描述的趋势。我们鼓励你在决定使用哪个算法的时候使用我们的这种基于经验的方法。
目标读者
如果你被困在一个沙漠孤岛上，并且只能选择一本算法书，我们推荐Donald Knuth的《计算机程序设计艺术（卷1～3）》（1998）。Knuth在这本书中描述了大量的数据结构和算法，并且进行了精巧的处理和分析。这本书包含了大量的脚注和练习，并且能够帮助一名程序员在接下来的时间中保持活力和竞争力。这些练习是非常有挑战的，并且你能够直接接触到Knuth的思想。
但是你不是被困在孤岛上，对吗？你接手了一些劣质的代码，而且这些代码必须在周五前进行改进，你需要知道如何去处理！
在你面对一个算法问题，需要解决一个特定的问题或者对现有解决方案进行改进的时候，我们希望本书能够成为第一选择。为解决大量的问题，我们广泛地讨论了现存的算法，并且遵循以下原则：
* 我们使用模式化的统一格式来描述每一个算法，进行每一次讨论并解释算法的重点。正因如此，我们的书才如此易读。我们才能够看出相似的设计会对不同的算法产生什么样的影响。
* 在这本书中，我们使用了不同的编程语言（包括C、C++、Java还有Ruby）来描述算法。得益于此，我们能够使用你熟悉的编程语言对算法进行详细的讨论。
* 我们描述了算法的期望性能，并且根据经验提供了支持这些结论的证据。无论你相信数学还是相信实际的运行时间，你都会被我们说服。
对软件工程师、程序员以及设计师来说，我们希望这本书能够非常有用。为了达到目标，你需要参考大量的关于实际解决方案和算法的资料，才能够解决手头的实际问题。你已经知道了如何用多种语言编写一个程序。你也知道了计算机科学的关键数据结构，例如数组、链表、栈、队列、散列表、二叉树还有有向图或者无向图。你不需要实现这些数据结构，因为它们大都在库函数中可以找到。
我们希望你能从这本书中学到如何选择并且测试解决方案以快速高效地解决问题，也能够学到一些高级数据结构和一些使用标准数据结构的新方法，来改善程序的性能。在选择算法时，当你能够知道什么样的决定可以改善解决方案的效率，这样能够提高你解决问题的能力。
本书组织方式
本书被分为三个部分。第一部分（第1章～第3章）介绍了算法的必要数学基础，以便于读者理解本书的描述。在每个算法的论述中，我们使用了一种模式化的格式。我们仔细地设计这个格式，确保前后一致。第二部分（第4章～第9章）介绍了一系列的算法。这些章节的每个独立部分都是一个完备的算法描述。
第三部分（第10章和第11章）为那些感兴趣的读者提供一些较为高深的资源。当没有一个高效的解决方案来解决问题，而且“所有的其他的失败”为解决问题提供了有意义的线索的时候，这个部分就能够告诉我们如何利用这些线索来解决问题。我们最后以一个重要领域的讨论结束本书。这个讨论在第2章之所以被忽略，是因为它的内容太过高深，太过前沿，甚至还没有被证明。第四部分包括了一个附录，这个附录描述了本书每章中对算法进行评测的方法以及数学分析。在业界，这是一种标准的基准测试方法，但是几乎没有算法教科书介绍这个方法。
本书体例
在印刷上的一些例行惯例：
代码（Code）
这些代码都是直接取自代码库，是现实中使用的代码。
斜体（Italic）
表示这个术语用于描述算法和数据结构。同样在伪代码描述中表示变量。
等宽字体（Constant Width）
表示实现中的软件元素，例如Java类、C语言的数组名称以及常量（true或者false）。
小型大写字母（SMALL CAPS）
表示算法名称。
在本书中，我们引用了大量的书籍、文章和网站。这些引用都用括号标示出来，例如（Cormen等，2001），每一章最后部分列出本章所使用的参考文献。正文中的引用列出作者的名字和文献的年份。
本书中的所有URL都在2008年8月时验证有效，而且我们抛弃了那些看起来不久就会失效的URL。短URl，例如http://www.oreilly.com，直接在文本中使用；否则，这些URL会放入参考文献中。
代码使用说明
本书的目的是帮助你更好地完成工作，一般来说，你可以在程序和文档中直接使用本书代码。除非你需要重构这些代码的重要部分，否则你不需要联系我们获得许可。例如，你可以编写一个使用了本书中一些代码的程序而不需要许可。销售或者分发来自O誖eilly出版书籍中的样例不需要许可。引用本书来回答问题或者引用样例代码也不需要许可。在你的产品文章中过度地使用本书中的代码也不需要许可。我们希望，但是不要求标明归属。一个归属说明通常包括标题、作者、出版商和ISBN。例如：“George T. Heineman，Gary Pollice和Stanley Selkow编写的《Introuduction to Algorithms》。版权属于George T. Heineman，Gary Pollice和Stanley Selkow，978-0-596-51624-6”。
如果你觉得你需要使用代码的情况超出了我们的允许范围，那么请联系：permissions@oreilly.com。
批评与建议
请将您对本书的宝贵意见及问题告诉我们。来信请寄：
O誖eilly Media, Inc.
1005 Gravenstein Highway North
Sebastopol, CA 95472
800-998-9938 (in the United States or Canada)
707-829-0515 (international or local)
707-829-0104 (fax)
本书也有相关的网页，我们在上面列出了勘误表、范例以及其他一些信息。你可以访问：
http://www.oreilly.com/catalog/9780596516246
对本书做出评论或者询问技术问题，请发送E-mail至：
bookquestions@oreilly.com
希望获得关于本书、会议、资源中心和O誖eilly网络的更多信息，请访问：
http://www.oreilly.com
致谢
我们感谢书籍的审阅者，感谢他们对于本书细节的关注以及所给出的建议，这些建议提高了本书的质量。他们是：Alan Davidson、Scot Drysdale、Krzysztof Duleba、Gene Hughes、Murali Mani、Jeffrey Yasskin和Daniel Yoo。
George Heineman感谢那些带领他走入算法世界的人，包括Scot Drysdale教授（达特茅斯学院），Zvi Galil（哥伦比亚大学）。同样，George也感谢他的妻子Jennifer，他的孩子Nicholas（他一直想要知道爸爸在写什么便条）和Alexander（出生于我们书籍定稿时）。
Gary Pollice感谢他的妻子陪伴他走过了40年的美好时光。他同样感谢WPI计算机科学系提供给他的伟大工作和优雅的环境。
Stanley Selkow感谢他的妻子Deb。这本书是在他们相伴走过的时光中的又一个结晶。
参考文献
Cormen, Thomas H., Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, Second Edition. McGraw-Hill, 2001.
Knuth, Donald E., The Art of Computer Programming, Volumes 1-3, Boxed Set Second Edition. Addison-Wesley Professional, 1998.
目录
第1章　 算法真得很重要 1
理解问题 1
如果需要，尽可能用实践检验 2
解决问题的算法 4
花絮 5
故事的寓意 5
参考资料 6
第2章　 算法的数学原理 6
问题样本的规模 6
函数的增长率 8
最好最坏和平均情况下的性能分析 10
最坏情况 12
平均情况 12
最好情况 13
性能族 13
讨论0：常数级算法的性能 13
讨论1：对数级算法的性能 14
讨论2：次线性的算法的性能，时间复杂度为O(nd)，d<1
讨论3：线性算法的性能 15
讨论4：nlogn算法的性能 18
讨论5a：二次方的算法性能 19
讨论5b：性能不明显的计算 20
基准测试 22
最后一点 23
参考文献 24
第3章　 模式和领域 24
模式和领域 24
模式：一种交流语言 24
算法模式的形式 25
算法模式的格式 25
伪代码模式的格式 26
设计格式 27
基于经验的评价格式 28
领域和算法 28
浮点计算 29
参考文献 35
第4章　 排序算法 35
排序算法 36
概述 36
术语 36
表述 36
可比较的元素 37
稳定排序 38
分析技术 38
通用输入 39
插入排序 39
使用环境 39
驱动因素 40
解决方案 40
结论 41
分析 41
中值排序 42
使用环境 42
驱动因素 45
解决方案 45
结论 45
分析 46
快速排序 49
使用环境 50
解决方案 50
结论 51
分析 51
变种 51
选择排序 53
堆排序 54
使用环境 55
驱动因素 55
解决方案 55
分析 57
变种 57
计数排序 57
使用环境 58
驱动因素 58
分析 59
桶排序 59
使用环境 59
驱动因素 59
解决方案 60
分析 62
变种 63
选择排序算法的标准 64
综合分析基准测试结果 65
双浮点数的基准测试结果 66
参考文献 68
第5章　 查找 68
概述 68
顺序查找 69
输入/输出 70
使用环境 70
驱动因素 70
解决方案 70
结论 71
分析 72
变种 72
二分查找 73
输入/输出 73
使用环境 73
驱动因素 73
解决方案 74
结论 75
分析 75
变种 76
基于散列的查找 76
输入/输出 77
使用环境 77
驱动因素 79
解决方案 80
结果 81
分析 81
变种 84
二叉查找树 85
输入/输出 85
使用环境 85
驱动因素 86
解决方案 87
结论 88
分析 88
变种 88
参考文献 89
第6章　 图算法 89
概论 89
图 89
存储问题 91
图分析 91
数据结构设计 92
问题 92
深度优先搜索 93
输入/输出 95
使用环境 95
解决方案 95
分析 97
广度优先搜索 97
输入/输出 98
使用环境 98
解决方案 98
分析 100
单源最短路径 100
输入/输出 100
解决方案 101
结论 102
分析 102
变种 105
比较 107
所有点对最短路径 108
解决方案 109
分析 111
最小生成树算法 111
解决方案 112
结论 113
分析 113
变种 113
参考文献 113
第7章　 人工智能中的寻径 113
概述 114
博弈树 114
搜索树 114
博弈树 114
搜索树 116
关键思想 118
表示状态 118
计算可行走法 118
使用启发式信息 119
最大扩展深度 119
假设 120
深度优先搜索 120
输入/输出 120
假设 121
使用环境 121
解决方案 121
结论 121
分析 122
广度优先搜索 125
输入/输出 126
使用环境 126
解决方案 126
结论 127
分析 127
A*搜索 127
输入/输出 128
假设 128
使用环境 128
解决方案 129
结论 130
驱动因素 131
分析 131
变种 132
相关算法 132
迭代加深 132
输入/输出 135
假设 135
使用环境 135
解决方案 136
结论 136
分析 137
变种 137
NegMax 137
输入/输出 137
使用环境 138
解决方案 138
结论 138
分析 138
AlphaBeta 139
输入/输出 140
解决方案 140
结论 141
分析 141
参考文献 142
第8章　 网络流算法 143
概述 143
网络流 144
最大流 145
输入/输出 145
输入 145
输出 146
解决方案 146
结论 148
分析 148
优化 149
相关算法 150
输入/输出 151
解决方案 152
分析 153
最小开销流 154
转运问题 155
运输问题 156
任务分配问题 156
线性编程 156
参考文献 158
第9章　 计算几何 158
概述 158
计算 161
假设 162
计算几何经典问题 162
凸包 162
计算线段集的相交 163
寻找最近邻点 163
回答基于范围的查询 164
总结 164
凸包扫描 164
输入/输出 165
假设 165
使用环境 165
驱动因素 166
解决方案 166
结论 166
分析 167
变种 167
相关算法 168
线段扫描 169
输入/输出 169
使用环境 170
驱动因素 170
解决方案 170
结论 173
分析 173
变种 176
最近点查询 176
输入/输出 177
假设 177
使用环境 177
驱动因素 178
解决方案 179
结论 181
分析 181
变种 183
范围查询 183
输入/输出 183
假设 183
使用环境 183
驱动因素 183
解决方案 183
分析 185
参考文献 186
第10章　 最后的招数 187
另类算法 187
近似算法 187
离线算法 188
并行算法 188
随机算法 188
估算集合的大小 188
估算搜索树的大小 189
结果可能出错却可以衰减错误率的算法 190
检测数据库间的不一致 191
零知识证明 191
参考文献 192
第11章　 尾声 192
概述 193
原则：了解数据 193
原则：将问题分解至更小的问题 193
原则：选择正确的数据结构 194
原则：空间换时间 194
原则：如果没有显而易见的解法，使用搜索 195
原则：如果没有显而易见的解法，将问题归约为另一个有解的问题 195
原则：编写算法难，测试算法更难 195
第1章　 算法真的很重要
算法真的很重要！在哪些情况下使用哪种算法会给你编写的软件的性能带来巨大的差异。如果你不信的话，那么请看看Gray是怎么通过一些小小的分析，选择了一个正确的算法，扭转了整个败局。1
Gray曾经在一个有着很多天才软件开发者的公司工作。和大多数有着很多天才的组织一样，这里有着层出不穷的伟大想法，这些天才们将这些伟大想法实现并且集成到了软件产品中。例如Graham，他从公司创立之初就加入了这个公司。Graham曾经思考过一个问题：如何知道一个程序是否存在内存泄漏，这是当时C和C++程序都存在的一个问题。如果一个存在内存泄漏的程序运行足够长时间，那么这个程序会由于内存耗尽而崩溃。任何一个存在此类问题的程序都不支持自动内存管理和垃圾回收。
Graham决定编写一个库，以包装操作系统的内存分配以及回收函数，例如malloc()、free()、还有他自己的函数。Graham的函数将每次内存的分配以及回都收记录在一个特定的数据结构中，这样在程序结束之后，程序员能够查询到这些记录。这些包装函数记录这些信息，并且调用操作系统函数来进行内存管理。Graham只花了几个小时就实现了这个库而且能够正常被调用执行。但是现在有一个问题：调用了Graham的库的程序运行得如此缓慢，以至于没有人会去使用它。这是真的名副其实地缓慢。你可以先启动程序，然后离开去喝一杯咖啡，或许喝一壶咖啡也可以，然后回来，你会看到程序还在缓慢地运行着。这种速度当然不能够接受。
为了解决这个问题，Graham很快就了解了操作系统以及内部工作原理。他是一个极其优秀的程序员，能在一个小时内写出其他程序员需要一天才能写出的代码。他已经在大学学习了算法、数据结构以及其他标准课程，所以这点事情肯定难不倒他。那么为什么使用了这些包装的函数，程序会执行的如此缓慢呢？看来，这就是一个典型的知道如何使程序运行，却不知道如何使程序运行得快的案例。但是像很多具有创新精神的人一样，Graham已经在思考他的下一个程序，而不是回到他的那个内存泄漏程序中继续寻找问题。于是，他希望Gray检查一下这个库，看看能不能修复运行缓慢的问题。Gray是一个编译以及软件工程方面的能手，他擅长精炼代码，使得它们可供发布。
在开始深入代码之前，Gray希望先和Graham谈谈这个程序。这样的话，他能够更好地理解Graham如何构造他的解决方案以及为什么他选择了这样的实现方式。
注意：在继续读下去之前，想想如果是你，你会问Graham一些什么。然后在接下来的部分，看看你是否能够得到和Gray相同的信息。
理解问题
解决问题最好从大局观开始：理解问题，找出潜在原因，然后深入挖掘细节。如果你觉得你知道原因，然后决定解决这个问题，那么你可能会出错，或者你也许不会发现其他的更好的答案。Gray首先希望Graham能够描述这个问题以及他的解决方案。
Graham说他的目的是希望能够知道一个程序是否存在内存泄漏。他想知道这个问题答案的最好方法是记录所有被程序分配的内存，不管这些内存是否在程序终止之前被释放掉了，同时也记录用户的程序在哪儿请求内存分配。他的解决方案是构建一个包含三个函数的小型库。
malloc()
一个包装了系统内存分配函数的函数。
free()
一个包装了系统内存回收函数的函数。
exit()
一个包装了系统退出函数的函数。
那就写一个使用了这个库的程序来进行测试吧，在程序中调用库中自定义函数而不是系统函数。自定义的malloc()和free()将会记录每一次内存分配和释放。当程序测试结束的时候，如果记录中，每一个内存分配接下来都有相对应的内存释放，那么就证明没有内存泄漏。如果存在内存泄漏，那么Graham的函数将会记录相关信息以供程序员参考。当调用自定义的exit()函数的时候，在程序实际退出之前，将会显示内存的分配释放记录。Graham将他的解决方案用图表示出来，如图1-1。
图 1-1　Graham的解决方案
描述貌似已经很清楚了。除非Graham在他包装了系统函数的代码中犯了一些相当严重的错误，否则还真的很难想象在包装的代码中存在性能问题。如果存在的话，那么所有的程序的缓慢程度都应该与调用的次数成比例。于是Gray询问Graham测试过的程序是否存在性能差异。Graham解释说，通过性能剖析发现，那些小的程序通常能够在一个勉强可以接受的运行时间内，不管这些程序是否有内存泄漏。但是，那些需要进行大量处理工作和有内存泄漏的程序运行起来慢得不像话。
如果需要，尽可能用实践检验
在继续深入之前，Gray希望能够较好地了解程序的运行状况。他和Graham坐下来一起写了一些小程序，通过调用这个库来检查这些程序是如何运行的。也许他们能够更好地明白是什么导致了这个诡异的问题。
你会进行哪些实验呢？你的程序将会是什么样？
Gray和Graham的第一个测试程序（程序A）如例1-1所示。
例1-1：程序A代码
int main(int argc, char **argv) {
　 int i = 0;
　 for (i = 0; i < 1000000; i++) {
　　malloc(32);
　 }
　 exit (0);
}
他们运行了这个程序然后等待结果。这个程序运行了数分钟。即便在当时的计算机速度比较缓慢的情况下，这个运行时间也很明显不可接受。当程序运行结束的时候，记录显示有32MB的内存泄漏。那么如果程序中所有分配的内存都被释放了会出现什么情况呢？他们做了一点小修改，这就是程序B，如例1-2所示。
例1-2：程序B代码
int main(int argc, char **argv) {
　 int i = 0;
　 for (i = 0; i < 1000000; i++) {
　　 void *x = malloc(32);
　　 free(x);
　 }
　 exit (0);
}
编译并且运行程序B，程序B在几秒内就运行结束了。Graham确信这个问题和程序结束的时候没有释放的内存大小相关。但是他找不出问题在哪儿出现。他搜寻了整个代码，花费了数个小时却也找不出问题在哪儿。Gray并不像Graham那样确信问题是与内存泄漏的数目相关。他建议做更多的实验，并且对程序做了另一次的修改，将所有的内存释放操作集中到程序的最后。如例1-3所示。
例1-3：程序C代码
int main(int argc, char **argv) {
　　int i = 0;
　　void *addrs[1000000];
　　for (i = 0; i < 1000000; i++) {
　　　　addrs[i] = malloc(32);
　　}
　　for (i = 0; i < 1000000; i++) {
　　　　free(addrs[i]);
　　}
　　exit (0);
}
这个程序就像第一个程序那样缓慢地运行着！这个例子证明了性能问题并不是由内存泄漏的数量导致的。不仅如此，这个程序让Gray明白了问题原因的真正所在。并不是程序结尾的内存分配次数导致性能问题，而是任意时刻没有被释放的内存的最大数量严重影响了整个程序的性能。如果程序本身的内存泄漏并不是影响问题的唯一因素，那么Graham维护内存分配以及释放的记录的方法就存在一些问题。在程序B的执行过程中，任何时刻都没有超过32字节的未释放内存。但是第一个和第三个程序运行的时候却有100万个内存分配操作没有相应的释放操作。分配和释放内存并不是关键，所以问题肯定和Graham记录内存分配和释放请求的代码有关。
Gray询问了Graham他是如何记录分配的内存的。Graham回答说他使用了一个二叉树来记录，每一个节点都记录了指向子结点的指针（若有的话）、指向分配内存的地址、分配的大小以及程序在哪儿进行的分配请求。Graham还补充道他是使用内存地址作为节点的键值，因此不能重复，这个方法使得插入和删除内存分配的记录更加容易。
使用二叉树通常比简单地使用有序链表更加高效。假设有一个包含了n个元素的有序链表，这个表中的每个元素被请求的概率是相等的。那么一个寻找表中一个元素平均将要花费n/2次比较。从表中插入或者删除元素平均也需要大约n/2次操作。计算机科学专业的教科书描述这些操作（查找、插入和删除）的性能为O(n)，实际上这些操作的数量的两倍就是和这个链表长度有关，进行这些操作花费的时间期望也是这么多。7
使用一棵二叉树能够将上述操作降到O(logn)的花费，虽然代码可能有一些难于编写和维护。跟链表的时间花费不一样，使用了二叉树，这些操作的花费仅仅是常数量的增长。当处理1000000个元素的时候，我们只需要平均检查20个元素，相比有序链表需要500000次操作，效率之高可想而之。如果键值是平均分布在树中的，那么使用二叉树是一个很好的选择。如果键值不是平均分布的，那么树会变得扭曲，不平衡，在某种程度上这个数据结构就会认为不适合用来查找。
知道了一些关于二叉树以及如何工作的知识后，Gray询问Graham一个价值64000美元（毕竟这个数字是对数）的问题：“你对这个二叉树进行了平衡处理吗？”Graham非常惊讶，因为他是一个优秀的软件工程师，不可能不知道这样简单的东西。“没有，为什么我需要做这个？这个操作使得代码更加复杂了。”不过事实的确是由于Graham没有做平衡处理，使得这棵树右倾到操作时间近似线性的程度，这种情况下更像是一个有序链表而不是一棵二叉树。想知道为什么吗，看看图1-2中的两棵二叉树。在a树中顺序插入数字1～15。它的根节点值为1，从根节点出发到达值为15的节点需要经过14个节点。b树插入了相同的数字，不过是按照这样的顺序：<8，4，12，2，6，10，14，1，3，5，7，9，11，13，15>。在这种情况下下，根节点的值是8，不过从根节点到其他节点的路径在3个节点或者更少。我们在第5章将会看到，查找时间直接和最长路径的长度相关。
图1-2：构建两棵二叉树样例
解决问题的算法
如果一棵二叉查找树的根节点到任意一个叶子节点的路径长度都基本相等，那么这棵树就是二叉平衡查找树。定义depth(Li)为从根节点到叶子节点Li的路径长度。如果一棵二叉树具有良好的平衡度，那么对任意两个叶子节点L1和L2来说，depth(L1)和depth(L2)的差的绝对值，即|depth(L1)-depth(L2)|≤1；同样对于任何一个叶子节点Li来说8，depth(Li)≤log(n)。Gray翻阅了他的算法书籍，决定对Graham的代码进行修改，用更加平衡的红黑树记录内存的分配。红黑树（Cormen et al., 2001）是一个平衡二叉树的高效实现。在红黑树中，给定两个叶子节点L1和L2，depth(L2)/depth(L1)≤2；同样对任意叶子节点Li来说，depth(Li)≤2*log2(n+1)。也就是说，一棵红黑树是大致地平衡，它确保这样一个性质，在红黑树中，不存在一条路径，其长度是另外一条路径的两倍。
Gray花了几个小时进行了修改和测试。当他完成之后，他将结果演示给Graham看。他们使用新的库，重新运行了上面的三个程序。程序A和程序C仅仅只是比程序B多花了几毫秒而已。性能很明显地大幅改善了，反映在速度提高了近5000倍。这样的性能改善是想当然的，你可以看到平均访问节点的数目从500000个降到了20个。事实上，这是数量级的降低：你也许期望能够加速25000倍，但是对树进行平衡的操作开销降低了部分性能。尽管如此，性能的改善仍然是惊人的，Graham的内存泄漏检测程序（包括Gray的修改）将再下一个产品中发布。
花絮
已知使用红黑树的效率，原生malloc()的实现可能会使用这个结构吗？毕竟，内存分配在某种程序上必须维护分配的区域集合，以使得这些区域将来能够被安全地释放。同样，注意到上述程序每次请求32字节的内存分配，那么每次请求的内存大小是否会影响malloc()和free()请求的性能？为了研究一下malloc()的行为，我们又进行了一系列的试验。首先，我们记下分配4096个内存块的时间，内存块的大小n从1字节取到2048字节。然后我们看看释放相同大小的内存需要多久，不过将才需三种策略来释放。
freeUp
按照分配的顺序释放，和程序C类似。
freeDown
按照分配的顺序逆序释放。
freeScattered
一次性释放所有内存。
对于每个n的值，我们进行100次试验，并且去掉最好的和最坏的成绩。图1-3显示了剩下98次试验的平均结果。正如我们所预料的，分配操作的开销与n的增长呈线性关系。令人惊讶的是，释放内存的方式在性能上有比较大的差异。freeUp的性能最好，freeDown比freeUp慢4倍左右。
图1-3：malloc/free请求的性能分析
经验表明，现在还不能回答是否原生malloc()以及free()使用了二叉树（无论是否平衡！）来记录信息。为什么内存释放的顺序会引起性能的差异，如果不查看free()的源代码，这个问题没有一个简单的解释。
我们给出这个例子是有两个目的。第一，内存分配以及释放背后的算法是惊人的复杂，这些算法也高度依赖于操作系统（也就是复杂的计算机）的特性。我们在整本书中将会看到，不同的算法都有他们自己最佳使用的情况。开发者能够根据问题的特殊信息使用相应的算法来改善性能。第二，我们在整本书中描述了不同的算法，并且解释了为什么一个算法会比另外一个算法表现更好。我们还是坚持使用数学来解释这一切。
故事的寓意
上面那个故事是真实的。你要知道，算法真得很重要。你也许会问树平衡算法真的是这个问题的优化方案吗？这是一个很好的问题，对于问这个问题的人，我们会问另外一个问题：它确实很关键重要吗？对于一个问题来说，寻找正确的算法就像是寻找正确的解决方案一样。现有的算法已经可以很好地工作了，我们无需寻找最完美的解决方案。当选择一个解决方案的时候，你必须在它的开销和带来的好处之间寻找一个平衡点。Gray的实现方案是能够被改进的，或者优化代码，或者采用不同的算法。但是，内存泄漏检测软件的性能不仅仅是可接受的，而且还必须是能够满足预期使用的，任何额外的改进将会产生没有收益的开销。
按需选择可以接受的算法，这种能力是非常重要的，每一个优秀的软件开发者都应该具有。并不需要你能够对算法进行详细的数学分析，但是你必须能够理解这些分析。并不需要你发明新的算法，但是你要知道哪个算法可以解决手头的问题。本书就是希望能够帮助你提高这种能力。当你具备这种能力之后，你的软件开发工具箱中又多了软件开发利器。
参考资料
Cormen, Thomas H., Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, Second Edition. McGraw-Hill, 2001.
第2章　 算法的数学原理
在解决问题之前，我们可以试着猜测下，在这个问题所依赖的平台（或者平台家族）和数据上，哪个算法将会获得最好的性能。计算一个算法的期望运行时间本质上是一个数学运算过程。在本章，我们将透过现象看本质，阐述隐藏在这些复杂计算内的数学工具以及使用方法。通过本章的阅读，读者应该能够理解本书将要使用的数学术语。
贯穿本章（实际上是贯穿整本书）的一个共同主题就是所有的假设和近似操作都会花费常数时间，但是最终我们得到抽象结论的时候，都会忽略这些常数时间。在所有的平台上，相比影响本书所述的算法性能的其他因素来说，这些常数都是小到可以忽略不计的。
问题样本的规模
问题样本是解决问题的程序所使用的数据集，在大部分问题中，随着已编码样本的规模的增长，程序的执行时间也不断增加。同时，紧凑地对样本数据进行编码（也许使用压缩技术）可能会不必要地降低程序的执行效率。寻找一条最优的样本编码方式是极其困难的，因为问题发生在现实世界，而且机器需要理解这种编码方式。我们需要合理地编码样本数据，以供计算机进行求解。让我们看看接下来边栏“编码的样本”中对数字x的两种表示方法。
编码的样本
给你一个很大的数字x，要求计算x的二进制形式中1的个数的奇偶性（也就是说，1的个数是奇数还是偶数）。例如，如果x=15137300128，其二进制表示是：
x2=1110000110010000001101111010100000
可以看到1的个数是偶数，我们考虑下面两种可行的编码策略：
x的编码1：1110000110010000001101111010100000
x的这个二进制表示方法使用了34个字节。注意到log2(x)的值是33.82，因此这个编码方式是最理想的。但是为了计算1的个数的奇偶性，需要检查每一个位。这种编码方式下，计算奇偶性的最佳时间的增长与x的长度n（x的对数）增长呈线性关系。
x也能够用下面的方式来表示，使用n个位，再加上一个额外的校检位来表示1的数目的奇偶性。
x的编码2：1110000110010000001101111010100000[0]
我们可以看到x 的这种编码方式的最后一个位是0，这表示1的个数为偶数个（偶数用0表示）。对于这种表示法，需要35个字节。在两种编码方式中，样本编码的规模都随x的值对数增长。但是，在第一种编码方式中，计算奇偶性最佳算法的时间增长情况与x的编码规模的增长呈对数关系，但是第二种编码方式中，最佳算法只需要花费常数的时间，而且与x编码规模无关。
我们在评价算法，尽量假设算法是否能够被有效实现不取决于问题样本的编码。在上一个问题中，我们看到，虽然编码方式在规模上差不多，但是在查询奇偶性的这个关键操作上，它们的性能差异非常明显。
选择合适的问题样本编码取决于将会进行的操作。设计一个高效的算法通常是从选择一个合适的数据结构开始的，数据结构通常是在计算机中表示将要解决的问题。如图2-1所示。
图2-1：问题样本的复杂编码
由于不能够限定问题样本的规模，所以我们假设样本的编码使用一种简洁的方式，可以大致被接受的。当对n个数字进行排序时，我们根据惯例在平台上用一个字来表示数字，这样样本的规模就是n。可能有些数字需要用不止一个字来表示，所以样本的规模也会受到相应的影响。例如，相比使用32位存储整数的类似算法，使用64位来存储整数的算法需要花费两倍时间。
为了存储数据集，大多数编程语言都支持数组，数组是连续的内存区域，这些区域都可以通过一个整数索引i直接快速存取。数组是一维的，每个元素大小用一个字来存储，例如整数数组，布尔数组，或者字符数组，字的大小是平台相关的。有些数组是多维的，这样能够更丰富地表示数据，图2-1所示，“编码对性能的影响”指出了编码能够影响一个算法的性能。
编码对性能的影响
假设一个程序需要处理元素周期表，有三个频繁的操作，它们是：a) “第N个元素的原子量是多少？”；b)“x元素的原子数是多少？”；c)“第N个元素的名字是什么”。一个有趣的挑战是：2008年1月的时候，第117个元素还仍未发现，但是第118个元素已经被发现，叫做Ununoctium。
周期表的第一种编码：两个数组，elementName[]，存储元素的名字，还有elementWeight[]，存储元素原子量。
周期表的第二种编码：用一个长度为2626个字符的字符串来表示整个周期表。最开头的62个字符是：
1 H Hydrogen 1.00794
2 He Helium 4.002602
3 Li Lithium 6.941
为了理解编码对于性能的影响，我们做了32次实验，每次实验包含100000个随机请求（包括无效的）。我们舍弃了最好的和最坏的，留下了30次实验的结果，下面这张表表示了余下30次实验执行时间的平均值（和标准差），用毫秒表示：
　　　　　原子量查询 元素序号查询 元素名称查询
编码1　　2.1±5.45　　　131.73±8.83　　　2.63±5.99
编码2　 635.07±41.19 1050.43±75.60　664.13±45.90
就像预期的那样，编码2的性能比编码1的性能差很多，因为采用编码2的时候，每一次请求都要执行一次字符串操作。编码1能够有效地处理原子量查询和元素名称查询，但是元素序号查询需要对整个表进行查找，因为表是元素序号无序的。
这个例子告诉我们，不同的编码会在执行时间上可能产生巨大的差异。同样也告诉设计人员必须根据将要进行的操作选择合理的编码来优化性能。
由于编程语言和平台的巨大差异，算法研究人员认为，即使给定编码方式，计算出精确的性能开销也是不可能的。因此，他们假定，如果一些算法的性能开销仅仅是常数倍差异，那么这些性能开销可以被认为是渐进等价的。但是这个假定在现实世界中是不可行的（谁会愿意将自己的应付账单乘以1000呢？），因此只是在比较算法的时候作为通用的手段。当实现一个算法的时候，对细节的重视反映在关注常数倍差异。
函数的增长率
一个广为接受的描述算法的方法是使用执行时间的增长率作为问题样本规模的函数。但是这种方法是抽象地描述一个算法的性能，忽略了细节问题。所以，在使用的时候需要对抽象背后的细节有一个清醒的认识。
程序都必须运行在某个平台上，在这里，平台的广义包括：
* 程序运行的计算机，包含了CPU、数据缓存、浮点运算单元以及其他芯片。
* 使用的语言、编译器/解释器以及生成代码的优化设置。
* 操作系统。
* 后台运行的其他进程。
一个基本的假设是：上述组成平台的任何条件的改变，都会改变程序的执行时间，但只是在原有的时间上乘以一个常数因子。在这里，我们简要地讨论一下顺序搜索算法，这个算法会在第5章讲到。顺序搜索算法会顺序搜索列表中的所有n个元素，直到找到想要的值v。现在，我们假设：
* 列表中有n个不同的元素。
* 将要寻找的元素v在这个列表里面。
* 列表中每个元素可能为v的概率都是相等的。
通过计算顺序搜索算法平均搜索多少个元素，我们能大致了解这个算法的性能情况。因为我们知道v肯定在这个列表里面，而且每个元素可能为v的概率都是相等的，用数学语言描述就是，对于一个包含有n个元素的列表，平均搜索的元素个数E（n）就是所有次数总共搜索元素个数的和除以搜索次数。
因此，上述假设作为前提的条件下，顺序搜索算法搜索了这个表中的大约一半元素。如果列表的元素个数加倍，那么顺序搜索会大约搜索原来两倍的元素；期望的搜索数目是n的线性函数。也就是说，期望搜索数目可以用 c*n来表示，c为常数。这里的c为1/2。关于性能分析的一个基本的观点是，在长时间的运行中，常数c是不重要的，因为最重要的影响性能的因子是问题样本的规模n，随着n越来越大，那么错误率就如：
变得不再重要，实际上，它们的比值接近1说明了：
虽然对于比较小的n来说，预计错误会是致命的。但是在上下文中，我们所谓的顺序搜索算法期望搜索数目的增长率是线性的。所以，在大样本规模情况下，我们可以忽略作为乘数的常数，而主要关注样本的规模。
依据增长率这个抽象的概念选择算法时，我们需要注意以下问题。
常数的问题
这就是为什么我们需要使用超级计算机和定期升级我们的计算机。
n并不总是非常大
在第4章我们将会看到，快速排序执行时间的增长率比插入排序执行时间的增长率要低。但是在小数据集上，插入排序表现得比快速排序要好。
算法的增长率决定了算法在逐渐增长的大数据集上的性能表现。我们在一个更复杂的例子上使用这个基本的原理。
给定一个排序任务，对四个排序算法进行评价。这个任务是对n个随机字符串进行排序。n的取值从1～512，对于每个n的值，我们都将进行50次试验，并且舍弃掉最好和最坏的试验结果，图2-2的图描述了剩下48次实验的平均运行时间（毫秒）。这些结果的差异实在令人惊异。
图2-2：小数据集上四个算法的比较结果
我们设计一个函数来解释这个结果，这个函数能够预测每个算法在规模为n的数据样本上的性能。我们不太可能精确地知道这个函数的具体形式，我们只能使用商业软件对结果使用统计方法进行回归分析，描绘出一条趋势线。趋势线与实际数据的拟合度设为R2，取值为0～1。R2越趋近于1，表示拟合度越高。例如，R2=0.9948表示，由于数据的随机变化，只有0.52%的几率造成趋势线和数据不拟合。
第四种排序法很明显地是四种算法中最差的，在电子数据表上描绘512个数据点，与数据相符合的趋势线是：
y = 0.0053*n2-0.3601*n+39.212
R2 = 0.9948
我们看到，R2的值如此地接近1，这是一个非常精确的预测。第二种排序法在给定的数据集上提供了最快的性能。它的行为可以用如下的趋势线来描述：
y = 0.05765*n*log(n)+7.9653
第二种排序法比第三种排序法的速度快，但最快也可能只比第三种排序法快10%。第一种排序法表现出了两种不同的性能特征。在数据集少于39个字符串的时候，性能表现为：
y = 0.0016*n2+0.2939*n+3.1838
R2 = 0.9761
但是，数据集在40个或者更多时，性能表现为：
y = 0.0798*n*log(n)+142.7818
这些表达式中的系数完全取决于这些算法运行的平台。就像之前描述过的那样，这些相同的差异（例如平台）并不重要。n的长期变化趋势支配着这些算法的行为。事实上，图2-2描绘了同一个算法在不同规模的数据集下的表现。直到数据集的规模n变得足够大的时候，算法之间的差异才变得明显。
算法设计人员试图去理解算法之间的性能差异。这些算法的源代码是来自开源的代码库，正因为这些算法的源代码的开源，所以算法设计人员能够从代码入手，分析他们的选择如何影响总的运行时间。第一种排序法反映了在Linux 2.6.8内核下快速排序的性能。当审阅源代码时（源代码可以在任何Linux的代码库中找到）*，一个人发现这样的注释：“这个快速排序例程是由Bentley和McIlroy设计的”。Bentley和Mcllroy（1993）描述了如何对快速排序进行优化，他们通过在不同的样本规模下采用不同的策略，例如规模小于7的，规模在8～39的以及40或者更大的规模下采取的策略。实验结果表明，这个隐藏的优化手段是非常有效的。
http:11xr.Linux.no/Linux+v2.6.11.11/fs/xfs/support/qsort.c
最好最坏和平均情况下的性能分析
现在有一个问题，对于所有的输入来说，前面得到的结果是否都成立呢？第二种排序法在少量字符串的时候性能也许是最好的。但是，输入数据有很多地方可能变化：
* 输入数据可能有1 000 000个字符串。算法如何处理如此大规模的数据？
* 输入数据可能会是部分有序状态，也就是说几乎所有的元素所在的位置离最终位置并不是很远。
* 输入数据可能包含重复的值。
* 无论输入数据的规模n是多少，输入数据都可以从一个小得多的数据集扩展而来，不过会有相当多的重复值。
虽然从图2-2上来看，第四种排序法在排序n个乱序字符串的时候是最慢的，但是处理已经排序的数据却是最快的。但是，随着n的增长，第四种排序法的领先优势消失得非常快，我们从图2-3上可以看到，在对16个乱序的字符串进行排序时，第四种排序法就已经失去领头羊的位置了。
图2-3：处理完全或者几乎有序的数据时，排序算法的性能表现
尽管如此，假设一个包含n个字符串的输入，并且这个输入已经是几乎有序，其中n/4个字符串（占总字符串的25%）被交换到仅仅是离最终位置4个元素。最终结果如图2-4所示，我们看到第四种排序法性能表现远远好于其他的排序算法。
图2-4：处理几乎有序数据时，第四种排序法胜出
我们得到这样一个结论，对于许多问题来说，并不存在单一的最优算法。选择一个算法需要对问题有着充分的理解，并知道这个问题将要处理数据规模的概率分布情况，还有算法的实际行为也必须要考虑到。
在这里我们提供一些指导，算法通常会分成三种情况进行分析：
最坏情况
定义一类输入，在这类输入下，算法表现出了最坏的运行性能。算法设计人员需要明白，这类输入的共同性质阻止了算法高效地运行，而不只是针对特定的输入。
平均情况
平均情况是表示算法在随机给定的数据上期望的执行情况。通俗地说，一些输入可能会在某些特殊情况下耗费程序大量的时间，但是大部分的输入并不会这样。这个衡量标准描述了用户对算法性能的期望。
最好情况
定义一类输入，算法在这类输入下表现出了最好的运行性能。对于这类输入来说，算法只进行很少的计算。不过在实际情况下，最好情况很少出现。
通过分析三种情况，大致了解了算法的性能，那么接下来你需要为将要面临的问题选择一个算法。
最坏情况
大多数问题都可能会处理一些比n大的数据。任意给定一个n，算法或者程序在处理所有规模为n的数据，其性能可能会动态地发生变化。给定一个程序和n，这个程序的最坏运行时间就是处理所有规模为n的数据所需要的最长运行时间。
我们也看到，最坏情况是对整个世界的一个悲观的分析。但是我们还是非常关注最坏情况，因为：
追根刨底的欲望
这通常是对一个算法复杂度的最早的分析。
实际运行时的限制
如果你需要设计一个系统，协助外科医生进行体外循环心脏手术，那么长时间的运行（即使这种情况是不经常发生）当然不可能接受。
更正式地说，如果Sn是数据集合si中规模为n的子集，t表示算法在每一份数据上的运行时间，那么最坏情况下，对于所有si∈Sn，算法在Sn上的运行时间是t(si) 的最大值。我们将在Sn下的最长时间记做Twc(n)，Twc(n) 的增长率表示算法在最坏情况下的复杂度。
一般来说，没有足够的资源来计算每一份数据si，然后检查算法在哪份数据上表现最坏。于是，给定算法的描述，算法分析人员总是想方设法地精心准备可能会导致最坏情况的输入数据。
平均情况
现在要设计一个支持n个电话的电话系统，n是一个非常大的数目，要求在最坏情况下，即n/2位用户同时呼叫另外n/2位用户时，这个系统也能够正确地处理数据。虽然这个系统不会由于过载而崩溃，但需要花费过高的代价构造这样的情况。而且，n/2位用户同时呼叫另外n/2位用户发生的概率极小。也许可以设计一个花费较小的系统在过载的情况下很少会（或者从不）崩溃。但是我们还是必需借助数学工具来计算这个概率问题。
对于一个n个样本的数据集合，我们用一个概率分布Pr表示样本的出现概率，单个样本的出现概率为0到1，所有样本的概率的和为1。如果Sn是n个样本的数据集合，那么：
P21
如果t表示算法在单个样本的执行时间，那么在Sn上的平均运行时间是：
P21
也就是说，在样本si的实际执行时间，t(si) 将会与概率加权。如果Pr{si}=0，那么t(si) 的实际值将不会影响程序的期望运行时间。我们用Tac(n) 表示算法在Sn上的平均运行时间，那么Tac(n) 的增长率表示算法在平均情况下的复杂度。
回忆一下，当我们描述时间或者工作量的增长率时，我们一直忽视了常数，所以我们认为顺序搜索n个元素的平均情况为：
P21
探测（符合我们之前的假设），按照惯例，在符合这些假设的前提下，期望顺序搜索能够处理线性或者是n阶的元素。
最好情况
知道算法的最好情况是非常有用的，即便这种情况很少发生。在很多情况下，最好情况能让我们看到算法的最优状况。例如，线性搜索的最好情况是当它在n个元素中搜索v的时候，第一个元素恰好就是要找的那个。一个稍微有些不同的算法，我们叫做计数搜索（Counting Search），在n个元素中搜索v，并且记录v在表中出现的次数。如果v的计数是0，那么这个值是不存在的，所以会返回false，否则返回 true。注意，计数搜索总是会搜索整个表，因此，它的最坏情况是O(n)（和顺序搜索一样），最好情况还是O(n)，所以我们不能够使用这个算法，因为它的最好或者平均情况没有改善性能。
性能族
比较算法的时候，我们使用输入数据的规模n来评价算法的性能。这个方法被认为是比较算法的标准方法，并且在过去的半个世纪中不断地被改进。这样一来，我们就能够通过输入数据的规模，计算算法的运行时间，从而得知，哪个算法能够更好地适应一些异常规模的问题。性能评价的第二种方法是考虑算法将会耗费多少内存或者存储空间。随后我们将在各自的算法章节中讨论这个问题。
我们将要使用的本书特有的算法分类，按照效率降序排列，如下所示。
* 常数级
* 对数级
* 次线性级
* 线性级
* nlog(n) 级
* 平方级
* 指数级
我们现在进行一些讨论，陈述一下衡量这些性能的标准。
讨论0：常数级算法的性能
当本书分析算法性能时，我们将不止一次地强调原生的操作都是常数级的性能。很明显，这个声明并不是完全准确地描述了操作的性能，因为我们没有考虑到硬件问题。例如，比较两个32位的数x和y大小是否一样，这个操作耗费的时间与x、y的大小无关。常数的操作被定义为O(1)的性能。
那么比较256位的数字时，性能表现又如何呢？1024位呢？我们认为在给定k的前提下，比较两个k位的数字的操作将在常数时间内完成。关键在于问题的规模（例如x、y的值）不可能超过k。我们把额外的工作，例如k的倍增，也抽象为O(1)的性能。
讨论1：对数级算法的性能
一个酒保和顾客打了一个10 000美元的赌。“我将选择一个从1到1 000 000的数字，然后你能够每次猜1个数字，共猜20次；每一次猜过之后，我将会告诉你高了，低了或者是你赢了。如果你能在20个问题之内赢，我给你10 000美元，否则你给我10 000美元。”你会打这个赌吗？你也许会，因为你可以一直赢下去。表2-1给了一个场景，不过候选数字是从1到10。问一系列的问题，并且每个问题都把候选数据缩减了一半。
表2-1：猜1到10的例子
数字
第一次猜的数字
第二次猜的数字
第三次猜的数字
1
是5吗？高了
是2吗？高了
是1吗？你赢了
2
是5吗？高了
是2吗？你赢了
3
是5吗？高了
是2吗？低了
是3吗？你赢了
4
是5吗？高了
是2吗？低了
是3吗？低了，所以是4
5
是5吗？你赢了
6
是5吗？低了
是8吗？高了
是6吗？你赢了
7
是5吗？低了
是8吗？高了
是6吗？低了，所以是7
8
是5吗？低了
是8吗？你赢了
9
是5吗？低了
是8吗？低了
是9吗？你赢了
10
是5吗？低了
是8吗？低了
是9吗？低了，所以是10
每次根据酒保的回答，将可能的数字范围缩减一半。最后，可能的数字只剩下了一个；这种情况将会在[log(n)]次询问之后出现。将[x]归入到等于或者大于x的最小整数。例如，如果酒保选择了数字范围是1到10，那么你最多只需要猜测[log(10)]=[3.32]，即4次。
这种方法在1 000 000个数字的时候也同样可行。事实上，例2-1所示的猜数算法能够对于任何的范围[low，high]有效，并且在[log(high-low+1)]次猜测之后得到数字n。如果有1 000 000个数字，那么这个算法将在至多[log(1 000 000)]即E(19.93)，也就是说20次（最坏情况）知道是哪个数字。
例2-1：在范围[low, high]之间猜数字的java代码
// 计算需要多少次猜测，当n在范围[low, high]的时候
public static int turns(int n, int low, int high) {
　 int turns = 0;
　// 当还剩下多于两个数字时，继续
　while (high - low≤2) {
　　//将[low, high]范围的中间数作为猜的数字
　　turns++;
　　 int mid = (low + high)/2;
　　 if (mid == n) {
　　　 return turns;
　　 } else if (mid < n) {
　　　 low = mid + 1;
　　 } else {
　　　 high = mid - 1;
　　 }
　 }
　 //在这里。只剩下两个数字，我们猜其中一个，如果是错的话那么剩下那个就是对的了。因此还能剩下1次或者更多的猜测机会。
　 return 1 + turns;
}
对数级算法是非常高效的，因为它们能够快速收敛到解。一般来说，这些算法的成功之处在于它们每次将问题的规模缩减一半。这个猜测算法至多经过k=[log(n)]次迭代便可以得到解，在第i次（i>0）迭代的时候，算法在±e=2(k－i)个数中进行猜测。e可以看做是不确定的个数。在每一次迭代之后，e缩减一半。
另外一个例子中则展现了牛顿法如何高效地解决一元方程（也就是说，x取什么值，使得f(x)=0）。解x*sin(x)－5*x=cos(x)，设f(x)=x*sin(x)－5*x－cos(x)，其导数为f?x)=x*cos(x)+sin(x)－5－sin(x)=x*cos(x)－5。牛顿迭代计算出xn+1=xn－f(xn)/f?xn)。开始猜测x等于0，这个算法能够快速地给出一个正确解，x=－0.189302759，见表2-2。被用括弧[]围起来的二进制和十进制数表示精确位。
表2-2：牛顿法
n 十进制xn 二进制xn
0 0.0
1 －1.2 [1011111111001]0011001100110011001100110...
2 －[0.18]8516717588... [1011111111001000001]0000101010000110110...
3 －[0.1893]59749489... [101111111100100000111]10011110000101101...
4 －[0.189]298621848... [10111111110010000011101]011101111111001...
5 －[0.18930]3058226... [1011111111001000001110110001]0101001001...
6 －[0.1893027]36274... [1011111111001000001110110001001]00111100...
7 －[0.189302759]639... [101111111100100000111011000100101]01001...
讨论2：次线性的算法的性能，时间复杂度为O(nd)，d<1
在某些情况下，这种算法的性能好于线性算法，但还是不如对数算法高效。在第9章，我们将会讨论多维kd-tree它能够高效地划分n个多维点。如果这种树是平衡树，那么区间查询的查询时间将会是O(n1-1/d)。
讨论3：线性算法的性能
有一些问题的解决看起来明显地需要更多的工作。任何一个8岁大的孩子都知道7+5等于12。那么难一点的问题，37+45呢？一般来说，相加两个n位的数（an…a1+bn…b1）得到一个n+1位的cn+1…c1数字有多难？相加算法使用了如下的原生操作：
P26
例2-2是相加算法的一个Java实现，n位数字被用一个int数组表示。在本节的例子中，我们假设数组中的元素表示一个十进制数d(0≤d≤9)。
例2-2：Java的add实现
public static void add (int[] n1, int[] n2, int[] sum) {
　　int position = n1.length-1;
　　int carry = 0;
　　while (position >= 0) {
　　　　int total = n1[position] + n2[position] + carry;
　　　　sum[position+1] = total % 10;
　　　　if (total > 9) { carry = 1; } else { carry = 0; }
　　　　position--;
　　}
　　sum[0] = carry;
}
只要这个输入数据能够被存储在内存中，add就能够使用两个int数组n1和n2来计算两个数的加法。例2-3有一些小改动，这个实现能够更加高效吗？
例2-3：Java的last实现
public static void last(int[] n1, int[] n2, int[] sum) {
　　int position = n1.length;
　　int carry = 0;
　　while (--position >= 0) {
　　　　int total = n1[position] + n2[position] + carry;
　　　　if (total > 9) {
　　　　　　sum[position+1] = total-10;
　　　　　　carry = 1;
　　　　} else {
　　　　　　sum[position+1] = total;
　　　　　　carry = 0;
　　　　}
　　}
　　sum[0] = carry;
}
这个小改动确实影响了算法的性能吗？让我们考虑其他两个潜在因素，这两个因素将会影响算法的性能。
* 编程语言是一个因素，如果这两个实现都能够转换成C程序，那么编程语言是如何影响算法的性能？
* 如果这个程序能够在另外一台不同的计算机上执行，那么计算机硬件是如何影响算法性能？
这些实现将会执行10 000次，数的位数从256位到32 768位。数的每一位都是随机产生的。其后，在每次执行中，这两个数都会循环移位，产生两个不同的数进行相加。我们使用了两台计算机：桌面PC和一台高端计算机。并且使用两种不同的编程语言（C和Java）。我们一开始就假设随着数据规模的加倍，算法执行时间也会加倍。我们希望重新确认算法总体行为和计算机、编程语言以及实现无关。
图2-5表示了数据的规模（用x轴表示）与执行10 000次（用y轴表示）的时间（单位是毫秒）的关系。每一次变化都更改了这些配置选项：
g
C程序将会把调试信息编译进去。
none
C程序不会进行任何优化。
O1，O2，O3
C程序将会按照不同的优化等级进行编译。一般来说，数字越高的意味着更好的优化与更佳的性能。
Java
算法的Java版。
PC-Java
在PC上执行，只有一种配置，之前的那些数据也同样会在高端计算机上执行。
图2-5：在不同的情境下比较add和last的表现。
留意在图2-5的左边（标“Desktop PC”），每条计算线的斜率都是近似线性的，这种性质表示x和y的值之间存在线性关系。在高端计算机执行优化过的代码，计算结果却不能够简单地归为线性，因为需要考虑到高端处理器的重要影响。
表2-3包含了一些图上的数据。本书中提供的代码都会提供这种信息。表2-3的第6列、第7列和最后一列直接对比了HighEnd-C-Last-O3实现*在不同数据规模下的性能。性能的比率与预想的很接近，在2左右。假设t(n) 是在数据规模为n的情况下，加法算法的实际运行时间。这个增长模型提供了强有力的证据，证明在高端计算机上，使用C语言并且执行O3级优化，计算n位数之和的时间将会在n/11到n/29之间。
P28
表2-3：对比add、last实现求随机n位数之和的时间（单位为毫秒）
P29
计算机科学家认为加法算法是关于输入规模呈线性的。也就是说，对于所有n>n0，存在一个常数c，c>0，使得t(n)≤c*n。事实上我们并不需要知道c或者n0的值。一个争论的焦点是，在做加法时，每一个位都必须检查（考虑一下漏掉的后果），这样的复杂程度是否需要一个线性时间下界。
在加法算法的last实现，我们设置c为1/11，选择n0为256。其他的加法实现应该会有不同的常数，但是它们的总体表现仍呈线性。这个结果让那些认为整数算术是常数操作的程序员大吃一惊。当整数的固定位数用n来表示时（例如16位或者64位），常数时间的加法是可达的。
在考虑算法间差异时候，知道算法的阶数比了解常数c更为重要。看似无关紧要的差异会导致不同的性能。加法算法的last实现在不采用取模计算之后显得更加高效。在操作不是2的幂的数时，取模计算是出了名得慢。在数不能被10整除的情况下，二进制计算机做“%10”计算会有较大的开销且并不高效。当然，这并不是说我们可以忽略掉常数c的值。如果我们做大量加法的话，那么c的一点点小的变动都会对程序的性能产生很大的影响。
讨论4：nlogn算法的性能
性能族已经很好地描述了同类高效算法的共同行为。为了更好地阐述实践中的行为，我们定义一个函数t(n)，表示算法需要解决一个样本规模为n的问题的时间。解决问题的一个高效方法就是分治法，一个规模为n的问题将会被分成（大致相等）两个规模为n/2的子问题，这样来递归地解决问题，最后通过某些方法，将子问题的结果归并起来，作为最初问题的解。用数学语言来说，就是：
t(n)=2*t(n/2)+O(n)
也就是说，t(n) 包括了解决两个子问题的开销以及归并结果的开销，归并结果的开销不会高于线性时间。在等式的右边，t(n/2) 是解决规模为n/2的问题的时间，按此逻辑推理，t(n/2) 能表示为：
t(n/2)=2*t(n/4)+O(n/2)
所以最初的等式可以写为：
t(n)=2*[2*t(n/4)+O(n/2)]+O(n)
我们再扩展一层，得到：
t(n)=2*[2*[2*t(n/8)+O(n/4)]+O(n/2)]+O(n)
最后一个等式归约到 t(n)=8*t(n/8)+O(3*n)。将其推广到一般情况，我们可以说t(n)=2k*t(n/2k)+O(k*n)。这个扩展在n=2k，也就是k=log(n)时停止。扩展到最后，问题规模仅仅只是1了，t(1) 是一个常数。因此我们能够得到闭合解为t(n)=n*c+O(n*log(n))。因为对于任何常数c来说，n*log(n) 都比c*n要高阶，所以t(n) 能够简写为O(nlogn)。
讨论5a：二次方的算法性能
现在考虑一个类似的问题：两个n位的数相乘。例2-4是这个乘法的一个实现，采用小学使用的很简单的算法。
例2-4：Java的乘法实现mult
public static void mult(int[] n1, int[] n2, int[] result) {
　　int pos = result.length-1;
　　// 清除所有的值
　　for (int i = 0; i < result.length; i++) { result[i] = 0; }
　　for (int m = n1.length-1; m>=0; m--) {
　　　　int off = n1.length-1 - m;
　　　　for (int n = n2.length-1; n>=0; n--, off++) {
　　　　　　int prod = n1[m]*n2[n];
　　　　　　// 计算部分和，并且加上进位
　　　　　　result[pos-off] += prod % 10;
　　　　　　result[pos-off-1] += result[pos-off]/10 + prod/10;
　　　　　　result[pos-off] %= 10;
　　　　}
　　}
}
同样地，我们也会给出一个变形算法：alt，这个算法消除了取模运算的高开销，并且避开了当n1[m]等于0时不必要的内层计算（注意，alt算法没有在这里描述，但是能够在提供的代码库中找到）。alt算法包含了203行Java代码来避免使用两个取模操作。那么这个变形算法在有额外的开销时，能够节省总体

就像《黑客帝国》里面的Trinity 所说的：
　　“Neo ，是这个问题驱使着我们，是这个问题带你来到这儿。”
　　你知道这个问题，我也是。
　　作为本书的作者，我们将回答引领你到此的问题：
　　我能够使用某个算法解决我的问题吗？如果可以，那么怎么实现呢？
　　你也许并不需要理解一个算法为什么是正确的。如果你需要，那么请看看其他的资料，例如1180 页的算法圣经──《算法导论》，作者是Thomas H. Cormen 等（2001 ）。在那本书中你会了解到推论、定理以及证明；你也会从一些练习题和逐步递进的样例中看到算法是如何执行的。也许你会惊奇地发现，在算法导论中你找不到任何的实际代码，仅仅是一些伪代码的片段，伪代码是无数的算法教科书用来阐述算法的高级描述手段。在课堂上，这些教科书是非常重要的，但是在实际软件开发中，它们却起不到应有的作用，因为这些书假定伪代码都能够直接变成实际代码。
　　我们希望经验丰富的程序员在寻找问题的解决方案时，能够频繁参考本书。作为一名程序员，你每天要解决的问题都能在这里找到解决方案。在软件中，算法是决定成败的关键因素，在这里你能够了解到哪些决定能够改善关键算法的性能，也能够找到适合你的需求和解决方案的实际代码。
　　所有的算法都有实现，并且都使用测试工具经过仔细测试，以确保其正确性。而且，它们有足够的代码文档，能在这本书的代码库附录中找到它们。我们严格地遵照一系列的原则来设计算法、实现算法，以及编写这本书。如果这些原则对你很有意义，那么这本书也会同样有用。
原则：使用实际代码，而不是伪代码
　　为了计算最大网络流，一个实践者应该做些什么才能将图P-1 的Ford-Fulkerson 算法描述转换成实际代码呢？

图P-1 ：教科书中常见的伪代码
　　图中的算法描述来自于维基百科（http://en.wikipedia.org/wiki/Ford_Fulkerson ），这个描述与《算法导论》上的伪代码极其相似。最好还是不要期望一个软件的开发者能够根据这个Ford-Fulkerson 算法的描述开发出实际的代码。翻到第8章，对比一下我们的代码。我们只使用有注释的，并且是精心设计过的代码。在你自己写的代码或者软件系统中使用我们提供的现成代码，或者这些代码的逻辑吧。
　　一些算法教科书确实有完整的C或者Java 代码。但是这些教科书的目的通常是教初学者编程语言，或者是解释如何实现抽象数据类型。而且代码都只是在页面的狭窄边栏，作者通常都会忽略注释和错误处理，或者使用在实际应用中不会用到的快捷方法。我们相信程序员能够从有注释的，并且是精心设计过的代码中学到更多的东西，这就是我们为什么做如此多的工作来开发算法的实际解决方案。
原则：将算法和将要解决的问题分开
　　如果不和具体的问题联系起来，我们很难“泛化地”实现一个算法。我们反对那些给出了算法完全实现的书，这些书上的实现将泛化问题和特定问题纠结在一起，从而很难看出算法的原始结构。更糟糕的是，很多可用的实现依赖于一些特定的数据存储方式，虽然这种方式能够容易被机器理解，但是很难被人理解。
　　我们将会为泛化的问题和特殊的问题各设计算法的实现。例如，在第7章，当我们描述A* 搜索算法的时候，我们用了一个例子，叫做八数码问题（在一个3×3格子的棋盘中移动编号为1～8的小方块）。A* 算法的实现依赖于一系列良好定义的接口。因为有良好定义的接口，实现这些接口的类能够清晰地封装八数码这类特定问题的细节。
　　在本书中，我们使用了大量的编程语言，并且遵循一种严格的设计规范，使得代码可读性高并且生成高效的解决方案。由于我们具备软件工程背景，所以根据泛化的算法和特定领域的解决方案设计一个清晰的接口是一件很容易的事情。按照这样的流程编码，产生的软件是易于测试、维护并且能够根据面临的问题即时扩展。　　另外一个好处是读者能够更加容易地阅读和理解算法的描述和结果。当选择了一个算法，我们将会告诉读者，如何将我们编写的可读并且高效的代码转换成高度优化（虽然稍稍降低了可读性）并且性能优秀的代码。毕竟，优化是在问题已经解决之后才进行的，而且客户需要的是运行更快的代码。即便如此，我也认为我们需要听从C. A. R. Hoare 的建议：“过早的优化是一切问题之源”。
原则：仅仅讲述足够的数学
　　很多算法注重专门关注于证明算法的正确性，并且抽象地解释其细节。我们关注的却是如何将算法应用到实践中去。最后我们才会介绍一些数学知识，这些数学知识都是为了读者能够更好地理解数据结构和解的控制流程。
　　例如，一个人需要理解在很多算法中使用的集合和二叉树的性质。但是，没有必要证明二叉树的高度如何得到，并且解释红黑二叉树是如何平衡的。如果你需要了解这些细节，请阅读《算法导论》的第13 章。我们仅仅是需要才会解释结果，如果读者需要理解如何证明结论，我们将会告诉读者在哪儿能够找到数学证明。
　　在这本书你将会学习到使用一些关键术语和分析技术，并且基于数据结构的功能来区分算法行为。
原则：用经验来支持数学分析
　　在这本书中，我们从数学角度来分析算法的性能，以帮助程序员了解在哪种情况下算法能够得到最好的性能。我们将会提供现成的代码样例，在相关代码库中，有大量的JUnit （http://sourceforge.net/projects/junit ）测试样例为每个算法的实现提供了文档。我们也会生成基准性能数据，供分析算法性能时参考。
　　我们将每个算法归到一个特定的性能族中，并且提供基准测试数据来得到算法的性能，支持我们的分析结论。有一些算法是那些具有数学背景的算法设计人员证明能够非常高效但是却不可能实现的，我们需要避免使用这样的算法。我们将在各种平台上执行我们的算法，以证明算法的高效并不依赖于特定平台，而是由于其优秀的设计。
　　附录包含了我们采用的基准测试方法的全部细节，并且这个基准测试能够独立地验证书中描述的所有性能结论。我们能够给你的建议在开源社区非常常见：“你得到的利益也许会不一样”。虽然你不可能准确地复制我们的结论，但是你能看出我们描述的趋势。我们鼓励你在决定使用哪个算法的时候使用我们的这种基于经验的方法。
目标读者
　　如果你被困在一个沙漠孤岛上，并且只能选择一本算法书，我们推荐Donald Knuth 的《计算机程序设计艺术（卷1～3）》（1998 ）。Knuth 在这本书中描述了大量的数据结构和算法，并且进行了精巧的处理和分析。这本书包含了大量的脚注和练习，并且能够帮助一名程序员在接下来的时间中保持活力和竞争力。这些练习非常有挑战性，并且你能够直接接触到Knuth 的思想。
　　但是你没有被困在孤岛上，对吗？你接手了一些劣质的代码，而且这些代码必须在周五前进行改进，你需要知道如何去处理才行！
　　在你面对一个算法问题，需要解决一个特定的问题或者对现有解决方案进行改进的时候，我们希望本书能够成为你的第一选择。为解决各种问题，我们广泛地讨论了现存的算法，并且遵循以下原则：
　　. 我们使用模式化的统一格式来描述每一个算法，进行每一次讨论并解释算法的重点。正因如此，我们的书才如此易读。我们才能够看出相似的设计会对不同的算法产生什么样的影响。
　　.在这本书中，我们使用了不同的编程语言（包括C、C++ 、Java 还有Ruby ）来描述算法。得益于此，我们能够使用你熟悉的编程语言对算法进行详细的讨论。
　　. 我们描述了算法的期望性能，并且根据经验提供了支持这些结论的证据。无论你相信数学还是相信实际的运行时间，你都会被我们说服。
　　对软件工程师、程序员以及设计师来说，我们希望这本书能够派上用场。为了达到目标，你需要参考大量的关于实际解决方案和算法的资料，才能够解决手头的实际问题。你已经知道了如何用多种语言编写一个程序。你也知道了计算机科学的关键数据结构，例如数组、链表、栈、队列、散列表、二叉树还有有向图或者无向图。你不需要实现这些数据结构，因为它们大都在库函数中可以找到。
　　我们希望你能从这本书中学到如何选择并且测试解决方案以快速高效地解决问题，也能够学到一些高级数据结构和一些使用标准数据结构的新方法，来改善程序的性能。在选择算法时，如果你可以知道什么样的决定可以改善解决方案的效率，那么就能够提高你解决问题的能力。
本书组织方式
　　本书分为三个部分。第一部分（第1章～第3章）介绍了算法的必要数学基础，以便于读者理解本书的描述。在每个算法的论述中，我们使用了一种模式化的格式。我们仔细地设计这个格式，确保前后一致。第二部分（第4章～第9章）介绍了一系列的算法。这些章节的每个独立部分都是一个完备的算法描述。
　　第三部分（第10 章和第11 章）为那些感兴趣的读者提供一些较为高深的资源。当没有一个高效的解决方案来解决问题，而且“最后的线索”为解决问题提供了有意义的线索的时候，这个部分就能够告诉我们如何利用这些线索来解决问题。最后我们以一个重要领域的讨论结束本书。这个讨论在第2章之所以被忽略，是因为它的内容太过高深，太过前沿，甚至还没有被证明。第四部分包括了一个附录，这个附录描述了本书每章中对算法进行评测的方法以及数学分析。在业界，这是一种标准的基准测试方法，但是几乎没有算法教科书介绍这个方法。
本书体例
　　在印刷上的一些例行惯例：
　　代码（Code）
　　这些代码都是直接取自代码库，是现实中使用的代码。
　　斜体（Italic）表示这个术语用于描述算法和数据结构。同样在伪代码描述中表示变量。
　　等宽字体（Constant Width）
　　表示实现中的软件元素，例如Java 类、C语言的数组名称以及常量（true 或者false ）。
　　小型大写字母（SMALL CAPS）表示算法名称。
　　在本书中，我们引用了大量的书籍、文章和网站。这些引用都用括号标示出来，例如（Cormen 等，2001 ），每一章最后部分列出本章所使用的参考文献。正文中的引用列出作者的名字和文献的年份。
　　本书中的所有URL 都在2008 年8月时验证有效，而且我们抛弃了那些看起来不久就会失效的URL 。短URL ，例如http://www.oreilly.com ，直接在文本中使用；否则，这些URL 会放入参考文献中。
代码使用说明
　　本书的目的是帮助你更好地完成工作，一般来说，你可以在程序和文档中直接使用本书代码。除非你需要重构这些代码的重要部分，否则你不需要联系我们获得许可。例如，你可以编写一个使用了本书中一些代码的程序而不需要许可。销售或者分发来自O’Reilly 出版书籍中的样例不需要许可。引用本书来回答问题或者引用样例代码也不需要许可。在你的产品文章中过度地使用本书中的代码也不需要许可。我们希望，但是不要求标明归属。一个归属说明通常包括标题、作者、出版商和ISBN 。例如：“George T. Heineman，Gary Pollice 和Stanley Selkow 编写的《Algorithms in a Nutshell 》。版权属于George T. Heineman，Gary Pollice 和Stanley Selkow，978-0-596-51624-6 ”。
　　如果你觉得你需要使用代码的情况超出了我们的允许范围，那么请联系：permissions@ oreilly.com 。
联系我们
　　对于本书，如果有任何意见或疑问，请按照以下地址联系本书出版商：美国：
O’Reilly Media, Inc.
1005 Gravenstein Highway North
Sebastopol, CA 95472
中国：北京市西城区西直门南大街2号成铭大厦C座807 室（100035）
奥莱利技术咨询（北京）有限公司
　　本书也有相关的网页，我们在上面列出了勘误表、范例以及其他一些信息。你可以访问：
http://www.oreilly.com/catalog/9780596516246 （英文版）
http://www.oreilly.com.cn/book.php bn=978-7-111-28674-5 （中文版）
　　对本书做出评论或者询问技术问题，请发送E-mail 至：
bookquestions@oreilly.com
　　希望获得关于本书、会议、资源中心和O’Reilly 网络的更多信息，请访问：
http://www.oreilly.com
http://www.oreilly.com.cn
致谢
　　我们感谢书籍的审阅者，感谢他们对于本书细节的关注以及所给出的建议，这些建议提高了本书的质量。他们是：Alan Davidson 、Scot Drysdale 、Krzysztof Duleba 、Gene Hughes 、Murali Mani 、Jeffrey Yasskin 和Daniel Yoo 。
　　George Heineman 感谢那些带领他走入算法世界的人，包括Scot Drysdale 教授（达特茅斯学院），Zvi Galil （哥伦比亚大学）。同样，George 也感谢他的妻子Jennifer ，他的孩子Nicholas （他一直想要知道爸爸在写什么便条）和Alexander （出生于我们书籍定稿时）。
　　Gary Pollice 感谢他的妻子陪伴他走过了40 年的美好时光。他同样感谢WPI 计算机科学系提供给他的伟大工作和幽雅的环境。
　　Stanley Selkow 感谢他的妻子Deb 。这本书是在他们相伴走过的时光中的又一个结晶。
参考文献
　　Cormen, Thomas H., Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, Second Edition. McGraw-Hill, 2001.
　　Knuth, Donald E., The Art of Computer Programming, Volumes 1－3, Boxed Set Second Edition. Addison-Wesley Professional, 1998.

（美）George T. Heineman; Gary Pollice; Stanley Selkow 著：暂无简介

杨晨 等译：暂无简介

算法，神秘而晦涩的词汇。算法，是计算机科学中最重要同时也是最基础的一环。从开始学习计算机，我们就深知，算法是整个计算机科学的核心。然而直至我们工作数年后，能够真正学好算法的人，却依旧是凤毛麟角。这并不是计算机教育的错，也不是计算机从业人员的错，更不是算法的错。长久以来，算法就像古老的咒语，算法背后高深的数学知识更让人望而生畏。其实，我们始终没有找到一条从理论走向实践的路。
　　在这里，我们很高兴能向大家介绍本书。它正是能够带领你学好算法的一本不可多得的好书。
　　本书的三位作者是伍斯特理工学院的教授，其中George T. Heineman毕业于达特茅斯学院和哥伦比亚大学，曾经获得过GE、IBM和AT&T的研究奖金，在软件工程方面有独到的研究。而Gary Pollice曾经供职于Rational Software、Sun等多家巨头，有着丰富的工业界经验，知道如何将学术和工业结合起来。Stanley M. Selkow毕业于卡内基梅隆大学和宾夕法尼亚大学，擅长图论和算法设计。本书由这三位伍斯特理工学院计算机理论专家合著，向我们展示了工业界和学术界对算法的不同看法以及如何高效地将理论和实践相结合。本书搭建了一条真正属于开发者的路。
　　本书的读者主要面向本科生以及程序设计人员，同样也适用于产品和项目管理人员。由于译者的知识和经验有限，翻译中难免有疏漏或错误，敬请广大读者谅解并批评指正。
杨晨 李明
2009年7月

前言 ............................................................................ 1
第一部分
第1章 算法真的很重要 ................................................11
理解问题 ..........12
如果需要，尽可能用实践检验 ..........................13
解决问题的算法 ...............5
花絮 .............16
故事的寓意 .......17
参考文献 ..........19
第2章 算法的数学原理 ............................................... 20
问题样本的规模 .................20
函数的增长率 ...............22
最好最坏和平均情况下的性能分析 ...........................................26
性能指标 ..........30
混合操作 ..........43
基准测试 ..........43
最后一点 ..........45
参考文献 ..........46
第3章 模式和领域 ...................................................... 47
模式：一种交流语言 .......................47
算法模式的格式 .................49
伪代码模式的格式 ..........49
设计格式 ..................50
基于经验的评价格式 .......................52
领域和算法 ...............52
浮点计算 ..................54
手动内存分配 ...............58
选择一门编程语言 ...................60
参考文献 ..................61
第二部分
第4章 排序算法 ............................................. 65
概述 ..........................65
插入排序 ..................71
中值排序 ..................75
快速排序 ..................85
选择排序 ....................92
堆排序 ......................93
计数排序 ..................98
选择排序算法的标准 ....................................105
参考文献 ................110
第5章 查找 ............................................112
概述 ........................112
顺序查找 ................113
二分查找 ................118
基于散列的查找 ..................122
二叉查找树 .............135
参考文献 ................141
第6章 图算法 .................................... 143
概述 ...............143
深度优先搜索 ...........149
广度优先搜索 ..............155
单源最短路径 ........159
所有点对最短路径 ...................170
最小生成树算法 ...............173
参考文献 ................176
第7章 人工智能中的寻路 ..................................... 177
概述 ........................177
深度优先搜索 ..........185
广度优先搜索 ...............194
A*搜索 ...................198
比较 ........................208
Minimax .................211
NegMax ..................216
AlphaBeta ...............219
参考文献 ................226
第8章 网络流算法 .................................... 229
概述 ........................229
最大流 ....................232
二部图匹配 .............240
在增广路上的深入思考 ..........................................244
最小开销流 .............246
转运问题 ................248
运输问题 ................248
任务分配问题 ...............250
线性编程 ................250
参考文献 ................251
第9章 计算几何 ................................... 252
概述 .......................252
凸包扫描 ................261
线段扫描 ................269
最近点查询 .............280
范围查询 ................289
参考文献 ................296
第三部分
第10章 最后的招数 ................................... 299
另类算法 ................299
近似算法 ................300
离线算法 ................300
并行算法 ................300
随机算法 ................301
结果可能出错却可以衰减错误率的算法 ..............................308
参考文献 ................311
第11章 尾声 ............................................................ 312
概述 ........................312
原则：了解数据 .............312
原则：将问题分解至更小的问题 ..................................313
原则：选择正确的数据结构 .....................................314
原则：空间换时间 .......315
原则：如果没有显而易见的解法，使用搜索 ..........................315
原则：如果没有显而易见的解法，将问题归约为另一个有解的问题 ............316
原则：编写算法难，测试算法更难 .................................317
第四部分
附录 基准测试 .............................. 321