本书为《算法笔记》的第2版，本书介绍了若干常见算法，既包括排序、哈希等基础算法，也包括无约束优化、插值与拟合等数值计算方法。本书在介绍算法的同时，结合了作者自己对数学背景、应用场景的理解，便于读者把握算法的核心思想。本书尽可能地避开了以应试为导向的灌输式讲解，力求引起读者的兴趣并扩大其视野，例如在介绍哈希时，讲解了如何将哈希的算法思想运用于相似性搜索、负载均衡等多个实际问题中；又如在介绍高斯消去法时，讲解了相关的数学理论及编程实现上的具体技巧，并将其运用于对大规模稀疏线性方程组的求解，等等。

本书取名“算法笔记”，主要源自作者在中国科学院读书期间学习算法时的体会，可以作为现有算法教科书的补充。本书讨论了计算机算法相关的若干话题，在介绍算法的同时结合了作者自己对数学背景、应用场景的理解，便于读者把握算法的核心思想。阅读本书需要有一定的数学基础和算法基础。 许多经典的算法教科书都详尽地介绍了算法的各个知识点，但在覆盖面广的同时难免会忽略许多细节问题。例如，哪些算法真正值得运用到实际问题中，算法有哪些变种值得我们了解，算法背后有哪些数学理论支撑，等等。 本书共包括8 章。各章中除了讲解基本知识，还回答了许多相关的有趣问题。 ? 排序：排序算法有很多种，在比较流行的编程语言中都有提供排序算法的库函数，直接调用这些库函数会非常简单。但它们所使用的算法为何有效，这些算法与一些经典的排序算法又有什么区别？ ? 哈希：在讲解哈希算法时一般主要介绍哈希函数的作用及哈希表的不同实现方法。但将哈希函数运用于不同的问题时，最为巧妙的地方在于哈希函数的设计。对于不同领域的问题，哈希函数都有哪些有趣的形式？ ? 动态规划与近似算法：通常这两类算法并不会放在一起去探讨。在面对不同复杂性的问题时，它们会有怎样的互补作用？ ? 高斯消去法：算法的基本过程是很简单的，但在实际使用中远远没有那么简单。如何保持计算的稳定性？如何解决稀疏矩阵的计算效率问题？ ? 图论与线性规划：图论中的许多问题都可以用线性规划去解决。图论中的一些经典结论实质上也可以用线性规划的相关定理去解释。线性规划作为一个更一般的工具，如何用于处理图论问题？ ? 无约束优化：无约束优化主要用于求解函数的最大值或最小值的问题。常用的这些方法为何有效？它们之间的差别在哪里？ ? 迭代法：常见的迭代算法都有哪些？它们为什么有效？ ? 插值与拟合：插值与拟合的思想是什么？有什么异同？如何运用于图像处理？ 读者可以发现，本书不仅指出了哪些算法可以解决问题，还指出了哪些算法可以更好地解决问题。这有助于我们对算法的深入理解。 由于作者水平有限，书中难免有错误和不足之处，欢迎读者批评和指正。 刁瑞、谢妍

第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