如何设计算法？下面本篇文章给大家分析一下常见的算法范式。有一定的参考价值，有需要的朋友可以参考一下，希望对大家有所帮助。
首先明确三个概念：
算法： 按步骤解决问题的过程。
范式： 思考问题的模式。
算法范式： 为问题构建高效解决方案的常规方法。
本文讨论一些常用的算法范式，例如
分治算法动态规划贪婪算法回溯算法
分治法
在排序算法中，合并和快速排序这两种算法的共同点就是分而治之的算法。
分而治之是一种常见的算法设计，它的思路是把问题分解为与原始问题相似的较小子问题。通常以递归方式解决子问题，并结合子问题的解决方案来解决原始问题。
分治法的逻辑可以分为三个步骤：
将原始问题划分为较小的子问题。通过递归解决子问题，解决完毕之后返回子问题的解决方案。将子问题的解决方案合并为原始问题的解决方案。
分治法的例子：二叉搜索
下面是用分治实现的二叉搜索。
function binarySearchRecursive(array, value, low, high) { if (low value) { return binarySearchRecursive(array, value, low, mid - 1); } else { return mid; } } return null;}export function binarySearch(array, value) { const sortedArray = quickSort(array); const low = 0; const high = sortedArray.length - 1; return binarySearchRecursive(array, value, low, high);}
登录后复制
请注意，上面的 binarySearch 函数是供他人调用的，而 binarySearchRecursive 是实现分治法的地方。
动态规划法
动态规划是一种优化技术，用于通过把复杂问题分解为较小的子问题来解决。看上去很像是分治法，但动态规划不是把问题分解为独立的子问题然后再组合在一起，而是只把问题分解为独立的子问题。
算法逻辑分为三个步骤：
定义子问题。重复解决子问题。识别并解决基本问题。
动态规划案例：最小硬币找零问题
这是一个名为为硬币找零问题的常见面试题。硬币找零问题是给定找零的金额，找出可以用多少特定数量的硬币来找零的方式。最小硬币找零问题只是找到使用给定面额的钱所需的最少硬币数量。例如，如果需要找零 3 毛 7 分，则可以使用 1 个 2 分，1个 5 分，1 个 1 毛钱和1个 2 毛钱。
function minCoinChange(coins, amount) { const cache = []; const makeChange = (value) => { if (!value) { return []; } if (cache[value]) { return cache[value]; } let min = []; let newMin; let newAmount; for (let i = 0; i = 0) { newMin = makeChange(newAmount); } if (newAmount >= 0 && (newMin.length 在上面的代码中，参数 coins 表示面额（在人民币中为 [1, 2, 5, 10, 20, 50]）。为了防止重复计算，用到了一个 cache 。 makeChange 函数是递归实现的，它是一个内部函数，可以访问 cache。
console.log(minCoinChange([1, 2, 5 10, 20], 37)); // => [2, 5, 10, 20]console.log(minCoinChange([1, 3, 4], 6)) // => [3, 3]
登录后复制
贪心算法
贪心算法与当前的最优解决方案相关，并试图找到一个全局的最佳方案。与动态规划不同，它不考虑全局。贪心算法倾向于简单直观，但可能不是整体最优的解决方案。
贪心算法案例：最小硬币找零问题
上面用动态规划解决的硬币问题也可以用贪心算法解决。这个解决方案的是否能得到最优解取决于所采用的面额。
function minCoinChange(coins, amount) { const change = []; let total = 0; for (let i = coins.length; i>= 0; i--) { const coin = coins[i]; while (total + coin 可以看到，贪心算法比动态规划的方案要简单得多。下面看一下同样的求解案例，来了解两者之间的区别：
console.log(minCoinChange([1, 2, 5 10, 20], 37)); // => [2, 5, 10, 20]console.log(minCoinChange([1, 3, 4], 6)) // => [4, 1, 1]
登录后复制
贪心算法给出了第一个问题的最优解，但第二个并不是最优解（应该是 [3，3]）。
贪心算法比动态规划算法要简单而且更快，但是得到的有可能不是最优解。
回溯算法
回溯算法非常适合逐步查找和构建解决方案。
尝试以一种方式解决问题。如果它不起作用，就回溯并重复步骤 1，直到找到合适的解决方案为止。
对于回溯算法，我会另写一篇文章来介绍更复杂的算法。究竟写什么我还没想好，也许是写一个对数独求解的程序，如果你对这个感兴趣，请关注我的公众号！
算法是永无止境的，希望本文能帮你了解一些常见的算法范式。
相关免费学习推荐：js视频教程
以上就是如何设计算法？常见的算法范式介绍的详细内容，更多请关注【创想鸟】其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至253000106@qq.com举报，一经查实，本站将立刻删除。
发布者：PHP中文网，转转请注明出处：https://www.chuangxiangniao.com/p/2725126.html
