【化解数据结构】从这里开启数据结构和算法

举报
阿童木 发表于 2021/12/20 15:33:47 2021/12/20
【摘要】 这是我参与11月更文挑战的第3天,活动详情查看:2021最后一次更文挑战📢 大家好,我是小丞同学,一名大二的前端爱好者📢 这篇文章是数据结构与算法专栏的第一篇博文📢 非常感谢你的阅读,不对的地方欢迎指正 🙏📢 愿你忠于自己,热爱生活 💡 知识点抢先看算法基础计算时间复杂度计算空间复杂度数据结构和算法的学习指南❗❗❗ 文末有惊喜噢~ 专栏简介按照惯例,每个专栏的第一篇文章都会简单的...

这是我参与11月更文挑战的第3天,活动详情查看:2021最后一次更文挑战

📢 大家好,我是小丞同学,一名大二的前端爱好者

📢 这篇文章是数据结构与算法专栏的第一篇博文

📢 非常感谢你的阅读,不对的地方欢迎指正 🙏

📢 愿你忠于自己,热爱生活

💡 知识点抢先看

  • 算法基础
  • 计算时间复杂度
  • 计算空间复杂度
  • 数据结构和算法的学习指南

❗❗❗ 文末有惊喜噢~

专栏简介

按照惯例,每个专栏的第一篇文章都会简单的介绍一下这个专栏的内容,以及未来的更文计划

本专栏 【化解数据结构】,将在这里总结自己学习数据结构和算法的学习笔记,从这篇算法入门开始,未来更文将涉及栈、队列、链表、堆、树、图…等数据结构,以及经典排序算法,算法设计思想等进阶算法…,同时将会结合 LeetCode 题目对每篇文章进行巩固和提升,欢迎大家关注本专栏或添加作者本文联系方式,一起努力,一起刷题,一起进步 🏆

image-20210929202048085

(图片来源于慕课网截图)

引言

在正式写这个之前,先来讲讲为什么要学数据结构和算法?

  • 为了计算出最优解

这是我的答案,当我打开 LeetCode 第一题两数之和的提交记录时,我发现自己半年前的代码,耗时 240ms,内存占用 40多mb 时,我感受到了它的魅力

image-20211029151803918

在最新的代码中,我采用了 map 的容器,通过 has 方法替代了先前采用的 indexof 方法,从查到的资料来看,map 的查找的时间复杂度为 O(1)indexOfO(n) ,在 map 的底层实现中采用了哈希表的数据结构,极大的优化了查找的复杂度

接下来我们来看看如何计算时间、空间复杂度!

一. 大 O 表示法

关于复杂度的计算,我们采用的是 大 O 表示法 ,它用来描述算法性能和复杂程度

常见的表示

符号大O标记法 名称
O(1) 常数
O(log N) 对数
O(N) 线性
O(N log N) 对数多项式
O(N^2) 二次
O(2^N) 指数
O(N!) 阶乘

大 O 表示法一般考虑的是 CPU 占用时间,它可以粗略的了解代码运行的时间效率

例如

function test(num){
	return ++num;
}

我们调用这个函数一次,执行时间是 t ,我们再调用一次,执行时间还是 t,和传入的参数无关, test 函数的性能都一样,因此它的复杂度为 O(1)

当循环 n 次时,就是 O(n)

二. 时间复杂度

O 表示法表明的是该段代码执行时间随数据规模增大的变化趋势,它的特点是

  • 只关注量级最大的时间复杂度

常见的时间复杂度量级 O(1) < O(logn) < O(n) < O(n^2)

对于 O(2)、O(3) 这些,我们都叫做 O(1) 常数级

例如:

1. O(1)

let i = 0;
i += 1;
// 每次执行代码只执行一次 O(1)

这段代码每次只执行一次,因此为 O(1)

2. O(n)

for (let j = 0; j < n; j++) {
    console.log(j);
}

再上面这段代码中,我们每次都需要执行 n 次的 log ,因此我们可以把它看作 O(n)

同样的我们再来看一个

let i = 0;
i += 1;
for (let j = 0; j < navigator; j++) {
    console.log(j);
}

这种代码我们经常写,前面是我们刚刚计算的 O(1),后面是 O(n) ,它们并行排列,时间复杂度相加,取最大的那个

  • 因此它的时间复杂度同样是 O(n)

3. O(log(n))

while (i < n) {
    console.log(i);
    i *= 2;
}

对于 log(n) 的情况,在个时间复杂度是很好的,当然 O(1) 是最好的,但是在解题的时候,如果能优化到 log(n) 也是很不错的了

那它是如何计算的呢?

