共计 2922 个字符，预计需要花费 8 分钟才能阅读完成。
作者：Aral Roca
翻译：疯狂的技术宅
原文：https://dev.to/christinamcmah…
未经容许严禁转载
首先明确三个概念：
算法： 按步骤解决问题的过程。
范式： 思考问题的模式。
算法范式： 为问题构建高效解决方案的惯例办法。
本文探讨一些罕用的算法范式，例如
- 分治算法
- 动静布局
- 贪心算法
- 回溯算法
分治法
在排序算法中，合并和疾速排序这两种算法的共同点就是分而治之的算法。
分而治之 是一种常见的算法设计，它的思路是把问题合成为与原始问题类似的较小子问题。通常以递归形式解决子问题，并联合子问题的解决方案来解决原始问题。
分治法的逻辑能够分为三个步骤：
- 将原始问题划分为较小的子问题。
- 通过递归解决子问题，解决结束之后返回子问题的解决方案。
- 将子问题的解决方案合并为原始问题的解决方案。
分治法的例子：二叉搜寻
上面是用分治实现的二叉搜寻。
function binarySearchRecursive(array, value, low, high) {if (low <= high) {const mid = Math.floor((low + high) / 2);
const element = array[mid];
if (element < value) {return binarySearchRecursive(array, value, mid + 1, high);
} else if (element > 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 < coins.length; i++) {const coin = coins[i];
newAmount = value - coin;
if (newAmount >= 0) {newMin = makeChange(newAmount);
}
if (newAmount >= 0 &&
(newMin.length < min.length - 1 || !min.length) && (newMin.length || !newAmount)) {min = [coin].concat(newMin);
}
}
return (cache[value] = min);
}
return makeChange(amount);
}在下面的代码中，参数 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 <= amount) {change.push(coin);
total += coin;
}
}
return change;
}能够看到，贪婪算法比动静布局的计划要简略得多。上面看一下同样的求解案例，来理解两者之间的区别：
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，直到找到适合的解决方案为止。
对于回溯算法，我会另写一篇文章来介绍更简单的算法。到底写什么我还没想好，兴许是写一个对数独求解的程序，如果你对这个感兴趣，请关注我的公众号！
算法是永无止境的，心愿本文能帮你理解一些常见的算法范式。
本文首发微信公众号：前端先锋
欢送扫描二维码关注公众号，每天都给你推送陈腐的前端技术文章
欢送持续浏览本专栏其它高赞文章：
- 深刻了解 Shadow DOM v1
- 一步步教你用 WebVR 实现虚拟现实游戏
- 13 个帮你进步开发效率的古代 CSS 框架
- 疾速上手 BootstrapVue
- JavaScript 引擎是如何工作的？从调用栈到 Promise 你须要晓得的所有
- WebSocket 实战：在 Node 和 React 之间进行实时通信
- 对于 Git 的 20 个面试题
- 深刻解析 Node.js 的 console.log
- Node.js 到底是什么？
- 30 分钟用 Node.js 构建一个 API 服务器
- Javascript 的对象拷贝
- 程序员 30 岁前月薪达不到 30K，该何去何从
- 14 个最好的 JavaScript 数据可视化库
- 8 个给前端的顶级 VS Code 扩大插件
- Node.js 多线程齐全指南
- 把 HTML 转成 PDF 的 4 个计划及实现
- 更多文章 …
