Part4 高级设计和分析技术
动态规划 贪心算法 摊还分析 算法导论
内容
注意事项
总结：
- 划分——要求子问题无关
- 依赖关系——最优子结构，决定划分的可用方式
- 依赖关系的必要要求，具有递归的形式——将问题逐渐变小成trivial的子问题集（这个要求已经包含在最优子结构的定义之中了）
- 首先我们要知道，算法层面只能通过减少重复运算来降低时间复杂度。而有效减少重复运算的一种方式就是对问题进行划分，比如分治模式中将问题一分为二。动态规划和贪心算法也是如此（注意两者的划分方式是相同的，只不过子问题的求解方式不同），它们也有自己的一种划分方式。
- 既然是通过划分这一途径，就要保证划分后的子问题是无关的，否则划分将没有意义。
- 分支模式中，母问题的解不依赖于子问题的划分方式（只要划分是连续的）；此处母问题的解依赖于子问题的划分方式，因为对原问题的划分本身就是原问题解的一部分。为了寻找到新的划分方法，关键是要知道母、子问题之间是如何依赖的。而且直观上，这种关系用该具有递推关系，这样才能最终把大问题尽可能地变成最小的子问题，由于最小的子问题一般都是trivial的，其答案可以直接求解，比如说一个数的排序问题。
- 最优子结构给出了这种依赖关系。根据这种特定的“规模”的依赖关系，动态规划采取的划分方式就是先把原问题划分成规模最小的子问题集，求解这些子问题集并记录它们的解，再根据依赖关系，就能得到规模更大的子问题的解直至原问题
- 最小体现了本质，无论是自顶向下还是自底向上都要先解决这些最小子问题，不过自顶向下，可能会忽略一些子问题。
动态规划
- 通常用于求解最优化问题，通过做出一组选择来达到最优解
- 选择子集会生成相同的子问题，通过记录这些重复出现的子问题的解来减少重复运算
贪心算法
- 通常用于求解最优化问题，，通过做出一组选择来达到最优解
- 思想是每部都追求逐步最优
- 速度比动态规划快，但是不能保证能得到最优解
摊还分析
用来分析一类特定的算法——执行一组相似的操作组成的序列
