算法导论

"出版者的话

专家指导委员会

译者序

前言

第一部分基础知识

引言

第1章算法在计算中的作用

1.1算法

1.2作为一种技术的算法

第2章算法入门

2.1插入排序

2.2算法分析

2.3算法设计

2.3.1分治法

2.3.2分治法分析

第3章函数的增长

3.1渐近记号

3.2标准记号和常用函数

第4章递归式

4.1代换法

4.2递归树方法

4.3主方法

*4.4主定理的证明

4.4.1取正合幂时的证明

4.4.2上取整函数和下取整函数

第5章概率分析和随机算法

5.1雇用问题

5.2指示器随机变量

5.3随机算法

*5.4概率分析和指示器随机变量的进一步使用

5.4.1生日悖论

5.4.2球与盒子

5.4.3序列

5.4.4在线雇用问题

第二部分排序和顺序统计学

引言

第6章堆排序

6.1堆

6.2保持堆的性质

6.3建堆

6.4堆排序算法

6.5优先级队列

第7章快速排序

7.1快速排序的描述

7.2快速排序的性能

7.3快速排序的随机化版本

7.4快速排序分析

7.4.1最坏情况分析

7.4.2期望的运行时间

第8章线性时间排序8.1排序算法时间的下界

8.2计数排序

8.3基数排序

8.4桶排序

第9章中位数和顺序统计学

9.1最小值和最大值

9.2以期望线性时间做选择

9.3最坏情况线性时间的选择

第三部分数据结构

引言

第10章基本数据结构

10.1栈和队列

lO.2链表

10.3指针和对象的实现

10.4有根树的表示

第11章散列表

……

第四部分高级设计和分析技术

第五部分高级数据结构

第六部分图算法

第七部分算法研究问题选编

第八部分附录：数学基础知识

参考文献

索引

"

"　　本书深入讨论各类算法，并着力使这些算法的设计和分析能为各个层次的读者接受。各章自成体系，可以作为独立的学习单元。算法以英语和伪代码的形式描述，具备初步程序设计经验的人就能看懂。说明和解释力求浅显易懂，不失深度和数学严谨性。本书自第1版出版以来，已经成为世界范围内广泛使用的大学教材和专业人员的标准参考书。第2版增加了论述算法作用、概率分析与随机算法、线性规划等几章。　　在有关算法的书中，有一些叙述非常严谨，但不够全面，另一些涉及了大量的题材，但又缺乏严谨性。《算法导论》将严谨性和全面性融为一体。本书深入讨论各类算法，并着力使这些算法的设计和分析能为各个层次的读者接受。各章自成体系，可以作为独立的学习单元。算法以英语和伪代码的形式描述，具备初步程序设计经验的人就能看懂。说明和解释力求浅显易懂，不失深度和数学严谨性。本书自第1版出版以来，已经成为世界范围内广泛使用的大学教材和专业人员的标准参考书。第2版增加了论述算法作用、概率分析与随机算法、线性规划等几章。同时，对第1版的几乎每一节都作了大量的修订。一项巧妙而又重要的修改是提前引入循环不变式，并在全书中用来证明算法的正确性。在不改变数学和分析重点的前提下，作者将许多数学基础知识从第一部分移到了附录中，并在开始部分加入了一些富有诱导性的题材。"