算法导论(核心篇 )(原书第4版)电子书

译者序

前言

第一部分 基础知识

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

1.1 算法

1.2 算法即技术

思考题

本章注记

第2章 算法基础

2.1 插入排序

2.2 分析算法

2.3 设计算法

思考题

本章注记

第3章 刻画运行时间

3.1 O符号、Ω符号和Θ符号

3.2 渐近符号：形式化定义

3.3 标准符号与常见函数

思考题

本章注记

第4章 分治策略

4.1 方阵乘法

4.2 矩阵乘法的Strassen算法

4.3 用代入法求解递推式

4.4 用递归树方法求解递推式

4.5 用主方法求解递推式

*4.6 证明连续主定理

*4.7 Akra-Bazzi递推式

思考题

本章注记

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

5.1 雇用问题

5.2 指示器随机变量

5.3 随机算法

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

思考题

本章注记

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

第6章 堆排序

6.1 堆

6.2 维护堆性质

6.3 建堆

6.4 堆排序

6.5 优先队列

思考题

本章注记

第7章 快速排序

7.1 快速排序的描述

7.2 快速排序的性能

7.3 快速排序的随机化版本

7.4 快速排序的分析

思考题

本章注记

第8章 线性时间排序

8.1 排序算法的下界

8.2 计数排序

8.3 基数排序

8.4 桶排序

思考题

本章注记

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

9.1 最小值和最大值

9.2 线性期望时间选择算法

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

思考题

本章注记

第三部分 数据结构

第10章 基本数据结构

10.1 基于数组的简单数据结构：数组、矩阵、栈、队列

10.2 链表

10.3 有根树的表示

思考题

本章注记

第11章 散列表

11.1 直接寻址表

11.2 散列表

11.3 散列函数

11.4 开放寻址法

11.5 实际考虑

思考题

本章注记

第12章 二叉搜索树

12.1 二叉搜索树是什么

12.2 查询二叉搜索树

12.3 插入和删除

思考题

本章注记

第13章 红黑树

13.1 红黑树的性质

13.2 旋转

13.3 插入

13.4 删除

思考题

本章注记

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

第14章 动态规划

14.1 钢条切割

14.2 矩阵链乘法

14.3 动态规划原理

14.4 最长公共子序列

14.5 最优二叉搜索树

思考题

本章注记

第15章 贪心算法

15.1 活动选择问题

15.2 贪心算法原理

15.3 霍夫曼编码

15.4 离线缓存

思考题

本章注记

第16章 摊还算法

16.1 聚合分析

16.2 核算法

16.3 势能法

16.4 动态表

思考题

本章注记

第五部分 高级数据结构

第17章 增强数据结构

17.1 动态顺序统计量

17.2 如何增强数据结构

17.3 区间树

思考题

本章注记

第18章 B树

18.1 B树的定义

18.2 B树上的基本操作

18.3 从B树中删除关键字

思考题

本章注记

第19章 不相交集合数据结构

19.1 不相交集合操作

19.2 不相交集合的链表表示

19.3 不相交集合森林

*19.4 带路径压缩的按秩合并分析

思考题

本章注记

第六部分 图算法

第20章 基本的图算法

20.1 图的表示

20.2 广度优先搜索

20.3 深度优先搜索

20.4 拓扑排序

20.5 强连通分量

思考题

本章注记

第21章 最小生成树

21.1 最小生成树的形成

21.2 Kruskal算法和Prim算法

思考题

本章注记

第22章 单源最短路径

22.1 Bellman-Ford算法

22.2 有向无环图中的单源最短路径问题

22.3 Dijkstra算法

22.4 差分约束与最短路径

22.5 最短路径性质的证明

思考题

本章注记

第23章 所有顶点对最短路径问题

23.1 最短路径与矩阵乘法

23.2 Floyd-Warshall算法

23.3 Johnson算法对于稀疏图的应用

思考题

本章注记

第24章 最大流问题

24.1 流网络

24.2 Ford-Fulkerson方法

24.3 最大二分匹配

思考题

本章注记

第25章 二部图的匹配

25.1 最大二部图匹配（重访）

25.2 稳定婚姻问题

25.3 分配问题的匈牙利算法

思考题

本章注记

附录 数学基础知识

附录A 求和

附录B 集合等离散数学内容

附录C 计数与概率

附录D 矩阵

参考文献

推荐阅读