蛮力和动态规划的区别
蛮力:
- 它用最直接的方法解决了一个问题。然而,它通常不是一个非常理想的解决方案,也不是一个灵活的解决方案,但它可以完成工作。
- 众所周知的蛮力编程示例是为访问多个测试用例并返回创建最有效且成本最低的路径。
- 蛮力编程测试每一个可能的路由组合;而其他数学算法在测试用例数量较大的情况下可以更快地得到结果。
- 蛮力技术通常不用于工业领域,因为它们会减慢整个产品或软件的速度。
动态规划:
- 动态规划方法类似于分治法,将问题分解为越来越小的子问题。
- 但与分治法不同的是,这些子问题不能独立解决。
- 相反,这些较小的子问题的结果被记住并用于相似或重叠。
使用动态规划的不同方法:
- Top-Down: 开始通过分解来解决给定的问题。如果我们看到问题已经被解决,那么就返回保存的答案。如果它还没有被解决,解决它并保存答案。
- Bottom-Up: 分析这个问题,看看子问题的解决顺序,然后从不起眼的子问题开始解决,直到给定的问题。在这个过程中,可以保证在解决问题之前先解决子问题。
蛮力和动态规划的区别:下表中清楚地提到了这两种方法的区别。
参数 of Comparison | Brute Force | Dynamic Programming |
---|---|---|
Methodology | 它找到给定问题的所有可能结果。 | 结果只有一个。 |
时间复杂度 | O(xy),其中x是要找到的字符数,y是输入的大小。 | O(x),其中x是唯一子问题的个数 |
示例 | 选择排序 | 弗洛伊德Warshell |
Iterations | 迭代次数更多 | 迭代次数更少 |
Efficiency | 效率较低 | 这样效率更高 |
Uses | 当我们的数据量更少的时候 | 当我们有大量的数据时 |