资讯专栏INFORMATION COLUMN

算法系列——算法入门之递归分而治之思想的实现

goji / 1580人阅读

摘要:简单算法之递归我向算法工程师请教如何学好算法,他跟我提议说先看懂汉诺塔,这是一个小朋友都会玩的游戏,里面用到了递归的思想。递归实现倒计时函数下面这个倒计时函数使用了递归,而且使用了尾递归优化。

前端需要算法吗?

别想太多,肯定要!!!

什么是算法

你以为的算法是各种排序,选择排序、快速排序、归并排序,广深搜索、动态规划......

然而,算法实际上指的是解决某个实际问题的方法。

解决同一个问题的方法有很多,比如循环输出某个数组,可以有for、for in、for of、map、forEach等,不同的实现方法会反映不同的性能,这些性能通常用执行时间来表示,执行时间越短,性能越好,目前我可以告诉你的是,上面的几个循环中,原生for循环的性能是最好的。

下面讲的都是非常非常非常非常简单的算法知识!!你千万不要害怕!!

数组和链表 数组

数组是算法中最常用到的数据结构,给你一串数组,你能很快的根据索引找到那个元素。

你或许知道时间复杂度O(n),我们叫他大O表示法,这是大写字母O,不是数字0,别搞错了。通常大O表示的是算法的最差情况。

数组 O(时间复杂度)
读取 O(1)
写入 O(n)
删除 O(n)

数组的大O很好理解,读取的时候,最坏情况就是1次,因为数组是内存上连续的地址(计算机的知识),可以直接根据地址(索引)找到那个元素。

写入的时候,如果是在数组的末尾push新的元素,那么前面已有的元素地址不需要改变,但是如果是在数组的头部push新的元素,那么所有已有的元素的地址都要加1,即需要移动n个元素,所以大O是n。

删除操作时,和插入一样,最好的情况是删除末尾的元素,复杂度就是1,最坏的情况是删除第一个元素,所有剩下的元素都需要地址减1,即需要移动n次。

或许你会发现上面有点不对劲,在删除的时候,不是移动 n-1 个元素吗?其实这就是要知道的大O表示法只是描述次数和数据量的线性关系,我们关注的是线性变化的规律,不在乎那一点点影响。

链表

链表比较复杂,我们这里只关心链表的一些特点。

链表和数组一样,通常也存在内存中,链表可以存在内存的任何地方,它不一定是连续的。这句话你可能不太理解。举个例子,假设你有的内存条有8G,这8G可能被分配给多个应用程序,你创建了一个数组,长度是10,那么,系统会分配10个连续的内存地址给你使用。而链表呢,假设你有10个数据,可以通过链表插入到内存的空余地址位置,中间可能被其他数据隔开。类似于插班生来到了你们班,插入了任意一个空位里面。

链表还有一个重要的特性就是他的读取必须是从头开始遍历,因为只有当前的元素位置才有下一个元素的指针!!你不能直接读取第N个元素!

链表 O(时间复杂度)
读取 O(n)
写入 O(1)
删除 O(1)

你会发现链表的读取大O是n,也就是说最坏的情况下,如果那个需要读取的元素刚好在链表的最末尾,那么,你就需要遍历整个链表。

写入和删除都是O(1),这和链表的特点有关,你可以在任意一个指针写入新的元素和删除链表的元素,而只需要将前一个元素的指针指向新的元素或者下一个元素即可。链表没有地址的概念,所以不需要移动地址。

形象表达内存中数组和链表的特点

上面的文字你觉得抽象的话,可以看下面的表格,假设这一段内存条,上面一共有8个内存地址,现在都是空余的,当你创建一个长度为2的数组时 new Array(2),系统会分配2个内存地址给数组,可能是地址0,1。然后继续创建一个长度为1的数组 new Array(1),系统会分配1个内存地址给数组,假设是地址4,现在整个内存被2个数组给分割开来了,单个数组的内存一定是连续的,不同的数组之间不需要连续。

这时候,你再创建一个链表,有3个元素,现在地址2、3、5、6、7都是空闲的,假设链表的第一个元素是2,那么下一个元素可以指向任意一个空闲的地址,比如3,到地址3的时候,地址4已经有数组的元素在占用了,不用担心,链表可以将指针指向地址5,这样链表的第三个元素就存储在地址5上面了。

这样你是不是更加清晰的理解了数组和链表的基本特点了。

0 1
2 3
4 5
6 7
组合型数据结构

数组和链表也可以组合起来成为一种复合型的数据结构,称为“链组结构”,不是恋父、不是恋母,而是链组!

作为前端,实际上只需要考虑和数组相关的基本算法就行了,还有就是各种性能提升的诀窍。

简单算法之递归

我向算法工程师请教如何学好算法,他跟我提议说先看懂汉诺塔,这是一个小朋友都会玩的游戏,里面用到了递归的思想。但是我在这里不说汉诺塔,而是从递归的简单实现入手。

以前我也写过递归的文章,ES6中也有尾递归优化的介绍。但递归的思想不只是应用在阶乘算法中,还有各种场景需要递归,特别是在函数式编程中,递归的地位显得越发的重要。

递归实现倒计时函数