我们可以看到,这里采用了 变量i来控制循环的终止,每次循环体中,都需要 2 * i 的操作

因此对于时间复杂度的计算 2^t = n 解得 t = log(n)

4. O(n^2)

for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
        console.log(i);
    }
}

对于这种嵌套排列,时间复杂度是 n^2 ,外面一层 n ,里面一层 n 乘一下就是 n^2,冒泡排序的时间复杂度就是 O(n^2)

关于时间复杂度就介绍这么多,其他的思路都差不多

image-20211029161002646

三、空间复杂度

空间复杂度表示的是:存储空间随数据规模的增长趋势,在 LeetCode 中最直接的反应就是内存消耗

例如

1. O(1)

let i = 0;

在这里我们申请了单个变量的内存空间,为 O(1)

2. O(n)

let arr = []
for(let i = 0;i < n;i++) {
    arr.push(i)
}

像这样的一个数组,并给它填满值,n 越大,它需要分配的空间就越多,它的空间复杂度就是 O(n)

3. O(n^2)

int arr = [][]
// 遍历赋值

声明一个二维数组,填满值,它的空间复杂度就是 O(n^2) ,你可以理解为一个矩阵,n*nn^2

📌 总结

  1. 复杂度计算按最高阶来计算
  2. 时间、空间复杂度描述的都是随数据规模的变化趋势
  3. 时间复杂度的重点在于循环嵌套
  4. 空间复杂度关注于内存

🐣 博主有话说

关于如何学习数据结构和算法,以及前端仔为什么要学算法?我想说

1. 如何学习数据结构和算法?

首先,我个人觉得学习任何东西,都需要一个适合自己的方法,其次是需要懂得如何去获取学习资源,如何找到优质的学习资料,这些都是很重要的,这不仅仅是对于数据结构和算法而言,学习什么都是如此。

再谈谈如何学习数据结构和算法:(拿我自己来说),其实这篇文章的内容没有什么特别难的东西,可以说基本看一眼就会了,那我为什么还要写它呢,习惯和想法

对我自己,我偏向于看视频来初次学习,这样可以跟着老师的思路,很快的找到门路,也能很好的帮助我引导我学下去。在看视频的同时,一定要动手动手动手!有题目的时候可以暂停下来,自己先理一遍思路,动手敲一下,再看老师是如何解的。这样更加能提升自己的代码能力。同时对于同一道题目,我喜欢尝试多种解法,以最优雅JS 代码来解题,一直是我在算题中的小目标。

在学习完之后,我会总结自己的学习笔记,例如之前的 react 学习笔记是在每天学习之后,晚上整理的,从每个知识点到 Demo 中的每个功能的实现,都有记录,这也算是对自己学习的复盘吧~再到 从零实现一个任务管理系统 的专栏了,这个是在做完整个项目之后,自己又重头再梳理一遍整个项目的逻辑过程,以及每个 hook 的功能实现。在我的观念中,只有把总结写好了,才算学会了,不然都是会忘记的。因此,我觉得笔记十分重要

总结一下就是:学的时候多敲代码,学完之后总结笔记

2. 说说为什么要学数据结构和算法吧?

  1. 第一点:如文章开头所言,我想要写出最优的代码,这点是个人观念的原因,在学习了 ES6+ 语法之后,以前很多的代码都显得冗余复杂了,mapset 就是最好的例子

  2. 第二点:提高代码运行效率,这一点不仅仅体现在刷算法题上,更体现在实际场景中,我们可能会因为我们的算法问题导致了时间复杂度过高,导致发送无用请求,导致前台页面等待时间过长等问题,这些都是我们前端需要懂得优化的

  3. 第三点:为了面试,这就很真实了,在网上看了很多的面经,算法都是必要的一环,所以学习好数据结构和算法也能为自己以后面试提前做好准备

一些小的建议:不要盲目的刷题,可以有针对性的,按照某一个类型的题来刷,比如这段时间我就刷关于树这个数据结构的题,下一段时间我刷堆的题,这样可以保证我们的刷题质量,同时把大量的时间花在刷算法题上是很不可取的噢~每天抽一点时间写 2,3 道这样慢慢积累,循循渐进~

3. 学习资料分享

书籍:《JavaScript 数据结构和算法》

Github仓库:JavaScript 算法与数据结构

视频推荐:B站 coderwhy 老师的视频

刷题地址:acwingleetcode

以上资源没有广告费,纯好感!!书籍没有的话可以联系我噢~


💌 最后,可能在很多地方讲诉的不够清晰,请见谅

💌 如果文章有什么错误的地方,或者有什么疑问,欢迎留言,也欢迎私信交流

【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。