经典算法
经典算法是程序设计中反复出现的问题解决套路。它们通常可以迁移到很多场景，例如搜索、推荐、缓存、调度、路径规划、数据去重和性能优化。
一、复杂度分析
复杂度用于描述算法随着输入规模增长时的成本变化。
| 复杂度 | 含义 | 例子 |
|---|---|---|
| O(1) | 常数时间 | 数组下标访问 |
| O(log n) | 对数时间 | 二分查找 |
| O(n) | 线性时间 | 遍历数组 |
| O(n log n) | 线性对数 | 快速排序、归并排序 |
| O(n²) | 平方时间 | 双重循环比较 |
分析算法时同时关注：
- 时间复杂度；
- 空间复杂度；
- 最坏情况；
- 平均情况；
- 输入数据特征。
二、排序算法
常见排序：
| 算法 | 平均复杂度 | 特点 |
|---|---|---|
| 冒泡排序 | O(n²) | 简单，效率低 |
| 插入排序 | O(n²) | 小规模或基本有序时较好 |
| 选择排序 | O(n²) | 交换次数少 |
| 快速排序 | O(n log n) | 实战常用，最坏 O(n²) |
| 归并排序 | O(n log n) | 稳定，需要额外空间 |
| 堆排序 | O(n log n) | 原地排序，不稳定 |
三、查找算法
常见查找：
- 顺序查找：适合无序小数据。
- 二分查找：适合有序数组。
- 哈希查找：平均 O(1)，依赖哈希函数。
- 树查找：适合动态有序数据。
二分查找重点是边界：
left <= right
mid = left + (right - left) / 2
根据条件移动 left 或 right
四、递归和分治
递归适合把问题拆成相同结构的子问题。
分治的典型流程：
典型算法：
- 归并排序；
- 快速排序；
- 二分查找；
- 大整数乘法；
- 最近点对。
五、回溯
回溯适合搜索所有可能解。
通用结构：
适合：
- 全排列；
- 子集；
- 组合；
- N 皇后；
- 数独。
六、贪心
贪心每一步都选择当前看起来最优的方案。
适合贪心的问题必须满足：
- 局部最优能推出全局最优；
- 子问题之间结构清晰；
- 选择后不会破坏后续最优性。
典型场景：
- 区间调度；
- 找零钱部分问题；
- Huffman 编码；
- 最小生成树。
七、动态规划
动态规划适合有重叠子问题和最优子结构的问题。
关键步骤：
- 定义状态。
- 写出状态转移方程。
- 确定初始值。
- 确定遍历顺序。
- 推导结果。
常见问题：
- 背包问题；
- 最长递增子序列；
- 最长公共子序列；
- 编辑距离；
- 爬楼梯；
- 股票买卖。
八、布隆过滤器
布隆过滤器是一种空间效率很高的概率型数据结构，用于判断一个元素是否可能存在。
特点：
- 判断不存在一定准确；
- 判断存在可能误判；
- 不能直接删除普通元素；
- 适合大规模去重和缓存穿透防护。
典型场景：
- 判断 URL 是否爬取过；
- 防止缓存穿透；
- 大规模黑名单判断；
- 日志去重。
总结
经典算法学习路线：