1. 算法分析基础 #

1.1 时间复杂度分析 #

• 大O表示法
• 最好、最坏和平均情况分析
• 递归关系求解
• 主定理应用

1.2 空间复杂度分析 #

• 辅助空间需求
• 原地算法
• 空间-时间权衡

1.3 渐进分析 #

• Ω和Θ表示法
• 渐进效率比较
• 算法效率的实际意义

2. 分治法 #

2.1 基本概念 #

• 分治策略原理
• 递归结构
• 子问题划分

2.2 经典算法 #

• 归并排序
• 快速排序
• 二分查找
• 大整数乘法

2.3 复杂度分析 #

• 递归树方法
• 主定理应用
• 分治效率分析

3. 动态规划 #

3.1 基本原理 #

• 最优子结构
• 重叠子问题
• 记忆化技术

3.2 设计步骤 #

• 状态定义
• 状态转移方程
• 边界条件确定

3.3 经典问题 #

• 背包问题
• 最长公共子序列
• 矩阵链乘法
• 最短路径问题

4. 贪心算法 #

4.1 贪心选择性质 #

• 局部最优选择
• 贪心策略证明
• 适用范围分析

4.2 典型应用 #

• 活动选择问题
• 霍夫曼编码
• 最小生成树算法
• 单源最短路径

5. 回溯法 #

5.1 基本框架 #

• 状态空间树
• 剪枝策略
• 解空间搜索

5.2 经典问题 #

• N皇后问题
• 图的着色问题
• 子集和问题
• 旅行商问题

6. 分支限界法 #

6.1 基本原理 #

• 界限函数设计
• 优先队列使用
• 搜索策略选择

6.2 实现方式 #

• FIFO分支限界
• 优先队列分支限界
• 最小成本优先搜索

7. 随机化算法 #

7.1 随机算法类型 #

• 拉斯维加斯算法
• 蒙特卡洛算法
• 随机化快速排序

7.2 概率分析 #

• 期望运行时间
• 随机化优势
• 概率保证

8. 近似算法 #

8.1 近似比分析 #

• 性能保证
• 最坏情况分析
• 近似方案设计

8.2 典型应用 #

• 顶点覆盖问题
• 旅行商问题近似
• 集合覆盖问题

9. 并行算法设计 #

9.1 并行计算模型 #

• PRAM模型
• 并行复杂度
• 加速比分析

9.2 并行算法技术 #

• 分治并行化
• 流水线技术
• 并行排序算法

10. 在线算法 #

10.1 竞争分析 #

• 竞争比定义
• 最坏情况分析
• 随机化在线算法

10.2 典型问题 #

• 页面调度算法
• k服务器问题
• 在线背包问题

11. 启发式算法 #

11.1 元启发式方法 #

• 模拟退火算法
• 遗传算法
• 蚁群优化算法

11.2 局部搜索 #

• 爬山算法
• 禁忌搜索
• 邻域结构设计

12. 算法设计模式 #

12.1 常用技巧 #

• 双指针技术
• 滑动窗口
• 前缀和数组

12.2 问题转化 #

• 问题归约
• 图论建模
• 线性规划转化

13. 算法优化技术 #

13.1 性能优化 #

• 缓存友好设计
• 循环展开
• 预处理技术

13.2 空间优化 #

• 位运算技巧
• 压缩存储
• 懒加载技术

14. 实际应用考虑 #

14.1 工程实现 #

• 代码可读性
• 错误处理
• 边界情况处理

14.2 性能调优 #

• 性能剖析
• 瓶颈识别
• 优化策略选择