知识点:
- P35
分治策略 - P37
矩阵 Strassen 算法 - P45
用递归树方法求解递归式,并分析运行时间 f(n) - P50
主定理 T(n) 和 f(n) 的三种情况分析,注意三种情况之间的gap
NP完全性 - P616
- 3SAT 3合取范式可满足性问题
- 证明NPC规约
动态规划 (小题多)
- 最优子问题
- 备忘录dp和自顶向下dp区别
- 矩阵链乘问题
贪心算法 (分数最多,算法设计大题都用贪心)
- 活动选择问题 (选择)
- 背包贪心求解
- 拟阵 (小题)
近似算法
- 近似概念
- 01背包问题的两种算法
- 近似比
- 多机调度描述
