《算法导论》学习笔记
《算法导论》学习笔记
《算法导论》(Introduction to Algorithms)是由Thomas H. Cormen、Charles E. Leiserson、Ronald L. Rivest和Clifford Stein编写的经典算法教材。本文记录了学习该书的关键概念和心得。
算法分析基础
渐近符号
学习算法的第一步是理解如何分析算法效率，《算法导论》介绍了以下关键符号：
- O符号(上界)：表示算法在最坏情况下的运行时间
- Ω符号(下界)：表示算法在最佳情况下的运行时间
- Θ符号(紧确界)：当上界和下界相同时使用
这些符号帮助我们抽象掉常数因子和低阶项，专注于算法增长率的本质。
递归方程
解决递归算法的时间复杂度时，书中介绍了几种方法：
- 代入法：猜测解的形式，然后用数学归纳法证明
- 递归树法：将递归过程可视化为树
- 主方法：适用于形如T(n) = aT(n/b) + f(n)的递归式
排序算法
比较排序
书中详细分析了多种排序算法：
| 算法 | 最坏时间复杂度 | 平均时间复杂度 | 空间复杂度 | 稳定性 |
|---|---|---|---|---|
| 插入排序 | O(n²) | O(n²) | O(1) | 稳定 |
| 归并排序 | O(n log n) | O(n log n) | O(n) | 稳定 |
| 堆排序 | O(n log n) | O(n log n) | O(1) | 不稳定 |
| 快速排序 | O(n²) | O(n log n) | O(log n) | 不稳定 |
学习心得：虽然归并排序和快速排序的渐近复杂度相同，但在实践中快速排序通常更快，这说明常数因子在实际应用中也很重要。
线性时间排序
书中还介绍了不基于比较的排序算法：
- 计数排序：O(n+k)，适用于范围较小的整数
- 基数排序：O(d(n+k))，适用于固定长度的项目
- 桶排序：平均O(n)，适用于均匀分布的输入
数据结构
基本数据结构
- 堆：实现优先队列的高效数据结构
- 二叉搜索树：支持动态集合操作
- 红黑树：自平衡的二叉搜索树，保证O(log n)的操作时间
- 哈希表：提供平均O(1)的查找时间
学习心得：理解这些数据结构的权衡非常重要。例如，红黑树虽然比普通二叉搜索树复杂，但它保证了最坏情况下的性能。
高级数据结构
- B树：为磁盘访问优化的搜索树
- 斐波那契堆：提供理论上更优的合并操作
- van Emde Boas树：支持O(log log u)时间的操作
图算法
图的表示
- 邻接矩阵：适用于稠密图
- 邻接表：适用于稀疏图
图的遍历
- 广度优先搜索(BFS)：使用队列，适合寻找最短路径
- 深度优先搜索(DFS)：使用栈或递归，适合拓扑排序
最短路径算法
- Dijkstra算法：适用于非负权重图
- Bellman-Ford算法：可处理负权重边
- Floyd-Warshall算法：解决所有点对最短路径问题
高级主题
动态规划
动态规划的关键步骤：
- 刻画最优解的结构
- 递归定义最优解的值
- 自底向上计算最优解
- 构造最优解
经典例题：
- 钢条切割问题
- 最长公共子序列
- 0-1背包问题
贪心算法
贪心算法在每一步都做出当前看起来最好的选择。适用于具有最优子结构和贪心选择性质的问题。
经典例题：
- 活动选择问题
- Huffman编码
- 最小生成树算法(Kruskal和Prim)
学习心得
《算法导论》是一本理论性很强的教材，但其中的思想对实际编程有深远影响：
- 算法分析思维：学会分析时间和空间复杂度，权衡不同算法的适用场景
- 问题抽象能力：将实际问题抽象为经典算法问题的能力
- 数据结构选择：根据操作特点选择合适的数据结构
学习建议：结合实际编程练习，特别是通过LeetCode等平台的题目来巩固理论知识。