算法笔记（第2版）

第1章 排序 1
1.1 比较排序 ................................................................................................................ 1
1.1.1 梳排序.......................................................................................................... 2
1.1.2 堆排序.......................................................................................................... 4
1.1.3 归并排序 ...................................................................................................... 5
1.1.4 快速排序 ...................................................................................................... 8
1.1.5 内省排序 ...................................................................................................... 10
1.1.6 Timsort ......................................................................................................... 11
1.2 非比较排序............................................................................................................. 14
1.2.1 桶排序.......................................................................................................... 14
1.2.2 基数排序 ...................................................................................................... 15
1.3 总结........................................................................................................................ 16
第2章 哈希 17
2.1 基本概念与实现..................................................................................................... 17
2.1.1 哈希函数 ...................................................................................................... 17
2.1.2 哈希表.......................................................................................................... 19
2.2 哈希的应用............................................................................................................. 20
2.2.1 相似性搜索 .................................................................................................. 20
2.2.2 信息安全 ...................................................................................................... 23
2.2.3 比特币.......................................................................................................... 25
2.2.4 负载均衡 ...................................................................................................... 26
第3章 动态规划与近似算法 29
3.1 基本概念 ................................................................................................................ 29
3.1.1 动态规划 ...................................................................................................... 29
3.1.2 计算复杂性 .................................................................................................. 30
3.2 字符串的编辑距离 ................................................................................................. 30
3.2.1 问题引入 ...................................................................................................... 31
3.2.2 动态规划算法............................................................................................... 33
3.2.3 滚动数组优化............................................................................................... 35
3.2.4 上界限制 ...................................................................................................... 36
3.2.5 解的回溯 ...................................................................................................... 37
3.2.6 分治算法 ...................................................................................................... 38
3.2.7 多个字符串的编辑距离 ............................................................................... 41
3.3 子集和问题............................................................................................................. 43
3.3.1 问题引入 ...................................................................................................... 43
3.3.2 子集和问题的动态规划算法........................................................................ 43
3.3.3 最优化问题 .................................................................................................. 44
3.3.4 滚动数组的技巧........................................................................................... 45
3.3.5 贪婪算法 ...................................................................................................... 46
3.3.6 松弛动态规划............................................................................................... 47
3.3.7 相关问题 ...................................................................................................... 48
3.4 旅行商问题............................................................................................................. 50
3.4.1 问题引入 ...................................................................................................... 50
3.4.2 动态规划算法............................................................................................... 52
3.4.3 一笔画问题 .................................................................................................. 52
3.4.4 Christofides算法 .......................................................................................... 54
3.4.5 Lin-Kernighan算法 ...................................................................................... 55
3.5 总结........................................................................................................................ 58
第4章 高斯消去法 59
4.1 问题引入 ................................................................................................................ 59
4.2 矩阵编程基础......................................................................................................... 60
4.3 三角方程组............................................................................................................. 62
4.3.1 三角矩阵 ...................................................................................................... 62
4.3.2 三角矩阵的存储........................................................................................... 63
4.3.3 三角方程组求解........................................................................................... 64
4.4 高斯消去法的原理 ................................................................................................. 66
4.4.1 算法概述 ...................................................................................................... 66
4.4.2 高斯变换 ...................................................................................................... 68
4.4.3 LU分解 ........................................................................................................ 69
4.4.4 Cholesky分解............................................................................................... 70
4.5 主元选择 ................................................................................................................ 71
4.5.1 列选主元 ...................................................................................................... 71
4.5.2 全选主元 ...................................................................................................... 73
4.5.3 主元与计算量............................................................................................... 74
4.6 稀疏矩阵的编程基础 ............................................................................................. 75
4.6.1 稀疏向量 ...................................................................................................... 76
4.6.2 稀疏矩阵 ...................................................................................................... 79
4.7 稀疏LU分解.......................................................................................................... 82
4.7.1 Markowitz算法 ............................................................................................ 82
4.7.2 最小度算法 .................................................................................................. 83
第5章 图论与线性规划 86
5.1 线性规划基础......................................................................................................... 86
5.1.1 Fourier Motzkin 消去法............................................................................... 89
5.1.2 基.................................................................................................................. 91
5.1.3 单纯形方法 .................................................................................................. 93
5.1.4 对偶.............................................................................................................. 95
5.2 全单模矩阵详解..................................................................................................... 98
5.2.1 关联矩阵 ...................................................................................................... 98
5.2.2 全单模矩阵 .................................................................................................. 99
5.2.3 全单模矩阵与图论....................................................................................... 100
5.2.4 全单模矩阵与线性规划 ............................................................................... 103
5.3 图论中的经典问题 ................................................................................................. 104
5.3.1 单源最短路问题........................................................................................... 104
5.3.2 二分图的最大匹配与最小覆盖问题 ............................................................ 106
5.3.3 最大流与最小割问题 ................................................................................... 108
5.4 延伸阅读 ................................................................................................................ 109
5.4.1 逐步线性规划............................................................................................... 109
5.4.2 半正定规划 .................................................................................................. 111
第6章 无约束优化 113
6.1 单峰函数的最值..................................................................................................... 114
6.1.1 三分法.......................................................................................................... 115
6.1.2 对分法.......................................................................................................... 115
6.1.3 黄金分割法 .................................................................................................. 116
6.1.4 小结.............................................................................................................. 117
6.2 无导数优化方法..................................................................................................... 118
6.2.1 模式搜索法 .................................................................................................. 118
6.2.2 坐标下降法 .................................................................................................. 119
6.2.3 代理模型法 .................................................................................................. 120
6.3 导数优化方法......................................................................................................... 121
6.3.1 线搜索.......................................................................................................... 122
6.3.2 梯度下降法 .................................................................................................. 123
6.3.3 共轭梯度法 .................................................................................................. 124
6.3.4 牛顿法.......................................................................................................... 127
6.3.5 拟牛顿法 ...................................................................................................... 128
6.4 最小二乘 ................................................................................................................ 132
6.4.1 线性最小二乘............................................................................................... 133
6.4.2 非线性最小二乘........................................................................................... 133
第7章 迭代法 136
7.1 线性方程组的迭代法 ............................................................................................. 136
7.1.1 一阶定常格式迭代法 ................................................................................... 136
7.1.2 Krylov子空间算法....................................................................................... 142
7.1.3 无约束优化方法........................................................................................... 147
7.2 非线性方程组的迭代法.......................................................................................... 147
7.2.1 不动点迭代 .................................................................................................. 148
7.2.2 Newton-Raphson迭代.................................................................................. 149
7.2.3 无约束优化方法........................................................................................... 152
第8章 插值与拟合 153
8.1 插值........................................................................................................................ 153
8.1.1 常见的插值算法........................................................................................... 154
8.1.2 插值的应用 .................................................................................................. 158
8.2 拟合........................................................................................................................ 163
8.2.1 常见的拟合算法........................................................................................... 164
8.2.2 拟合的应用 .................................................................................................. 166
参考文献 169