95% 的算法都是基于这 6 种算法思想

7,839 阅读11分钟

算法思想是解决问题的核心,万丈高楼起于平地,在算法中也是如此,95% 的算法都是基于这 6 种算法思想,结下了介绍一下这 6 种算法思想,帮助你理解及解决各种算法问题。

1、递归算法

1.1 算法策略

递归算法是一种直接或者间接调用自身函数或者方法的算法。

递归算法的实质是把问题分解成规模缩小的同类问题的子问题,然后递归调用方法来表示问题的解。递归算法对解决一大类问题很有效,它可以使算法简洁和易于理解。

优缺点:

  • 优点:实现简单易上手
  • 缺点:递归算法对常用的算法如普通循环等,运行效率较低;并且在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储,递归太深,容易发生栈溢出。

1.2 适用场景

递归算法一般用于解决三类问题:

  • 数据的定义是按递归定义的。(斐波那契数列)
  • 问题解法按递归算法实现。(回溯)
  • 数据的结构形式是按递归定义的。(树的遍历,图的搜索)

递归的解题策略:

  • 第一步:明确你这个函数的输入输出,先不管函数里面的代码什么,而是要先明白,你这个函数的输入是什么,输出为何什么,功能是什么,要完成什么样的一件事。
  • 第二步:寻找递归结束条件,我们需要找出什么时候递归结束,之后直接把结果返回
  • 第三步:明确递归关系式,怎么通过各种递归调用来组合解决当前问题

1.3 使用递归算法求解的一些经典问题

  • 斐波那契数列
  • 汉诺塔问题
  • 树的遍历及相关操作

DOM树为例

下面以以 DOM 🌲为例,实现一个 document.getElementById 功能

由于DOM是一棵树,而树的定义本身就是用的递归定义,所以用递归的方法处理树,会非常地简单自然。

第一步:明确你这个函数的输入输出

从 DOM 🌲根节点一层层往下递归,判断当前节点的 id 是否是我们要寻找的 id='d-cal'

输入:DOM 🌲根节点 document ,我们要寻找的 id='d-cal'

输出:返回满足 id='sisteran' 的子结点

function getElementById(node, id){}

第二步:寻找递归结束条件

从document开始往下找,对所有子结点递归查找他们的子结点,一层一层地往下查找:

  • 如果当前结点的 id 符合查找条件,则返回当前结点
  • 如果已经到了叶子结点了还没有找到,则返回 null
function getElementById(node, id){
    // 当前结点不存在,已经到了叶子结点了还没有找到,返回 null
    if(!node) return null
    // 当前结点的 id 符合查找条件,返回当前结点
    if(node.id === id) return node
}

第三步:明确递归关系式

当前结点的 id 不符合查找条件,递归查找它的每一个子结点

function getElementById(node, id){
    // 当前结点不存在,已经到了叶子结点了还没有找到,返回 null
    if(!node) return null
    // 当前结点的 id 符合查找条件,返回当前结点
    if(node.id === id) return node
    // 前结点的 id 不符合查找条件,继续查找它的每一个子结点
    for(var i = 0; i < node.childNodes.length; i++){
        // 递归查找它的每一个子结点
        var found = getElementById(node.childNodes[i], id);
        if(found) return found;
    }
    return null;
}

就这样,我们的一个 document.getElementById 功能已经实现了:

function getElementById(node, id){
    if(!node) return null;
    if(node.id === id) return node;
    for(var i = 0; i < node.childNodes.length; i++){
        var found = getElementById(node.childNodes[i], id);
        if(found) return found;
    }
    return null;
}
getElementById(document"d-cal");

使用递归的优点是代码简单易懂,缺点是效率比不上非递归的实现。Chrome浏览器的查DOM是使用非递归实现。非递归要怎么实现呢?如下代码:

function getByElementId(node, id){
    //遍历所有的Node
    while(node){
        if(node.id === id) return node;
        node = nextElement(node);
    }
    return null;
}

