Python算法设计与分析

第1章 算法初步 1

1.1　什么是算法　1

1.1.1　算法的定义　1

1.1.2　算法与程序的区别　1

1.2　时间复杂度　2

1.2.1　运行时间和程序复杂程度的

关系　2

1.2.2　时间复杂度是渐进的　2

1.2.3　简单程序的时间复杂度分析　3

1.2.4　时间复杂度的意义　6

1.3　空间复杂度　8

1.4　算法的应用　8

1.5　Python算法的优势　9

1.6　小结　9

1.7　习题　10

第2章　排序算法　12

2.1　初级排序算法　12

2.1.1　插入排序　12

2.1.2　选择排序　14

2.1.3　冒泡排序　17

2.2　高级排序算法　19

2.2.1　归并排序　19

2.2.2　快速排序　21

2.2.3　希尔排序　24

2.2.4　堆排序　26

2.2.5　桶排序　30

2.3　小结　32

2.4　习题　32

第3章　查找　34

3.1　顺序查找　34

3.2　二分查找　35

3.3　树　41

3.4　二叉树　43

3.4.1　二叉树的性质　43

3.4.2　满二叉树　44

3.4.3　完全二叉树　44

3.4.4　创建二叉树　45

3.4.5　遍历二叉树　46

3.5　二叉搜索树　47

3.5.1　二叉搜索树基础　47

3.5.2　二叉搜索树的操作　47

3.6　平衡二叉树　56

3.6.1　二叉搜索树的效率　56

3.6.2　AVL树　56

3.7　小结　62

3.8　习题　62

第4章　双指针问题　65

4.1　单链表　65

4.1.1　建立单链表　65

4.1.2　遍历单链表　66

4.1.3　插入单链表　66

4.1.4　删除单链表第n个数　68

4.2　双指针的应用　69

4.2.1　数组合并问题　69

4.2.2　删除单链表倒数第n个数　71

4.3　小结　72

4.4　习题　72

第5章　哈希算法　73

5.1　哈希算法的原理　73

5.2　哈希函数　74

5.2.1　除法哈希算法　74

5.2.2　乘法哈希算法　75

5.2.3　平方取中法　75

5.2.4　随机数哈希算法　75

5.3　解决冲突　76

5.3.1　开放定址法　76

5.3.2　拉链址法　77

5.4　哈希算法的应用　78

5.4.1　两个数的和问题　78

5.4.2　团体赛问题　79

5.4.3　猜数字游戏　81

5.5　小结　83

5.6　习题　83

第6章　深度优先搜索算法　85

6.1　搜索　85

6.2　图上的深度优先搜索　85

6.2.1　无向图　85

6.2.2　图的术语　86

6.2.3　图上的搜索　88

6.2.4　经典例题讲解（*大的油田）　89

6.3　二叉树上的深度优先搜索　91

6.3.1　二叉树相关术语　91

6.3.2　二叉树上的搜索　92

6.3.3　经典例题讲解（员工派对）　92

6.3.4　经典例题讲解（城市危机）　97

6.4　小结　105

6.5　习题　106

第7章　广度优先搜索算法　107

7.1　依旧是图的搜索　107

7.2　队列中的存储方式　108

7.3　经典例题讲解　111

7.3.1　艰难旅行　111

7.3.2　混乱地铁　114

7.3.3　温室大棚　116

7.4　小结　120

7.5　习题　120

第8章　回溯算法　121

8.1　回溯算法原理　121

8.2　回溯算法的应用　124

8.2.1　N皇后　124

8.2.2　数独　128

8.2.3　排列组合　132

8.2.4　两个扩展问题　137

8.3　小结　139

8.4　习题　139

第9章　动态规划　141

9.1　动态规划介绍　141

9.2　矿工问题　141

9.2.1　问题描述　141

9.2.2　问题分析　142

9.2.3　参考实现　145

9.3　爬楼梯问题　146

9.3.1　问题描述　146

9.3.2　问题分析　147

9.3.3　参考实现　149

9.4　背包问题　149

9.4.1　问题描述　149

9.4.2　问题分析　150

9.4.3　问题实例　151

9.4.4　参考实现　153

9.5　*长递增子序列问题　154

9.5.1　问题描述　154

9.5.2　改进算法　155

9.5.3　参考实现　156

9.6　小结　157

9.7　习题　157

第10章　贪心算法　158

10.1　贪心算法介绍　158

10.2　硬币找零问题　159

10.2.1　问题描述　159

10.2.2　问题实例　159

10.2.3　参考实现　160

10.3　活动安排问题　160

10.3.1　问题描述　160

10.3.2　参考实现　161

10.4　哈夫曼编码　162

10.4.1　问题描述　163

10.4.2　哈夫曼树　163

10.4.3　贪心选择性质　165

10.4.4　*优子结构性质　166

10.4.5　参考实现　166

10.5　小结　167

10.6　习题　168

第11章　分治算法　169

11.1　分治算法原理　169

11.2　分治算法应用　170

11.2.1　二分查找　170

11.2.2　二维数组的查找　171

11.2.3　快速凸包算法　173

11.2.4　快速傅氏变换　178

11.3　小结　183

11.4　习题　183

第12章　并查集　184

12.1　并查集介绍　184

12.1.1　并查集的构造方法　184

12.1.2　并查集的应用　184

12.1.3　并查集3种基本操作的Python实现　186

12.2　朋友圈　187

12.2.1　问题描述　187

12.2.2　问题分析　187

12.2.3　代码　188

12.3　图的子元素　190

12.3.1　问题描述　190

12.3.2　问题分析　190

12.3.3　代码　192

12.4　小结　193

12.5　习题　193

第13章　*短路径算法　194

13.1　戴克斯特拉算法　194

13.1.1　算法介绍　194

13.1.2　算法证明　199

13.1.3　算法代码　200

13.2　贝尔曼-福特算法　202

13.2.1　算法介绍　203

13.2.2　算法证明　205

13.2.3　算法代码　206

13.3　弗洛伊德算法　208

13.3.1　算法介绍　208

13.3.2　算法代码　212

13.4　A*搜索算法　215

13.4.1　算法介绍　215

13.4.2　算法证明　219

13.4.3　算法代码　220

13.5　习题　222

第14章　数论算法　223

14.1　欧几里得算法　223

14.1.1　算法分析与证明　223

14.1.2　算法代码　224

14.1.3　算法应用　224

14.2　中国余数定理　228

14.2.1　算法介绍　228

14.2.2　算法证明　229

14.2.3　算法代码　229

14.3　素性检验算法　230

14.3.1　费马素性检验　230

14.3.2　米勒-拉宾素性检验　231

14.3.3　算法代码　233

14.4　小结　234

14.5　习题　234