内容简介：
《算法基础》自1997年出版以来深受读者喜爱，已经被翻译成多种语言出版，并成为世界许多高校广泛采用的算法教材之一。书中对算法设计、算法的复杂度分析和计算复杂度进行了恰如其分的介绍。作者用平实的语言和简单的符号介绍了各种抽象的数学概念，既浅显易懂，又不失严谨。为了便于读者理解和记忆，作者还提供了大量的示例，并在附录中介绍了基本的数学概念。
第5版新增了一章，介绍遗传算法和遗传编程，其中提供了理论和实践两方面的应用。此外，这一版还对练习和示例进行了全面更新，并且改进了教师资源。本书可作为本科生和研究生算法课程的教材，也可供程序员及算法分析和设计人员阅读。
作者简介：
Richard E. Neapolitan
美国东北伊利诺伊大学计算机科学教授，C Suite Consulting Group贝叶斯网络和统计学研究员。研究方向包括：概率与统计、人工智能、认知科学，以及贝叶斯网络和概率建模在医学、生物和金融领域的应用。他是国际知名的理论家和实践者，并受邀在世界各地发表讲演、举办研讨会。Neapolitan还是一位多产的作家，另著有《专家系统的概率推理》《学习贝叶斯网络》《当代人工智能》等专著。
目录：
第1章 算法：效率、分析和阶1
1.1 算法1
1.2 开发高效算法的重要性5
1.2.1 顺序查找与二分查找的对比 6
1.2.2 斐波那契序列7
1.3 算法分析10
1.3.1 复杂度分析10
1.3.2 理论应用14
1.3.3 正确性分析15
1.4 阶15
1.4.1 阶的直观介绍15
1.4.2 阶数的严谨介绍17
1.4.3 利用极限计算阶23
1.5 本书概要25
1.6 习题25
第2章 分而治之30
2.1 二分查找30
2.2 合并排序33
2.3 分而治之方法38
2.4 快速排序（分割交换排序）38
2.5 Strassen矩阵乘法算法42
2.6 大整数的算术运算46
2.6.1 大整数的表示：加法和其他线性时间运算46
2.6.2 大整数的乘法46
2.7 确定阈值50
2.8 不应使用分而治之方法的情况53
2.9 习题53
第3章 动态规划58
3.1 二项式系数58
3.2 Floyd最短路径算法61
3.3 动态规划与最优化问题66
3.4 矩阵链乘法67
3.5 最优二叉查找树73
3.6 旅行推销员问题79
3.7 序列对准84
3.8 习题88
第4章 贪婪方法92
4.1 最小生成树94
4.1.1 Prim算法96
4.1.2 Kruskal算法100
4.1.3 Prim算法与Kruskal算法的比较 103
4.1.4 最终讨论103
4.2 单源最短路径的Dijkstra算法104
4.3 调度计划106
4.3.1 使系统内总时间最短106
4.3.2 带有最终期限的调度安排 108
4.4 霍夫曼编码112
4.4.1 前缀码113
4.4.2 霍夫曼算法114
4.5 贪婪方法与动态规划的比较：背包问题 116
4.5.1 0-1背包问题的一种贪婪方法 116
4.5.2 部分背包问题的贪婪方法 118
4.5.3 0-1背包问题的动态规划方法 118
4.5.4 0-1背包问题动态规划算法的改进118
4.6 习题120
第5章 回溯124
5.1 回溯方法124
5.2 n皇后问题129
5.3 用蒙特卡洛算法估计回溯算法的效率 132
5.4 “子集之和”问题134
5.5 图的着色138
5.6 哈密顿回路问题141
5.7 0-1背包问题143
5.7.1 0-1背包问题的回溯算法 143
5.7.2 比较0-1背包问题的动态规划算法与回溯算法149
5.8 习题150
第6章 分支定界153
6.1 用0-1背包问题说明分支定界154
6.1.1 带有分支定界修剪的宽度优先查找154
6.1.2 带有分支定界修剪的最佳优先查找158
6.2 旅行推销员问题161
6.3 溯因推理（诊断）167
6.4 习题173
第7章 计算复杂度介绍：排序问题 175
7.1 计算复杂度175
7.2 插入排序和选择排序176
7.3 每次比较最多减少一个倒置的算法的下限179
7.4 再谈合并排序181
7.5 再谈快速排序185
7.6 堆排序186
7.6.1 堆和基本堆例程186
7.6.2 堆排序的一种实现189
7.7 合并排序、快速排序和堆排序的比较 193
7.8 仅通过键的比较进行排序的下限 194
7.8.1 排序算法的决策树194
7.8.2 最差情况下的下限196
7.8.3 平均情况下的下限197
7.9 分配排序（基数排序）200
7.10 习题203
第8章 再谈计算复杂度：查找问题 207
8.1 仅通过键的比较进行查找的下限 207
8.1.1 最差表现的下限209
8.1.2 平均情况下的下限210
8.2 插值查找213
8.3 树中的查找215
8.3.1 二叉查找树215
8.3.2 B树218
8.4 散列219
8.5 选择问题：对手论证222
8.5.1 找出最大键222
8.5.2 同时找出最大键和最小键 223
8.5.3 找出第二大的键227
8.5.4 查找第k小的键230
8.5.5 选择问题的一种概率算法 236
8.6 习题238
第9章 计算复杂度和难解性：NP 理论简介241
9.1 难解性241
9.2 再谈输入规模242
9.3 三类一般问题244
9.3.1 已经找到多项式时间算法的问题244
9.3.2 已经证明难解的问题245
9.3.3 未被证明是难解的，但也从来没有找到多项式时间算法的问题 245
9.4 NP理论245
9.4.1 集合P和NP247
9.4.2 NP完全问题250
9.4.3 NP困难、NP容易和NP等价问题 256
9.5 处理NP困难问题259
9.5.1 旅行推销员问题的近似算法 259
9.5.2 装箱问题的近似算法263
9.6 习题266
第10章 遗传算法和遗传编程268
10.1 遗传知识复习268
10.2 遗传算法270
10.2.1 算法270
10.2.2 说明范例270
10.2.3 旅行推销员问题272
10.3 遗传编程278
10.3.1 说明范例279
10.3.2 人造蚂蚁281
10.3.3 在金融贸易中的应用283
10.4 讨论及扩展阅读284
10.5 习题284
第11章 数论算法286
11.1 数论回顾286
11.1.1 合数与质数286
11.1.2 最大公约数286
11.1.3 质因数分解288
11.1.4 最小公倍数289
11.2 计算最大公约数290
11.2.1 欧氏算法290
11.2.2 欧氏算法的扩展292
11.3 模运算回顾294
11.3.1 群论294
11.3.2 关于n同余295
11.3.3 子群299
11.4 模线性方程的求解302
11.5 计算模的幂305
11.6 寻找大质数307
11.6.1 寻找大质数307
11.6.2 检查一个数字是否为质数 307
11.7 RSA公钥密码系统318
11.7.1 公钥加密系统318
11.7.2 RSA加密系统319
11.8 习题321
第12章 并行算法简介324
12.1 并行体系结构325
12.1.1 控制机制326
12.1.2 地址空间的组织326
12.1.3 互联网络328
12.2 PRAM模型330
12.2.1 为CREW PRAM模型设计算法 332
12.2.2 为CRCW PRAM模型设计算法 337
12.3 习题339
附录A 必备数学知识回顾340
附录B 求解递归方程：在递归算法分析中的应用363
附录C 不交集的数据结构388
参考文献395
文章试读：前面曾经提到，无论计算机变得多么快速，内存变得多么廉价，效率永远都是重要的考虑因素。接下来，我们通过对比同一问题的两种算法来说明其原因。 1.2.1 顺序查找与二分查找的对比 前面曾经提到，在电话簿中查找姓名的方法是一种经过修改的二分查找，它通常要远快于顺序查找。下面将对比这两种方法的算法，以说明二分查找法要快多少。 我们已经编写了完成顺序查找的算法，即算法1.1。在一个非递减顺...
(查看全部试读)