You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
通常采用 大 O 表示法 来表示复杂度。它并不代表真正的执行时间或存储空间消耗,而是表示代码执行时间随数据规模增长的变化趋势(时间复杂度)或存储空间随数据规模增长的变化趋势(空间复杂度),所以,也叫作渐进时间(或空间)复杂度(asymptotic time complexity),简称时间(或空间)复杂度。
每次循环 i 都乘以 2 ,直至 i > n ,即执行过程是:20、21、22、…、2k、…、2x、 n 所以总执行次数 x ,可以写成 2x = n ,则时间复杂度为 O(log2n) 。这里是 2 ,也可以是其他常量 k ,时间复杂度也是: O(log3n) = O(log32 * log2n) = O(log2n)
引言
本篇素材来自于瓶子君前端进阶算法集训营,每天一道算法题或文章,现已更新半月:
以及题目:
本节是前端进阶算法集训营半月的总结与回顾👇
一、前端进阶算法 1:如何分析、统计算法的执行效率和资源消耗?
好的数据结构与算法能够大大缩短代码的执行时间与存储空间,那么我们如何去衡量它喃?这节就主要介绍算法性能的衡量指标—复杂度分析。
复杂度可分为:
1. 如何表示算法复杂度?
通常采用 大 O 表示法 来表示复杂度。它并不代表真正的执行时间或存储空间消耗,而是表示代码执行时间随数据规模增长的变化趋势(时间复杂度)或存储空间随数据规模增长的变化趋势(空间复杂度),所以,也叫作渐进时间(或空间)复杂度(asymptotic time complexity),简称时间(或空间)复杂度。
2. 常见复杂度
多项式量级:
常量阶: O(1):当算法中不存在循环语句、递归语句,即使有成千上万行的代码,其时间复杂度也是Ο(1)
对数阶:O(logn): 简单介绍一下
let i=1;
while (i <= n) {
i = i * 2;
}
复制代码
每次循环
i
都乘以2
,直至i > n
,即执行过程是:20、21、22、…、2k、…、2x、 n 所以总执行次数 x ,可以写成 2x = n ,则时间复杂度为 O(log2n) 。这里是2
,也可以是其他常量k
,时间复杂度也是: O(log3n) = O(log32 * log2n) = O(log2n)线性阶:O(n)
线性对数阶:O(nlogn)
平方阶、立方阶、….、k 次方阶:O(n2)、O(n3)、…、O(nk)
非多项式量阶:
3. 复杂度的划分
以时间复杂度为例,时间复杂度受数据本身影响,还分为:
详情:前端进阶算法 1:如何分析、统计算法的执行效率和资源消耗?
二、前端进阶算法 2:从 Chrome V8 源码看 JavaScript 数组(附赠腾讯面试题)
1. JavaScript 中,数组的应用
它的这种特定的存储结构决定了:
优点
缺点
查找: 根据下标随机访问的时间复杂度为 O(1);
插入或删除: 时间复杂度为 O(n);
在 JavaScript 中的数组几乎是万能的,它不光可以作为一个普通的数组使用,可以作为栈或队列使用。
数组:
栈:
队列:
2. JavaScript 中,数组的独特之处
JavaScript 中,
JSArray
继承自JSObject
,或者说它就是一个特殊的对象,内部是以 key-value 形式存储数据,所以 JavaScript 中的数组可以存放不同类型的值。它有两种存储方式,快数组与慢数组,初始化空数组时,使用快数组,快数组使用连续的内存空间,当数组长度达到最大时,JSArray
会进行动态的扩容,以存储更多的元素,相对慢数组,性能要好得多。当数组中hole
太多时,会转变成慢数组,即以哈希表的方式( key-value 的形式)存储数据,以节省内存空间。具体快慢数组、动态扩容前往:前端进阶算法 2:从 Chrome V8 源码看 JavaScript 数组(附赠腾讯面试题)
三、前端进阶算法 3:从浏览器缓存淘汰策略和 Vue 的 keep-alive 学习 LRU 算法
1. 浏览器缓存淘汰策略
当我们打开一个网页时,例如
https://github.com/sisterAn/JavaScript-Algorithms
,它会在发起真正的网络请求前,查询浏览器缓存,看是否有要请求的文件,如果有,浏览器将会拦截请求,返回缓存文件,并直接结束请求,不会再去服务器上下载。如果不存在,才会去服务器请求。其实,浏览器中的缓存是一种在本地保存资源副本,它的大小是有限的,当我们请求数过多时,缓存空间会被用满,此时,继续进行网络请求就需要确定缓存中哪些数据被保留,哪些数据被移除,这就是浏览器缓存淘汰策略,最常见的淘汰策略有 FIFO(先进先出)、LFU(最少使用)、LRU(最近最少使用)。
LRU (
Least Recently Used
:最近最少使用 )缓存淘汰策略,故名思义,就是根据数据的历史访问记录来进行淘汰数据,其核心思想是 如果数据最近被访问过,那么将来被访问的几率也更高 ,优先淘汰最近没有被访问到的数据。画个图帮助我们理解 LRU:
2. Vue 的 keep-alive 源码解读
在
keep-alive
缓存超过max
时,使用的缓存淘汰算法就是 LRU 算法,它在实现的过程中用到了cache
对象用于保存缓存的组件实例及key
值,keys
数组用于保存缓存组件的key
,当keep-alive
中渲染一个需要缓存的实例时:key
在keys
中的位置(移除keys
中key
,并放入keys
数组的最后一位)keys
的长度大于max
(缓存长度超过上限),则移除keys[0]
缓存主要实现 LRU 代码:
源码详情:前端进阶算法 3:从浏览器缓存淘汰策略和 Vue 的 keep-alive 学习 LRU 算法
四、前端进阶算法 4:链表原来如此简单(+leetcode 刷题)
1. 图解链表
常用的链表类型有单链表、双链表以及循环链表,其中
next
为后继指针,指向它的后继节点,prev
为前驱指针,指向它的前驱节点。单链表
双链表
循环链表
2. 链表复杂度一览表
单链表
双链表
循环链表
详情:前端进阶算法 4:链表原来如此简单(+leetcode 刷题)
五、图解 leetcode88:合并两个有序数组
1. 题目
给你两个有序整数数组
nums1
和nums2
,请你将nums2
合并到nums1
中,使num1
成为一个有序数组。说明:
初始化
nums1
和nums2
的元素数量分别为m
和n
。 你可以假设nums1
有足够的空间(空间大小大于或等于m + n
)来保存nums2
中的元素。示例:
2. 解答
解题思路:
nums1
、nums2
有序,若把nums2
全部合并到nums1
,则合并后的nums1
长度为m+n
m+n-1
的位置填充nums1
,比较nums1[len1]
与nums2[len2]
的大小,将最大值写入nums1[len]
,即nums1[len1]>=nums2[len2]
,nums1[len--] = nums1[len1--]
, 这里--
是因为写入成功后,下标自动建议,继续往前比较nums1[len--] = nums2[len2--]
len1 < 0
,即len2 >= 0
,此时nums1
已重写入,nums2
还未合并完,仅仅需要将nums2
的剩余元素(0…len)写入nums2
即可,写入后,合并完成len2 < 0
,此时nums2
已全部合并到nums1
,合并完成时间复杂度为 O(m+n)
代码实现:
3. 更多解答请看:图解 leetcode88:合并两个有序数组
六、字节 & leetcode1:两数之和
1. 题目
给定一个整数数组
nums
和一个目标值target
,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。
示例:
2. 解答
解题思路:
map = new Map()
nums
nums[i]
的差值,即k = target - nums[i]
,判断差值在map
中是否存在map.has(k)
为false
) ,则将nums[i]
加入到map
中(key 为nums[i]
, value 为i
,方便查找 map 中是否存在某值,并可以通过get
方法直接拿到下标)map.has(k)
),返回[map.get(k), i]
,求解结束nums
中没有符合条件的两个数,返回[]
时间复杂度:O(n)
代码实现:
3. 更多解答请看:字节 & leetcode1:两数之和
七、腾讯:数组扁平化、去重、排序
1. 题目
2. 答案:
感谢 352800205 的补充:
flat()
方法对 node 版本有要求,至少需要 12.0 以上3. 更多解答请看:腾讯:数组扁平化、去重、排序
八、leetcode349:给定两个数组,编写一个函数来计算它们的交集
1. 题目
给定两个数组,编写一个函数来计算它们的交集。
示例 1:
示例 2:
说明:
输出结果中的每个元素一定是唯一的。 我们可以不考虑输出结果的顺序。
2. 答案
解题思路:
filter
过滤Set
去重代码实现:
3. 更多解答请看:leetcode349:给定两个数组,编写一个函数来计算它们的交集
九、leetcode146:设计和实现一个 LRU(最近最少使用)缓存机制
1. 题目
运用你所掌握的数据结构,设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作: 获取数据
get
和写入数据put
。获取数据
get(key)
- 如果密钥 (key
) 存在于缓存中,则获取密钥的值(总是正数),否则返回-1
。 写入数据put(key, value)
- 如果密钥不存在,则写入数据。当缓存容量达到上限时,它应该在写入新数据之前删除最久未使用的数据,从而为新数据留出空间。进阶:
你是否可以在 O(1) 时间复杂度内完成这两种操作?
示例:
2. 答案
基础解法:数组 + 对象实现
类 vue keep-alive 实现
进阶:Map
利用 Map 既能保存键值对,并且能够记住键的原始插入顺序
3. 更多解答请看:leetcode146:设计和实现一个 LRU(最近最少使用)缓存机制
十、阿里算法题:编写一个函数计算多个数组的交集
1. 题目
要求: 输出结果中的每个元素一定是唯一的
2. 答案
使用 reducer 函数
3. 更多解答请看:阿里算法题:编写一个函数计算多个数组的交集
十一、leetcode21:合并两个有序链表
1. 题目
将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例:
2. 答案
解答:
确定解题的数据结构: 单链表
确定解题思路: 从链表头开始比较,
l1
与l2
是有序递增的,所以比较l1.val
与l2.val
的较小值就是合并后链表的最小值,次小值就是小节点的next.val
与大节点的val
比较的较小值,依次递归,直到递归到l1
l2
均为null
画图实现: 画图帮助理解一下
确定边界条件: 当递归到任意链表为
null
,直接将next
指向另外的链表即可,不需要继续递归了代码实现:
3. 更多解答请看:leetcode21:合并两个有序链表
十二、有赞 & leetcode141:判断一个单链表是否有环
1. 题目
给定一个链表,判断链表中是否有环。
为了表示给定链表中的环,我们使用整数
pos
来表示链表尾连接到链表中的位置(索引从0
开始)。 如果pos
是-1
,则在该链表中没有环。示例 1:
示例 2:
示例 3:
进阶:
你能用 O(1)(即,常量)内存解决此问题吗?
2. 答案
解法一:标志法
给每个已遍历过的节点加标志位,遍历链表,当出现下一个节点已被标志时,则证明单链表有环
时间复杂度:O(n)
空间复杂度:O(n)
解法二:利用
JSON.stringify()
不能序列化含有循环引用的结构时间复杂度:O(n)
空间复杂度:O(n)
解法三:快慢指针(双指针法)
设置快慢两个指针,遍历单链表,快指针一次走两步,慢指针一次走一步,如果单链表中存在环,则快慢指针终会指向同一个节点,否则直到快指针指向
null
时,快慢指针都不可能相遇时间复杂度:O(n)
空间复杂度:O(1)
3. 更多解答请看:有赞 & leetcode141:判断一个单链表是否有环
十三、图解 leetcode206:反转链表
1. 题目
示例:
进阶: 你可以迭代或递归地反转链表。你能否用两种方法解决这道题?
2. 解答
解法一:迭代法
解题思路: 将单链表中的每个节点的后继指针指向它的前驱节点即可
画图实现: 画图帮助理解一下
确定边界条件: 当链表为
null
或链表中仅有一个节点时,不需要反转代码实现:
时间复杂度:O(n)
空间复杂度:O(1)
解法二:尾递归法
解题思路: 从头节点开始,递归反转它的每一个节点,直到
null
,思路和解法一类似代码实现:
时间复杂度:O(n)
空间复杂度:O(n)
解法三:递归法
解题思路: 不断递归反转当前节点
head
的后继节点next
画图实现: 画图帮助理解一下
代码实现:
时间复杂度:O(n)
空间复杂度:O(n)
3. 更多解答请看:图解 leetcode206:反转链表
十四、leetcode876:求链表的中间结点
1. 题目
给定一个带有头结点
head
的非空单链表,返回链表的中间结点。如果有两个中间结点,则返回第二个中间结点。
示例 1:
示例 2:
提示:
给定链表的结点数介于 1 和 100 之间。
2. 解法:快慢指针
解题思路: 快指针一次走两步,慢指针一次走一步,当快指针走到终点时,慢指针刚好走到中间
时间复杂度:O(n)
空间复杂度:O(1)
3. 更多解答请看:leetcode876:求链表的中间结点
十五、前端算法集训营第一期免费加入啦
欢迎关注「前端瓶子君」,回复「算法」自动加入,从 0 到 1 构建完整的数据结构与算法体系!
在这里,瓶子君不仅介绍算法,还将算法与前端各个领域进行结合,包括浏览器、HTTP、V8、React、Vue 源码等。
在这里,你可以每天学习一道大厂算法题(阿里、腾讯、百度、字节等等)或 leetcode,瓶子君都会在第二天解答哟!
扫码进营学习!若二维码人数已经达到上限,可扫底部二维码,在公众号「前端瓶子君」内回复「算法」自动拉你进群学习
⬆️ 扫码关注公众号「前端瓶子君」,回复「算法」即可自动加入 👍👍👍
https://juejin.cn/post/6844904122496319495
The text was updated successfully, but these errors were encountered: