序言

温馨提醒，想直接看正文的可以跳过本段哈。在上个月底作者终于结束了C语言的入门和深剖，对的，之前说过进阶还在路上哈（寒假就有了哈）。然后一直到现在才再次冒头，绝对不是玩去了哈，我没有偷懒哈，咳咳，当然也确实休息了两天，跨年嘛不是（这绝对不是我去浪的借口咳咳），不过紧接着就是莽数据结构去了，在此之前是接触了一点的，那时学完了顺序表，链表，栈和队列，然后消失的这几天就再次复习了一下，真的是解决了当时很多的疑惑，收获真的很多，当然也不是复习这一个原因，因为复习之前也把C语言理论是学完了，这也是理解更深一个很重要的原因哈。然后就一直往下学，至1月3日晚，作者完成了这2022的第一篇博客，其实开始是没准备来写的，本想着把数据结构快速过一遍再来写博客的，但是可能一直看视频而且用倍数吧，脑袋有点晕乎乎的，在队列结束后就是二叉树了，然后二叉树又是比前面的更难一些，所以就准备第二天再去肝他，状态会好点，然后就有了本篇文章。想了想，数据结构对于小白不像之前那么容易理解，而且作者也想去更加完善文章，提升一下文章的品质，而且准备一下写一个大内容，比如链表就是一个单内容这样，不要像之前的分篇去写，当然之前是没办法哈，内容太多了，一起太杂了，而且关联性也不是那么强，但是数据结构关联性很强而且内容不是太多可能更多偏于理解（就目前觉得），所以就准备一大块一大块内容来写哈，感觉应该挺不错的。但是之后的更新速度应该会慢一点了，可能两三篇一周吧？但是绝对精哈！当然也可能有一些其他的文章，但是数据结构更新应该是快也快不了太多吧。好像想说的也就这么多，让我们一起加油吧！冲刺大厂，不负未来，不负你！  

谁都不能阻挡你成为更优秀的人。  

1. 数据结构前言

1.1. 什么是数据结构？

数据结构(Data Structure)是计算机存储、组织数据的方式，指相互之间存在一种或多种特定关系的数据元素的集合。

1.2.什么是算法？

算法(Algorithm):就是定义良好的计算过程，他取一个或一组的值为输入，并产生出一个或一组值作为输出。简单来说算法就是一系列的计算步骤，用来将输入数据转化成输出结果。

 

1.3.如何学好数据结构和算法

3.1. 死磕代码，磕成这样就可以了（=。=哈哈）

3.2. 注意画图和思考

两点都非常重要，如果要做一个好的程序员，数据结构的学习绝对是必不可少的哈！

2. 什么是时间复杂度和空间复杂度？

大家一般都是在各种算法题目上面看见的，是一个限制条件，其实网上是有很多篇幅去讲这个东西，但是其实很简单。总结就是时间复杂度不看时间，看次数。空间复杂度不看空间看个数。

2.1. 算法效率

算法效率分析分为两种：第一种是时间效率，第二种是空间效率。 间效率被称为时间复杂度，而空间效率被称作空间复杂度。 时间复杂度主要衡量的是一个算法的运行速度，而空间复杂度主要衡量一个算法所需要的额外空间，在计算机发展的早期，计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展，计算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注一个算法的空间复杂度

2.2. 时间复杂度的概念

时间复杂度的定义：在计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。一个算法执行所耗费的时间，从理论上说，是不能算出来的，只有你把你的程序放在机器上跑起来，才能知道。但是我们需要每个算法都上机测试吗？是可以都上机测试，但是这很麻烦，所以才有了时间复杂度这个分析方式。一个算法所花费的时间与其中语句的执行次数成正比例，算法中的基本操作的执行次数，为算法的时间复杂度。

即：找到某条基本语句与问题规模N之间的数学表达式，就是算出了该算法的时间复杂度。

2.3. 空间复杂度的概念

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。

空间复杂度不是程序占用多少byte空间，因为这个也没太大意义，所以空间复杂度算的是变量的个数。空间复杂度计规则基本跟时间复杂度类似，也使用大O渐进表示法。

注意：函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了，因此空间复杂度主要通过函数在运行时候显示申请的额外空间来确定。

3. 如何计算常见算法的时间复杂度？

3.1. 让我们来举个栗子（重点）

实际中我们计算时间复杂度时，我们其实并不一定要计算精确的执行次数，而只需要大概执行次数，那么这里我们使用大O的渐进表示法。

大O符号（Big O notation）：是用于描述函数渐进行为的数学符号。

这上面的时间复杂度就是N*N+2*N+10，但是如果N够大，2*N和10就显得很小，可以忽略不计，此时N*N非常大，所以时间复杂度就是O（N^2）。

再说明，比如我们去N个数里面找一个数（没有相同的），有三种情况，最好情况一次找到，平均情况N/2，最坏情况N次找到在实际中一般情况关注的是算法的最坏运行情况，所以数组中搜索数据时间复杂度为O(N) 。  

1. 基本操作执行了2N+10次，通过推导大O阶方法知道，时间复杂度为 O(N)。

2. 基本操作执行了M+N次，有两个未知数M和N，时间复杂度为 O(N+M)。（要注意N，M差距大不大）

3. 基本操作执行了10次，通过推导大O阶方法，时间复杂度为 O(1)。（只要是只有准确的数字就是O（1））

4. 基本操作执行最好1次，最坏N次，时间复杂度一般看最坏，时间复杂度为 O(N)。

5. 基本操作执行最好N次，最坏执行了(N*(N+1)/2次，通过推导大O阶方法+时间复杂度一般看最坏，时间复杂度为 O(N^2)。

6. 基本操作执行最好1次，最坏O(logN)次，时间复杂度为 O(logN) 。ps：logN在算法分析

中表示是底数为2，对数为N。有些地方会写成lgN（其实是错的，与数学有矛盾）。

7. 基本操作递归了N次，时间复杂度为O(N)。

3.2. 时间复杂度对比（图解）

4. 如何计算常见算法的空间复杂度？

使用了常数个额外空间，所以空间复杂度为 O(1)。（上面不一定画完了哈，就是有多少个变量，但是是常数个，和时间复杂度是差不多的其实，就是看的东西不一样）。

递归调用了N次，开辟了N个栈帧，每个栈帧使用了常数个空间。空间复杂度为O(N) 。

今天的内容就到这里了哈！！！

要是认为作者有一点帮助你的话！

就来一个点赞加关注吧！！！当然订阅是更是求之不得！

最后的最后谢谢大家的观看！！！

你们的支持是作者写作的最大动力！！！

下期见哈！！！