还是依次遍历所有的 DOM 结点,只是这一次改成一个 while 循环,函数 nextElement 负责找到下一个结点。所以关键在于这个 nextElement 如何实现非递归查找结点功能:

// 深度遍历
function nextElement(node){
    // 先判断是否有子结点
    if(node.children.length) {
        // 有则返回第一个子结点
        return node.children[0];
    }
    // 再判断是否有相邻结点
    if(node.nextElementSibling){
        // 有则返回它的下一个相邻结点
        return node.nextElementSibling;
    }
    // 否则,往上返回它的父结点的下一个相邻元素,相当于上面递归实现里面的for循环的i加1
    while(node.parentNode){
        if(node.parentNode.nextElementSibling) {
            return node.parentNode.nextElementSibling;
        }
        node = node.parentNode;
    }
    return null;
}

在控制台里面运行这段代码,同样也可以正确地输出结果。不管是非递归还是递归,它们都是深度优先遍历。 实际上 getElementById 浏览器是用的一个哈希 map 存储的,根据 id 直接映射到 DOM 结点,而 getElementsByClassName 就是用的这样的非递归查找。

2 分治算法

2.1 算法策略

在计算机科学中,分治算法是一个很重要的算法,快速排序、归并排序等都是基于分治策略进行实现的,所以,建议理解掌握它。

分治,顾名思义,就是 分而治之 ,将一个复杂的问题,分成两个或多个相似的子问题,在把子问题分成更小的子问题,直到更小的子问题可以简单求解,求解子问题,则原问题的解则为阿子问题解的合并。

2.2 适用场景

当出现满足以下条件的问题,可以尝试只用分治策略进行求解:

  • 原始问题可以分成多个相似的子问题
  • 子问题可以很简单的求解
  • 原始问题的解是子问题解的合并
  • 各个子问题是相互独立的,不包含相同的子问题

分治的解题策略:

  • 第一步:分解,将原问题分解为若干个规模较小,相互独立,与原问题形式相同的子问题
  • 第二步:解决,解决各个子问题
  • 第三步:合并,将各个子问题的解合并为原问题的解

2.3 使用分治法求解的一些经典问题

  • 二分查找
  • 归并排序
  • 快速排序
  • 汉诺塔问题
  • React 时间分片

二分查找

也称折半查找算法,它是一种简单易懂的快速查找算法。例如我随机写0-100之间的一个数字,让你猜我写的是什么?你每猜一次,我就会告诉你猜的大了还是小了,直到猜中为止。

第一步:分解

每次猜拳都把上一次的结果分出大的一组和小的一组,两组相互独立

  • 选择数组中的中间数
function binarySearch(items, item) {
    // low、mid、high将数组分成两组
    var low = 0,
        high = items.length - 1,
        mid = Math.floor((low+high)/2),
        elem = items[mid]
    // ...
}

第二步:解决子问题

查找数与中间数对比

  • 比中间数低,则去中间数左边的子数组中寻找;
  • 比中间数高,则去中间数右边的子数组中寻找;
  • 相等则返回查找成功
while(low <= high) {
 if(elem < item) { // 比中间数高
  low = mid + 1
 } else if(elem > item) { // 比中间数低
  high = mid - 1
 } else { // 相等
     return mid
 }
}

第三步:合并

function binarySearch(items, item) {
    var low = 0,
        high = items.length - 1,
        mid, elem
    while(low <= high) {
        mid = Math.floor((low+high)/2)
        elem = items[mid]
        if(elem < item) {
            low = mid + 1
        } else if(elem > item) {
            high = mid - 1
        } else {
            return mid
        }
    }
    return -1
}

最后,二分法只能应用于数组有序的情况,如果数组无序,二分查找就不能起作用了

