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