算法分析

围绕算法分析建立可解释、可验证的知识主线。

阅读起点

学习前先阅读：数据结构与算法学习路线。

全书顺序

本书按知识依赖组织。主线先建立可运行的共同模型，再进入机制、工程边界和生产约束；维护与前沿内容明确标注，不改变主线的学习顺序。

第1章｜成本模型与渐进记号

理解本章成本模型与渐进记号的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。

1. 成本模型：确定什么算成本：理解成本模型：确定什么算成本的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
2. 输入规模：元素数、位数与多维度量：理解输入规模：元素数、位数与多维度量的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
3. 渐进记号：O、Ω、Θ 与严格增长：理解渐进记号：O、Ω、Θ 与严格增长的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
4. 增长族：常数、对数、幂、指数与阶乘：理解增长族：常数、对数、幂、指数与阶乘的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
5. 组合成本：顺序、嵌套、分支与求和：理解组合成本：顺序、嵌套、分支与求和的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
6. 渐进边界：何时忽略常数、何时不能：理解渐进边界：何时忽略常数、何时不能的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。

第2章｜递推、分治与递归树

理解本章递推、分治与递归树的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。

1. 递推建模：从递归结构写出成本式：理解递推建模：从递归结构写出成本式的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
2. 递归树与展开法：求和与上下界：理解递归树与展开法：求和与上下界的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
3. 主定理：适用条件与不同分支：理解主定理：适用条件与不同分支的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
4. 分治算法分析：排序、选择与几何：理解分治算法分析：排序、选择与几何的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
5. 递归空间：深度、栈与尾递归：理解递归空间：深度、栈与尾递归的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。

第3章｜摊销分析与数据结构

理解本章摊销分析与数据结构的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。

1. 摊销分析基础：单次与序列保证：理解摊销分析基础：单次与序列保证的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
2. 聚合法：动态数组扩容与总成本：理解聚合法：动态数组扩容与总成本的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
3. 记账法：预存成本与信用：理解记账法：预存成本与信用的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
4. 势能法：势函数与势能变化：理解势能法：势函数与势能变化的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
5. 动态结构分析：哈希扩容、并查集与自调整：理解动态结构分析：哈希扩容、并查集与自调整的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
6. 摊销与实时：序列保证能否满足单次延迟：理解摊销与实时：序列保证能否满足单次延迟的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。

第4章｜概率、随机与平均分析

理解本章概率、随机与平均分析的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。

1. 期望成本：线性期望与指示变量：理解期望成本：线性期望与指示变量的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
2. 输入分布：平均输入与随机算法：理解输入分布：平均输入与随机算法的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
3. 随机算法：Las Vegas、Monte Carlo 与采样：理解随机算法：Las Vegas、Monte Carlo 与采样的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
4. 概率工具：Markov、Chebyshev 与 Chernoff：理解概率工具：Markov、Chebyshev 与 Chernoff的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
5. 可靠性与失败概率：重复放大与种子：理解可靠性与失败概率：重复放大与种子的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。

第5章｜下界、难度与不可避免的成本

理解本章下界、难度与不可避免的成本的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。

1. 信息论下界：决策树、比较次数与熵：理解信息论下界：决策树、比较次数与熵的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
2. 模型下界：比较模型、代数模型与流模型：理解模型下界：比较模型、代数模型与流模型的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
3. 排序与搜索下界：比较排序的必然成本：理解排序与搜索下界：比较排序的必然成本的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
4. 归约与困难性：问题变换与复杂度传递：理解归约与困难性：问题变换与复杂度传递的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
5. P/NP 与近似：可验证、NP 完全与参数化：理解P/NP 与近似：可验证、NP 完全与参数化的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。

第6章｜空间、I/O、并行与实证验证（第1段）

理解本章空间、I/O、并行与实证验证的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。

1. 空间复杂度：辅助空间、递归栈与持久化：理解空间复杂度：辅助空间、递归栈与持久化的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
2. 缓存与局部性：分块、缓存行与内存带宽：理解缓存与局部性：分块、缓存行与内存带宽的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
3. 外存模型：I/O 次数、块与数据库连接：理解外存模型：I/O 次数、块与数据库连接的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
4. 并行成本：加速比、通信与 Amdahl 定律：理解并行成本：加速比、通信与 Amdahl 定律的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
5. 分布式成本：消息数、延迟与容错：理解分布式成本：消息数、延迟与容错的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
6. 实证分析：基准设计、统计与剖析：理解实证分析：基准设计、统计与剖析的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。

第7章｜空间、I/O、并行与实证验证（第2段）

理解本章空间、I/O、并行与实证验证的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。

1. 复杂度报告：模型、假设、推导与复现：理解复杂度报告：模型、假设、推导与复现的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
2. 成本模型：理解成本模型的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
3. 增长族比较：理解增长族比较的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
4. 递归树展开：理解递归树展开的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
5. 主定理：理解主定理的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
6. 递归空间：理解递归空间的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。

第8章｜空间、I/O、并行与实证验证（第3段）

理解本章空间、I/O、并行与实证验证的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。

1. 势能函数：理解势能函数的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
2. 动态结构：理解动态结构的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
3. 摊销与实时：理解摊销与实时的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
4. 线性期望与指示变量：理解线性期望与指示变量的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
5. 输入分布：理解输入分布的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
6. 概率工具：理解概率工具的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。

第9章｜空间、I/O、并行与实证验证（第4段）

理解本章空间、I/O、并行与实证验证的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。

1. 可靠性：理解可靠性的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
2. Monte Carlo 算法：理解Monte Carlo 算法的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
3. 决策树：理解决策树的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
4. 模型限制：理解模型限制的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
5. 归约：理解归约的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
6. P/NP：理解P/NP的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。

第10章｜空间、I/O、并行与实证验证（第5段）

理解本章空间、I/O、并行与实证验证的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。

1. 排序下界：理解排序下界的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
2. 缓存局部性：理解缓存局部性的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
3. 外存模型：理解外存模型的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
4. 加速比与 Amdahl 定律：理解加速比与 Amdahl 定律的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
5. 分布式通信：理解分布式通信的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
6. 实证分析：理解实证分析的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。

第11章｜空间、I/O、并行与实证验证（第6段）

理解本章空间、I/O、并行与实证验证的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。

1. 空间复杂度：理解空间复杂度的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
2. 基准设计：理解基准设计的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
3. 复杂度报告：理解复杂度报告的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
4. 多规模拟合：理解多规模拟合的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。

阅读边界

本页是学习路线和专题入口，不替代专题笔记中的机制解释、可运行示例和练习。笔记尚未完成的专题会先显示为占位页；已有经验的读者可以跳到具体章节，再按前置关系回补。

路线状态

本路线的目录已完成本轮架构审查；专题笔记的内容质量和来源审查另行进行。