作者：Aral Roca

翻译：疯狂的技术宅

原文：https://dev.to/christinamcmah...

未经容许严禁转载

首先明确三个概念：

算法： 按步骤解决问题的过程。

范式： 思考问题的模式。

算法范式： 为问题构建高效解决方案的惯例办法。

本文探讨一些罕用的算法范式，例如

  • 分治算法
  • 动静布局
  • 贪心算法
  • 回溯算法

分治法

在排序算法中，合并和疾速排序这两种算法的共同点就是分而治之的算法。

分而治之是一种常见的算法设计，它的思路是把问题合成为与原始问题类似的较小子问题。通常以递归形式解决子问题，并联合子问题的解决方案来解决原始问题。

分治法的逻辑能够分为三个步骤：

  1. 将原始问题划分为较小的子问题。
  2. 通过递归解决子问题，解决结束之后返回子问题的解决方案。
  3. 将子问题的解决方案合并为原始问题的解决方案。

分治法的例子：二叉搜寻

上面是用分治实现的二叉搜寻。

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 是实现分治法的中央。

动静规划法

动静布局是一种优化技术，用于通过把简单问题合成为较小的子问题来解决。看上去很像是分治法，但动静布局不是把问题合成为独立的子问题而后再组合在一起，而是只把问题合成为独立的子问题。

算法逻辑分为三个步骤：

  1. 定义子问题。
  2. 反复解决子问题。
  3. 辨认并解决根本问题。

动静布局案例：最小硬币找零问题

这是一个名为为硬币找零问题的常见面试题。硬币找零问题是给定找零的金额，找出能够用多少特定数量的硬币来找零的形式。最小硬币找零问题只是找到应用给定面额的钱所需的起码硬币数量。例如，如果须要找零 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. 尝试以一种形式解决问题。
  2. 如果它不起作用，就回溯并反复步骤 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个计划及实现
  • 更多文章...