下面这个倒计时函数使用了递归,而且使用了尾递归优化。你或许不了解尾递归优化,我想你可以去看一下 尾递归优化特点

function countdown(i) {
  if (i <= 0) return
  console.log(i)
  setTimeout(() => {
    return countdown(i-1)
  }, 1000)
}
countdown(10)
递归实现阶乘

阶乘是什么?n!表示 1X2X3X...Xn

function t(i, s=1) {
  if (i <= 0) return s
  s *= i
  return t(i - 1, s)
}
const s = t(5)
console.log(s)
递归之分而治之思想实现数组元素求和

需求是这样的,假设你有一个数字组成的数组,现在你需要写一个函数求所有元素的和,比如[2, 4, 6]。

这里不单单是递归的思想,还有一种思想叫做分而治之,分而治之的思想分为2个步骤,一是找出基线条件。二是每次调用递归都离基线条件更近一步。

那么数组[2, 4, 6]的基线条件是什么呢?其实它就是一个临界情况,比如当数组元素为空时[],或者数组只剩一个元素时[2]。这个基线有什么作用呢?当递归达到基线时,就返回结果,不再递归。

下面的代码实际上是根据这样一个步骤去执行的,[2, 4] + 6 => [2] + 4 + 6 => 2 + 4 + 6,通过数组不断的拆分和求和,直至数组达到基线条件,这时候将相加的和返回。

未尾递归优化

function add_1(arr, len=arr.length, sum=arr[len-1]) {
 if(len <= 1) return sum
 return sum + add_1(arr.slice(0, len - 1))
}

const r = add_1([2, 4, 6])
console.log(r) // 12

尾递归优化

function add_2(arr, len=arr.length, sum=arr[len-1]) {
 if(len <= 1) return sum
 len = arr.slice(0, len - 1).length
 sum += arr[len - 1]
 return add_2(arr.slice(0, len - 1), len, sum)
}

const p = add_2([2, 4, 6])
console.log(p) //12
总结

学习算法是一个漫长的过程,第一次学网页设计的时候,div都学习了大半年才搞懂什么玩意,后来CSS的学习时间更长,js的学习从开始到现在始终在进行着,正则的学习一开始也是很痛苦,最后,轮到了算法,只有像以前学习前端知识那样坚持下去,才能学好算法!!

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/60276.html

相关文章

  • 算法系列——算法入门递归而治思想实现

    摘要:简单算法之递归我向算法工程师请教如何学好算法,他跟我提议说先看懂汉诺塔,这是一个小朋友都会玩的游戏,里面用到了递归的思想。递归实现倒计时函数下面这个倒计时函数使用了递归,而且使用了尾递归优化。 前端需要算法吗? 别想太多,肯定要!!! 什么是算法 你以为的算法是各种排序,选择排序、快速排序、归并排序,广深搜索、动态规划...... 然而,算法实际上指的是解决某个实际问题的方法。 解决同...

    or0fun 评论0 收藏0
  • 算法系列——JavaScript快速排序思想实现

    摘要:源码实现快速排序理论理解起来很容易,但经常是实际写代码,无从下手,下面是我根据快排的步骤实现的递归快速排序。合并第一次快速排序的,,数组。 原理 快速排序离不开递归的思想,你如果不了解递归,可以结合我另外一篇文章来学习 算法入门之递归分而治之思想的实现 网上有有趣的动态图来表示快速排序,但其实我们大部分程序员都是脑子不太好使那种,即使看了形象生动的动态图,还是想不到具体实现思路。 排序...

    lentrue 评论0 收藏0
  • 算法系列——JavaScript快速排序思想实现

    摘要:源码实现快速排序理论理解起来很容易,但经常是实际写代码,无从下手,下面是我根据快排的步骤实现的递归快速排序。合并第一次快速排序的,,数组。 原理 快速排序离不开递归的思想,你如果不了解递归,可以结合我另外一篇文章来学习 算法入门之递归分而治之思想的实现 网上有有趣的动态图来表示快速排序,但其实我们大部分程序员都是脑子不太好使那种,即使看了形象生动的动态图,还是想不到具体实现思路。 排序...

    null1145 评论0 收藏0
  • js算法入门(3)--递归

    摘要:在递归过程中,未完成计算的函数将会挂起压入调用堆栈,不然递归结束的时候没办法进行回溯。这就引出了回溯法回溯法就是在达到递归边界前的某层,由于一些事实导致已经不需要前往任何一个子问题递归,就可以直接返回上一层。 1简介 递归在前端开发中应用还是非常广泛的,首先DOM就是树状结构,而这种结构使用递归去遍历是非常合适的。然后就是对象和数组的深复制很多库也是使用递归实现的例如jquery中的e...

    jzman 评论0 收藏0
  • JavaScript算法 ,Python算法,Go算法,java算法,系列归并排序

    摘要:常见的内部排序算法有插入排序希尔排序选择排序冒泡排序归并排序快速排序堆排序基数排序等。用一张图概括归并排序英语,或,是创建在归并操作上的一种有效的排序算法,效率为。 常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括: showImg(https://segmentfault.com/img/bVNwuO?w=966&h=...

    zhou_you 评论0 收藏0

发表评论

0条评论

goji

|高级讲师

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<