蛮力与动态规划：差异与比较

在我们的日常生活中会遇到很多问题。 同样，编程领域也存在很多问题。

有很多方法可以解决与算法和编程相关的特定问题。 蛮力和动态编程都是解决问题和找到解决方案的技术类型。

关键精华

1. 蛮力算法详尽地搜索所有可能的解决方案，而动态规划将问题分解为更小的重叠子问题并存储解决方案以供重用。
2. 与蛮力方法相比，动态规划提高了效率并降低了计算复杂性。
3. 蛮力方法更容易实现，而动态规划需要对问题有更深入的理解，以确定最优子结构和重叠子问题。

蛮力与动态规划

当中的差异： 蛮力 而动态规划就是效率。 这两种技术都有其效率。 这 蛮力 方法对给定的数据集进行多次迭代，因此效率很低，而动态规划方法只对数据集进行一次迭代，因此效率很高。 但是，是的，这两种方法在不同情况下都有用。

蛮力方法找到与给定问题相关的所有可能解决方案，直到找到令人满意的解决方案。 如果存在解决方案，它始终是实施和保证解决方案的最简单方法。

蛮力技术的这种性质导致其工作速度减慢。 蛮力方法始终是获得解决方案的最简单方法。

动态规划是用更少的时间和更少的精力解决问题的优化版本。 这是递归的优化，因为在递归中，我们多次解决同一组输入，而通过动态规划，我们只解决给定问题的未解决情况。

对比表

比较参数	蛮力	动态编程
研究方法	它找到给定问题的所有可能解决方案。	它只会找到一个最优解。
时间复杂度	O(mn)，其中 m 是要查找的字符数，n 是输入的大小。	O(n)，其中 n 是唯一子问题的数量
例如：	选择排序	弗洛伊德战壳
迭代次数	迭代次数较多	迭代次数较少
效率	效率较低	更高效

什么是蛮力？

在...方面 计算机科学, 蛮力是一种流行的寻找解决方案的技术。 Brute Force 方法保证了给定问题的解决方案，但它需要大量的运行时间并且效率低下。

它首先系统地枚举所有案例并检查它们是否满足条件。

如果我们以对数组元素进行排序为例，那么通过 Brute force 方法，我们将遍历数组很多次，直到获得所需的解决方案。 这将导致时间的浪费。

这就是为什么它被称为耗时的原因。

当数据集有限时使用 Brute Force 技术，因为如果我们对大量数据多次应用大量计算会导致很多复杂情况。 每当出现未知其适当解决方案的新问题时，蛮力技术就会用作基线方法。

蛮力解决现实世界问题的主要缺点是它增加了要检查的案例数量。 例如，如果我们想找到一个数的除数，假设它的除数是 16，那么蛮力将执行 10^15 次计算来找到解决方案。

什么是动态规划？

动态规划是解决数学和计算机科学问题的优化方法。 它由 Richard Bellman 在 1950 年代开发。

今天，由于其优化能力，它在各个领域都有应用。

它通过以递归方式将复杂问题分解为更简单的子问题来解决它。 然后递归地解决每个子问题。

要点是，如果一个子情况“a”在一个复杂问题中出现了 4 次，那么动态规划只会解决一次，而递归会解决 4 次。

这就是首选动态规划的原因。 就数学而言，动态规划是指通过将决策分解为子问题来简化决策。

在计算机科学的情况下，我们有两个重要的术语，我们应用动态规划，第一个是最优子结构，另一个是重叠子问题。

最优子结构是指通过组合所有子问题的优化解来获得优化问题的解。 重叠子问题意味着子问题的空间必须很小。

它也有缺点，就像每枚硬币都有两个面一样。 正如我们所知，它在解决子问题的同时存储了中间结果，这导致大量使用内存。

蛮力和动态规划之间的主要区别

1. 蛮力方法通过对数据集进行大量迭代来解决问题。 而动态规划只迭代一次并给出最优解。
2. Brute Force 提供的解决方案不能保证是最佳的，因为它提供了所有可能的解决方案。 而动态规划提供的解决方案将始终是最优的。
3. 蛮力方法通过一次考虑所有数据集来解决，而动态规划通过将给定问题分成几个子问题来解决问题。
4. 蛮力方法不使用最优子结构和重叠子问题的概念。 动态规划使用这些概念。
5. 蛮力方法不是最优和有效的。 它多次解决相同的计算，而 Dynamin 编程是最佳且高效的，因为它只解决一次计算并使用记忆。

参考资料

1. https://www.science.org/doi/abs/10.1126/science.153.3731.34
2. https://dl.acm.org/doi/fullHtml/10.1145/3107239

最后更新时间：14 年 2023 月 XNUMX 日