算法分析
这门课学什么
课程讲如何用数学精确预测算法的性能。内容包括递推关系、生成函数和渐近分析，再用到树、排列、字符串和字典树上。
内容摘要
这门课讲怎样用数学精确预测算法的性能。它不满足于大 O 上界，而是求出比较次数或运行时间的精确表达式和渐近式，并用实验验证。课程延续高德纳（Donald Knuth）开创的算法分析传统，对应塞奇威克和弗拉若莱合著的《算法分析导论》（An Introduction to the Analysis of Algorithms）。
全课 9 讲，分 2 个阶段。第 1 阶段是第 1–5 讲，讲数学工具：先用快速排序演示完整的分析流程，再讲递推关系、生成函数、渐近分析，最后简介解析组合学的符号方法。第 2 阶段是第 6–9 讲，讲应用：把这些工具用到树、排列、字符串与字典树、单词与映射 4 类基本组合结构上，并联系到二叉搜索树、排序、散列表这些具体算法。
每讲配 1 个测验和 1 组课后习题，第 2 讲另有 2 个小测验，全课共 11 个测验。没有编程作业。习题要求学生自己推导递推、求生成函数和渐近式。
学完以后，学生能为常见算法建立数学模型，能解递推关系，能用生成函数求均值和分布，并能读懂算法论文里的平均情况分析。这门课是学习 Analytic Combinatorics 的直接前导课。
塞奇威克讲课把数学推导和算法实例交替展开，每讲先提出一个具体问题，再引出需要的数学工具。课程要求离散数学和微积分基础，节奏偏快，建议边看边动笔推导。
为什么值得学
课程延续 Knuth 开创的算法分析传统。它连接《算法》系列和《解析组合学》。
课程信息
- 学校
- 普林斯顿（Princeton）
- 讲师
- 罗伯特·塞奇威克（Robert Sedgewick）
- 学期
- self-paced
- 平台
- Coursera
- 费用
- 免费
- 难度
- 高级
- 学时
- 9 个单元 × 每单元 2–3 小时
- 先修
- 需要离散数学和微积分基础。
- 材料
- 视频、幻灯片、教材
- 许可证
- 未注明
课程大纲 · 共 9 节
大纲依据：Coursera 模块列表（9 讲，每讲一个模块；结构取自 api.coursera.org onDemandCourseMaterials.v2 与课程页）（查看原始页面 ↗）
- 1算法分析Analysis of Algorithms
讲算法分析的历史和科学方法，以快速排序为例走完建模、推导和验证的全过程。
- 2递推关系Recurrences
讲递推的数值计算、望远镜求和和递推的分类，分析归并排序，并讲主定理。
- 3生成函数Generating Functions
讲普通生成函数和指数生成函数，用它们计数、推导卡特兰数和解递推。
- 4渐近分析Asymptotics
讲标准渐近尺度、渐近展开的运算、有限和的渐近估计和二元渐近。
- 5解析组合学Analytic Combinatorics
简介符号方法、有标号对象和系数渐近，为后面 4 讲提供统一工具。
- 6树Trees
讲树与森林的计数、二叉搜索树、路径长度，以及其他类型的树。
- 7排列Permutations
讲排列的循环结构、从左到右的最小值和其他参数，并用二元生成函数求参数分布。
- 8字符串与字典树Strings and Tries
讲带限制条件的位串、形式语言，以及字典树和它的参数分析。
- 9单词与映射Words and Mappings
讲生日问题、集券问题和散列表的分析，最后讲随机映射的结构。
普林斯顿的其他经典课
- 算法（上） · Algorithms, Part I
- 算法（下） · Algorithms, Part II
- 计算机科学：有目的的编程 · Computer Science: Programming with a Purpose
- 计算机科学：算法、理论与机器 · Computer Science: Algorithms, Theory, and Machines
- 解析组合学 · Analytic Combinatorics
- 比特币与加密货币技术 · Bitcoin and Cryptocurrency Technologies