当前位置: 首页 > news >正文

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

前端需要算法吗?

别想太多,肯定要!!!

什么是算法

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

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

解决同一个问题的方法有很多,比如循环输出某个数组,可以有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上面了。

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

01
23
45
67

组合型数据结构

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

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

简单算法之递归

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

以前我也写过递归的文章,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的学习从开始到现在始终在进行着,正则的学习一开始也是很痛苦,最后,轮到了算法,只有像以前学习前端知识那样坚持下去,才能学好算法!!

相关文章:

  • 建立名称server
  • Hyper-V Server增强会话模式
  • 《Javascript高级程序设计 (第三版)》第五章 引用类型
  • Spring AOP 1
  • 如何启动Nunit的调试功能
  • ELK日志分析系统实战(一)安装和部署
  • H3C路由器登录管理
  • Laravel5.1 条件性验证
  • Redhat7 增加swap分区
  • 进程调度器--UNIX还是是老大
  • 监控apache脚本原理
  • JAVA与.NET的相互调用——利用JNBridge桥接模式实现远程通讯
  • 13.liunx机器互相登录
  • nginx配置虚拟主机
  • mysql日志文件在哪
  • ES6系统学习----从Apollo Client看解构赋值
  • extract-text-webpack-plugin用法
  • Javascript基础之Array数组API
  • Java教程_软件开发基础
  • Js基础知识(一) - 变量
  • js继承的实现方法
  • JS题目及答案整理
  • miaov-React 最佳入门
  • MySQL QA
  • Redis学习笔记 - pipline(流水线、管道)
  • thinkphp5.1 easywechat4 微信第三方开放平台
  • WordPress 获取当前文章下的所有附件/获取指定ID文章的附件(图片、文件、视频)...
  • 编写符合Python风格的对象
  • 从setTimeout-setInterval看JS线程
  • 技术:超级实用的电脑小技巧
  • 理解 C# 泛型接口中的协变与逆变(抗变)
  • 聊一聊前端的监控
  • 让你的分享飞起来——极光推出社会化分享组件
  • 什么软件可以提取视频中的音频制作成手机铃声
  • ​iOS实时查看App运行日志
  • ​LeetCode解法汇总1276. 不浪费原料的汉堡制作方案
  • ​一些不规范的GTID使用场景
  • # include “ “ 和 # include < >两者的区别
  • #【QT 5 调试软件后,发布相关:软件生成exe文件 + 文件打包】
  • #etcd#安装时出错
  • ${factoryList }后面有空格不影响
  • (Matalb分类预测)GA-BP遗传算法优化BP神经网络的多维分类预测
  • (保姆级教程)Mysql中索引、触发器、存储过程、存储函数的概念、作用,以及如何使用索引、存储过程,代码操作演示
  • (提供数据集下载)基于大语言模型LangChain与ChatGLM3-6B本地知识库调优:数据集优化、参数调整、Prompt提示词优化实战
  • (转)ORM
  • .Net CF下精确的计时器
  • .Net+SQL Server企业应用性能优化笔记4——精确查找瓶颈
  • .Net8 Blazor 尝鲜
  • .Net的C#语言取月份数值对应的MonthName值
  • .NET上SQLite的连接
  • /proc/stat文件详解(翻译)
  • @kafkalistener消费不到消息_消息队列对战之RabbitMq 大战 kafka
  • [ vulhub漏洞复现篇 ] Celery <4.0 Redis未授权访问+Pickle反序列化利用
  • [20190401]关于semtimedop函数调用.txt
  • [AIGC] MySQL存储引擎详解