function binarySearch(items, item) {
    // 快排
    quickSort(items)
    var low = 0,
        high = items.length - 1,
        mid, elem
    while(low <= high) {
        mid = Math.floor((low+high)/2)
        elem = items[mid]
        if(elem < item) {
            low = mid + 1
        } else if(elem > item) {
            high = mid - 1
        } else {
            return mid
        }
    }
    return -1
}

// 测试
var arr = [2,3,1,4]
binarySearch(arr, 3)
// 2

binarySearch(arr, 5)
// -1

3 贪心算法

3.1 算法策略

贪心算法,故名思义,总是做出当前的最优选择,即期望通过局部的最优选择获得整体的最优选择。

某种意义上说,贪心算法是很贪婪、很目光短浅的,它不从整体考虑,仅仅只关注当前的最大利益,所以说它做出的选择仅仅是某种意义上的局部最优,但是贪心算法在很多问题上还是能够拿到最优解或较优解,所以它的存在还是有意义的。

3.2 适用场景

在日常生活中,我们使用到贪心算法的时候还是挺多的,例如:

从100章面值不等的钞票中,抽出 10 张,怎样才能获得最多的价值?

我们只需要每次都选择剩下的钞票中最大的面值,最后一定拿到的就是最优解,这就是使用的贪心算法,并且最后得到了整体最优解。

但是,我们任然需要明确的是,期望通过局部的最优选择获得整体的最优选择,仅仅是期望而已,也可能最终得到的结果并不一定不能是整体最优解。

那么一般在什么时候可以尝试选择使用贪心算法喃?

当满足一下条件时,可以使用:

  • 原问题复杂度过高
  • 求全局最优解的数学模型难以建立或计算量过大
  • 没有太大必要一定要求出全局最优解,“比较优”就可以

如果使用贪心算法求最优解,可以按照以下 步骤求解 :

  • 首先,我们需要明确什么是最优解(期望)
  • 然后,把问题分成多个步骤,每一步都需要满足:
  • 可行性:每一步都满足问题的约束
  • 局部最优:每一步都做出一个局部最优的选择
  • 不可取消:选择一旦做出,在后面遇到任何情况都不可取消
  • 最后,叠加所有步骤的最优解,就是全局最优解

3.3 经典案例:活动选择问题

使用贪心算法求解的经典问题有:

  • 最小生成树算法
  • 单源最短路径的 Dijkstra 算法
  • Huffman 压缩编码
  • 背包问题
  • 活动选择问题等

4 回溯算法

4.1 算法策略

回溯算法是一种搜索法,试探法,它会在每一步做出选择,一旦发现这个选择无法得到期望结果,就回溯回去,重新做出选择。深度优先搜索利用的就是回溯算法思想。

4.2 适用场景

回溯算法很简单,它就是不断的尝试,直到拿到解。它的这种算法思想,使它通常用于解决广度的搜索问题,即从一组可能的解中,选择一个满足要求的解。

4.3 使用回溯算法的经典案例

  • 深度优先搜索
  • 0-1背包问题
  • 正则表达式匹配
  • 八皇后
  • 数独
  • 全排列

等等,深度优先搜索我们在图那一章已经介绍过,这里以正则表达式匹配为例,介绍一下

正则表达式匹配

var string = "abbc"

var regex = /ab{1,3}c/

console.log( string.match(regex) )

// ["abbc", index: 0, input: "abbc", groups: undefined]

它的匹配过程: image.png

在第 5 步匹配失败,此时 b{1,3} 已经匹配到了两个 b 正在尝试第三个 b ,结果发现接下来是 c 。此时就需要回溯到上一步, b{1,3} 匹配完毕(匹配到了 bb ),然后再匹配 c ,匹配到了 c 匹配结束。

5 动态规划

5.1 算法策略

动态规划也是将复杂问题分解成小问题求解的策略,与分治算法不同的是,分治算法要求各子问题是相互独立的,而动态规划各子问题是相互关联的。

