关于前端:浅析常见的算法范式

作者：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 个计划及实现

• 更多文章 …