贪心算法
#算法/贪心算法
目录
1. 贪心算法的特性
1.1. 特性 1：局部最优 → 全局最优
举个例子：
- 你面前放着 100 张不同面值人民币，你只能拿
十张，怎么才能拿最多的面额？ - 显然每次选择剩下钞票中面值最大的一张，最后你的选择一定是最优的。
上面的例子 ， 每一步都做出一个局部最优的选择，最终的结果就是全局最优
1.2. 特性 2：符合贪心算法的线性规划问题复杂度比较低
- 一个算法问题使用暴力解法需要
指数级时间 - 如果能使用动态规划消除重叠子问题，就可以降到
多项式级别的时间 - 如果满足贪心选择性质，那么可以进一步降低时间复杂度，达到
线性级别的
2. 「贪心选择性质」和「最优子结构」的区别
- 最优子结构
- 已经把所有子问题的最优解都求出来了，
- 基于这些子问题的最优解推导出原问题的最优解
- 贪心选择
- 局部最优的选择策略，就能直接知道哪个子问题的解是最优的了
- 且这个局部最优解可以推导出原问题的最优解。
- 此时此刻我就能知道，不需要等到所有子问题的解算出来才知道