所以,动态规划适用于子问题重叠的情况,即不同的子问题具有公共的子子问题,在这种情况下,分治策略会做出很多不必要的工作,它会反复求解那些公共子子问题,而动态规划会对每个子子问题求解一次,然后保存在表格中,如果遇到一致的问题,从表格中获取既可,所以它无需求解每一个子子问题,避免了大量的不必要操作。

5.2 适用场景

动态规划适用于求解最优解问题,比如,从面额不定的100个硬币中任意选取多个凑成10元,求怎样选取硬币才可以使最后选取的硬币数最少又刚好凑够了10元。这就是一个典型的动态规划问题。它可以分成一个个子问题(每次选取硬币),每个子问题又有公共的子子问题(选取硬币),子问题之间相互关联(已选取的硬币总金额不能超过10元),边界条件就是最终选取的硬币总金额为 10 元。

针对上例,也许你也可以说,我们可以使用回溯算法,不断的去试探,但回溯算法是使用与求解广度的解(满足要求的解),如果是用回溯算法,我们需要尝试去找所有满足条件的解,然后找到最优解,时间复杂度为 O(2^n^) ,这性能是相当差的。大多数适用于动态规划的问题,都可以使用回溯算法,只是使用回溯算法的时间复杂度比较高而已。

最后,总结一下,我们使用动态规划求解问题时,需要遵循以下几个重要步骤:

  • 定义子问题
  • 实现需要反复执行解决的子子问题部分
  • 识别并求解出边界条件

5.3 使用动态规划求解的一些经典问题

  • 爬楼梯问题:假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?
  • 背包问题:给出一些资源(有总量及价值),给一个背包(有总容量),往背包里装资源,目标是在背包不超过总容量的情况下,装入更多的价值
  • 硬币找零:给出面额不定的一定数量的零钱,以及需要找零的钱数,找出有多少种找零方案
  • 图的全源最短路径:一个图中包含 u、v 顶点,找出从顶点 u 到顶点 v 的最短路径
  • 最长公共子序列:找出一组序列的最长公共子序列(可由另一序列删除元素但不改变剩下元素的顺序实现)

这里以最长公共子序列为例。

爬楼梯问题

这里以动态规划经典问题爬楼梯问题为例,介绍求解动态规划问题的步骤。

第一步:定义子问题

如果用 dp[n] 表示第 n 级台阶的方案数,并且由题目知:最后一步可能迈 2 个台阶,也可迈 1 个台阶,即第 n 级台阶的方案数等于第 n-1 级台阶的方案数加上第 n-2 级台阶的方案数

第二步:实现需要反复执行解决的子子问题部分

dp[n] = dp[n−1] + dp[n−2]

第三步:识别并求解出边界条件

// 第 0 级 1 种方案 
dp[0]=1 
// 第 1 级也是 1 种方案 
dp[1]=1

最后一步:把尾码翻译成代码,处理一些边界情况

let climbStairs = function(n) {
    let dp = [11]
    for(let i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2]
    }
    return dp[n]
}

复杂度分析:

  • 时间复杂度:O(n)
  • 空间复杂度:O(n)

优化空间复杂度:

let climbStairs = function(n) {
    let res = 1, n1 = 1, n2 = 1
    for(let i = 2; i <= n; i++) {
        res = n1 + n2
        n1 = n2
        n2 = res
    }
    return res
}

空间复杂度:O(1)

6 枚举算法

6.1 算法策略

枚举算法的思想是:将问题的所有可能的答案一一列举,然后根据条件判断此答案是否合适,保留合适的,丢弃不合适的。

6.2 解题思路

  • 确定枚举对象、枚举范围和判定条件。
  • 逐一列举可能的解,验证每个解是否是问题的解。

总结

算法是编程的"里子",不管你是前端还是后端,作为一名计算机工程师,具备一定的算法能力,是一种基本要求。