书: https://pan.baidu.com/s/1xhc2t938Uhd6HLI6pHjlVg?pwd=77ya
笔记如下：
1. 算法基础与分析方法
- 算法复杂度：用大O表示法（O(n), O(log n)等）衡量时间与空间效率，区分最坏、平均和最好情况。
- 递归与分治：递归需注意基线条件（Base Case），分治策略（如归并排序）将问题分解为子问题。
- 贪心算法：局部最优解不保证全局最优（如霍夫曼编码），需验证正确性。
- 动态规划（DP）：通过备忘录（Memoization）或制表法（Tabulation）避免重复计算（如背包问题）。
2. 数据结构与经典算法
- 数组与链表：数组随机访问快（O(1)），链表插入/删除高效（O(1)）。
- 哈希表：冲突解决策略（链地址法、开放寻址法），负载因子影响性能。
- 树结构：二叉搜索树（BST）的平衡性决定效率（退化为链表时O(n)）。
- 图算法：
- BFS（广度优先）解决最短路径（无权图）。
- DFS（深度优先）用于拓扑排序、连通分量。
- 堆与优先队列：二叉堆实现插入（O(log n)）和取最值（O(1)），适用于调度场景。
3. 排序与搜索
- 快速排序：平均O(n log n)，分区（Partition）策略影响性能（如三数取中法）。
- 堆排序：原地排序但缓存不友好，适合大数据量。
- 二分搜索：要求数据有序，变种（如查找左边界）需处理边界条件。
4. 高级算法设计
- 回溯法：通过剪枝（Pruning）优化穷举（如N皇后问题）。
- 网络流算法：Ford-Fulkerson方法解决最大流问题（如交通网络优化）。
- NP完全问题：近似算法（如旅行商问题的2-近似）或启发式策略（遗传算法）。
5. 实际应用与优化
- 字符串匹配：
- KMP算法利用部分匹配表跳过无效比较。
- Boyer-Moore从右向左匹配，适合长模式串。
- 几何算法：扫描线算法（如矩形重叠检测）和凸包（Graham Scan）。
- 并行算法：MapReduce分治思想（如大规模数据排序）。
6. 工程实践建议
- 算法选择权衡：时间 vs. 空间、实现复杂度 vs. 维护成本。
- 测试与验证：
- 边界测试（空输入、极值）。
- 随机化测试（如快速排序的随机化分区）。