算法设计与应用电子书

前言

第1章 算法概念和基础

1.1 基本概念

1.1.1 搜索

1.1.2 排序

1.2 算法复杂度

1.2.1 时间复杂度

1.2.2 算法的时间复杂度

1.2.3 空间复杂度

1.3 数据结构

1.3.1 堆

1.3.2 不相交集

1.4 本章小结

1.5 习题

第2章 排序

2.1 比较排序

2.1.1 冒泡排序

2.1.2 堆排序

2.1.3 插入排序

2.1.4 归并排序

2.2 线性排序

2.2.1 桶排序

2.2.2 计数排序

2.2.3 基数排序

2.3 本章小结

2.4 习题

第3章 递归

3.1 基本概念

3.2 递归例子

3.2.1 生成排列

3.2.2 整数划分

3.3 复杂度的递归方法求解

3.3.1 展开法

3.3.2 代入法

3.3.3 递归树方法

3.3.4 主方法

3.3.5 几种递归形式的复杂度分析

3.4 本章小结

3.5 习题

第4章 分治

4.1 基本概念

4.2 快速排序

4.3 最大子数组问题

4.4 最近点对问题

4.5 棋盘覆盖问题

4.6 寻找第k小元素

4.7 分治在傅里叶变换中的应用∗

4.8 本章小结

4.9 习题

第5章 动态规划

5.1 基本概念和步骤

5.2 最大子数组问题

5.3 0-1背包问题

5.4 旅行商问题

5.5 最长公共子序列

5.6 斯坦纳最小树∗

5.7 状态压缩动态规划

5.7.1 集合状态压缩

5.7.2 空间状态压缩

5.8 动态规划和贝尔曼方程∗

5.9 本章小结

5.10 习题

第6章 贪心

6.1 基本概念

6.2 小数背包和0-1背包

6.2.1 小数背包贪心算法的正确性证明

6.2.2 0-1背包贪心算法

6.3 最小生成树

6.3.1 Kruskal算法

6.3.2 Prim算法

6.4 霍夫曼编码

6.5 贪心算法在稳定匹配中的应用∗

6.6 本章小结

6.7 习题

第7章 图算法

7.1 深度优先搜索

7.1.1 无向图的深度优先搜索

7.1.2 有向图的深度优先搜索

7.1.3 应用：寻找图的关节点

7.2 广度优先搜索

7.2.1 无向图的广度优先搜索

7.2.2 有向图的广度优先搜索

7.2.3 应用：最短路径（跳数）

7.3 单源最短路径

7.3.1 Dijkstra算法

7.3.2 Bellman-Ford算法

7.3.3 SPFA算法

7.3.4 差分约束系统

7.4 多源最短路径

7.4.1 Floyd算法（弗洛伊德算法）

7.4.2 Johnson算法

7.5 最短路径在网络路由中的应用∗

7.6 本章小结

7.7 习题

第8章 回溯和分支限界

8.1 回溯的基本方法

8.1.1 回溯法的基本步骤

8.1.2 回溯法的通用框架

8.2 骑士巡游问题

8.3 0-1背包问题

8.4 最大团问题

8.4.1 最大团的回溯算法

8.4.2 Bron-Kerbosch算法

8.5 分支限界法

8.5.1 基本方法

8.5.2 旅行商问题

8.5.3 任务指派问题

8.6 分支限界在流水线作业调度中的应用∗

8.7 本章小结

8.8 习题

第9章 匹配与指派

9.1 基本概念

9.2 基于图的匈牙利算法

9.2.1 匹配问题

9.2.2 指派问题

9.3 基于矩阵的匈牙利算法

9.3.1 算法流程

9.3.2 最大化指派

9.4 匹配算法在多目标跟踪中的应用∗

9.5 本章小结

9.6 习题

参考文献