数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学贪婪算法与动态规划的区别
在这篇文章中，我们将了解贪婪算法和动态规划方法的区别。
贪婪算法
这是一种算法范式，它逐步构建解决方案。选择下一步时，要选择能带来最明显和直接好处的方案。
- 涉及选择局部最优值的问题将有助于选择问题的全局最优值/解决方案。这些是与贪婪算法相关的问题。
- 不能保证贪婪算法一定会找到最优解。
- 在问题的每个阶段都会做出最优选择，即局部最优解。
- 它在内存使用方面效率很高，因为无需回溯或更改之前的解决方案/值。
- 总的来说，与动态规划技术相比，它速度更快。
- 示例：Dijkstra最短路径算法，时间复杂度为O(ELogV + VLogV)。
- 贪婪算法中的解是用前向方法计算的，从不访问或更改之前的数值/解。
动态规划
这是一种优化技术，用于存储子问题的解，以便将来需要时无需重新计算。它们可以直接从预先计算的集合中提取。它将时间复杂度从指数复杂度降低到多项式复杂度。
- 例如：可以通过计算将递归解转换为动态规划问题。
- 在此方法中，每一步的决策都是通过考虑当前问题和先前已解决的子问题的解来做出的。这将用于计算最优值/解。
- 动态规划问题的解一定是最优解。
- 这里选择的最佳解是全局最优解。它使用某些公式来存储先前计算的状态值。
- 需要动态规划表进行记忆化。这增加了内存复杂度。
- 它相对较慢。
- 示例：Bellman-Ford算法，时间复杂度为O(VE)。
- 动态规划通过从小问题（已找到最优解）开始逐步构建，从而确定解决方案。
更新于：2021年3月2日
529 次浏览
广告