4
Greedy Algorithm | 一直进步 做喜欢的
source link: https://xfliu1998.github.io/2023/05/21/Greedy-Algorithm/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Greedy Algorithm
Created2023-05-21|Updated2023-06-04|Data Structures and Algorithms
Word count:608|Reading time:1min|Post View:1|Comments:
贪心算法（Greedy algorithm）是一种常用的算法设计策略，用于解决优化问题。它的基本思想是在每一步选择中都采取当前状态下的最优选择，希望通过局部最优选择的累积，达到全局最优解。知识点：
- 贪心选择性质：贪心算法每一步都选择当前最优解，不考虑未来的结果。它通常通过贪心选择性质来判断当前最优解是否会导致最终的全局最优解。
- 最优子结构：问题具有最优子结构性质意味着最优解可以通过子问题的最优解来构造。贪心算法常常利用最优子结构性质来推导问题的最优解。
- 适用性：贪心算法适用于一些特定类型的问题，如活动选择问题、霍夫曼编码、最小生成树等。对于一些问题，贪心算法可能会得到近似最优解，但不一定是全局最优解。
- 与动态规划的区别：贪心算法与动态规划类似，都是求解优化问题的方法。然而，贪心算法每一步的选择都只考虑当前状态，不需要保存子问题的解。而动态规划则需要记录并利用子问题的解来构建最优解。
虽然贪心算法具有一定的局限性，无法解决所有优化问题，但在一些特定情况下，它具有简单、高效的优势，并且可以用于快速求解近似最优解的问题。比如一个算法问题使用暴力解法需要指数级时间，如果能使用动态规划消除重叠子问题，就可以降到多项式级别的时间，如果满足贪心选择性质，那么可以进一步降低时间复杂度，达到线性级别的。
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK