算法设计技巧与分析
基本信息
- 原书名称：算法设计技巧与分析（Algorithm Design Techniques and Analysis）
- 作者：[沙特] 米哈伊·阿苏外耶（Mihai A. Alistarh，此处按原文署名翻译）
- 出版社：Morgan Kaufmann（Elsevier）
- 文件大小：31.56 MB
- 总页数：328页
- 文档类型：混合类型（部分文字页 + 部分扫描页）
- 处理方式：pdf-inspector 文本提取 + OCR 补充扫描页
核心内容概述
本书是一本经典的算法设计与分析教材，从理论和实践两个角度系统地介绍了算法设计的核心技巧。全书分为三大部分：基本方法、高级技巧和专题分析。
第一部分：基础算法设计方法
1. 分治法（Divide and Conquer）
- 基本思想：将问题分解为若干子问题，递归求解后再合并
- 经典案例：归并排序、快速排序、最大子数组问题
- 复杂度分析：递归树、主定理（Master Theorem）
2. 动态规划（Dynamic Programming）
- 无记忆递归 → 记忆化搜索 → 表格法
- 最优子结构与重叠子问题
- 典型问题：0/1背包、最长公共子序列、矩阵链乘法
3. 贪心算法（Greedy Algorithm）
- 贪心选择性质与最优子结构
- 区间调度、哈夫曼编码、最小生成树（Kruskal/Prim）
4. 回溯法（Backtracking）
- 解空间树与剪枝策略
- N皇后、子集和、旅行商问题
第二部分：高级设计技巧
5. 随机化算法（Randomized Algorithms）
- 随机化快速排序、随机选择算法
- 蒙特卡洛与拉斯维加斯算法
6. 摊还分析（Amortized Analysis）
- 聚合分析、记账法、势能法
- 动态数组、并查集、斐波那契堆
7. 近似算法（Approximation Algorithms）
- NP-hard问题的近似策略
- 集合覆盖、顶点覆盖、旅行商近似
第三部分：专题深度分析
8. 图算法
- BFS/DFS及其变体
- 最小生成树、最短路径（Dijkstra、Bellman-Ford）
- 网络流（Ford-Fulkerson）
9. 字符串算法
- KMP、Rabin-Karp、Z算法
- 后缀数组与后缀树
10. 几何算法
- 凸包（Graham Scan、Monotone Chain）
- 最近点对、线段相交
关键知识点
- 主定理：求解形如 T(n) = aT(n/b) + f(n) 的递推关系
- DP状态设计：如何定义状态、转移方程、边界条件
- 贪心正确性证明：交换论证、活动选择引理
- 摊还复杂度：不同分析方法的选择与适用场景
- NP完全性：多项式归约、经典NP完全问题
与其他知识的关联
- 编程珠玑（第二版）中文版 - 算法编程实践与思维训练
- 算法导论中文版 - 更全面的算法理论基础
- 计算机程序的构造和解释 - 递归与分治的函数式视角
- Head First 设计模式 - 设计模式与算法策略的交叉
阅读建议
- 适合有一定编程基础的读者，重点在于理解算法思想而非实现细节
- 每个章节后均有习题，建议动手实现以加深理解
- 动态规划和贪心算法是重点，需反复练习
- 可结合实际项目中的性能瓶颈问题，用本书技巧优化
笔记说明
- 本笔记基于 pdf-inspector 文本提取结果整理
- 扫描页部分已用 PP-OCRv6 Small 模型补充提取
- 内容涵盖全书核心章节与关键概念