一切的前提——推导大 O 阶
BigO notation ：描述算法运行需要多少时间和空间
例如最经典的序列求和：
求 1+2+3+…+n 的值
很简单吧，只需要我们遍历 1 到 n，然后累加，便能得出答案
这段算法用 Big O 描述为： O(n)
n 表示算法里的变量 n
受循环的影响，整个程序的运算时间随着 n 的变大而变大
不信的话，我们来看下这个小算法的运行时间与占用内存
我们可以看到第一次计算花了 62ms，到了第十次居然花了 531ms，尽管在现代计算机中几乎可以忽略掉这几百 ms，但是无数个几百 ms 如果累加在一起那耽误的可不可能被忽略了
像魔笛手的创始者 Pied Piper，当初就是因为创造了一个强大的压缩算法而被美国互利公司以一千万美元收购，尽管 Pied Piper 当时选择了拒绝，但在一个听歌需要等待的时代，在 Pied Piper 强大的压缩算法下几乎没有延迟，就像你用 5G 网络玩游戏突然没了延迟，你还会用回 460ms 的 4G 吗？
做为初学者，在编码时我们应以完美主义的眼光去制作自己的作品，尽管我们能力有限
这便是大 O 推导阶能帮我们的
如果你还不感冒，那他至少可以帮我们看看，我们自己写的程序怎么样子，尽可能地，在程序的运行时间和占用空间上做到“完美”
序列求和的第二种写法：
是不是觉得代码少了很多？
这次我们没用循环，而是直接使用通项公式
此时的算法时间复杂度为：O(1)
为啥？因为我就计算一次，(1+n)*n/2 这套公式我就用一次
Big O 有个特点就是不在乎常量，例如我把(1+n)*n/2 写两次，输出两次，他还是 O(1)
*因为我就算一次*
我们来看下改良后的时间复杂度是多少：
531ms 到 171ms，时间减少了三倍
恐怕没有比这更令人兴奋的事情了吧
书里面还有一大堆的 O(n^m)、O(lnN)等等等，
这些都是常用的
按时间复杂度所耗费的时间从大到小排序依次为：
别看到公式就被吓倒了，例如 O(n^m)不就是嵌套 m 次循环嘛，以编码的角度来理解你就没有什么可害怕的了
时间复杂度还分三种情况
1.最好情况时间复杂度：
顾名思义，看名字你就知道，就是代码执行的次数为一次即为最好的 O(1)。 这是要我们写代码最想要的。但是这是不现实的。
2.最坏情况时间复杂度：
同样的看名字你也可以知道，这是代码执行的总次数很多，每次都要运行 n 次， 所以表示为 O(n)。这是我们写代码最不想要的。当然这也是不现实的。
3.平均时间复杂度： 就是把最好情况时间复杂度和最坏情况时间复杂度求取一平均值， 这是我们写代码最有意义的，因为这是期望的运行时间，所以在写代码时应当考虑这一点。
常见复杂度：
还有一个重要的概念：算法空间复杂度
所谓算法的空间复杂度就是通过计算机算法所需求的存在空间实现。 计算公式可以表示为：S(n) = O( f(n) )，其中，n 为问题的规模， f(n) 为语句关于 n 所占存储空间的函数。
一般情况下，一个程序在机器上运行时，除了考虑到程序的本身运行指令， 常数，变量和输入数据外，还需要考虑存储对数据操作的存储单元.我们在写代码 时完全可以用空间换取时间，两者不存在绝对的好与坏，这么用好二者关系取决于 你用在什么地方。所以，实际情况还是要根据工程代码做最完美的选择。
时间复杂度大 O 表示方法的由来。 大 O 推导的表示方法和常用的大 O 表示法时间复杂度。 时间复杂度的三种情况：最好情况、最坏情况和平均情况。 算法空间复杂度，适当情况可以用空间换取时间。
但不论怎么样，我们学习 Big O 的根本目的就是：用 Big O 方法帮帮助我们从各种编码思路中，找到最合适的那一种方案
数据结构是啥？
还有朋友可能不太理解什么是数据结构，就像喝水，你总是喝到最上面的一层，我称之为“水的栈”这便是一种结构
顾名思义数据结构，便是数据的结构，数据结构并不是什么很高深的东西
起初数据结构并没有一门专门的学科，并不是没有就代表不存在
我问大家一个问题，先有数据结构还是先有的编程？
瑞典计算机科学家 Niklaus Wirth 在 1976 年写了一本书，叫作《Algorithms + Data Structures = Programs》，数据结构的学科便从此发展的不可收拾
要知道早在 1949 年汇编就诞生了
其实深究这个问题是没有任何意义的，如 Niklaus Wirth 的书名：《Algorithms + Data Structures = Programs》
学习数据结构的目的就是为了让我们理解数据在计算机里的存储结构
树？图？栈？
别被这些名词给吓到了，例如"树"，你就可以理解数据在计算机中是像树一样的存储，不妨打开你的电脑，随便看一看自己的文件目录，是不是就像一颗树一样
数组
关于数组的知识，我想是我们每个初学者的必学必备
但我想没多少人能真正理解到——数组其实就是一种数据结构
一维数组就是一行数据，n 个数据，二维数组就是 n 行，m 列，n*m 个数据，那三维数组呢？除此之外还有五维、六维。。。。直到内存爆炸，这该怎么描述？所以死记硬背是行不通的，只有了解其底层含义才能通向罗马。
如图：不同维度的数组长这样
很简单是不是？
高纬度嵌套低纬度，同时高纬度等于下一级维度的 2 倍
接下来就是数组优点：
1、按照索引查询元素速度快
例如 j[1]
2、按照索引遍历数组方便
例如 j[i]
缺点：
1、数组的大小固定后就无法扩容了
2、数组只能存储一种类型的数据
3、添加，删除的操作慢，因为要移动其他的元素。
适用场景：
频繁查询，对存储空间要求不大，很少增加和删除的情况。
扩展：
我们也可以
创造一个简单
存储字符串的动态数组
像 List 一样存储数据：
运行结果：
感受到数据结构的魅力了吗？
你所使用的容器，也都是被前辈们这样基于底层创造出来的，当然了，他们更强大
栈
栈的结构如图：
之前我们提到了：
数据结构就像喝水，你总是喝到最上面的一层，我称之为“水的栈”这便是一种结构
所以你可以把栈的结构理解为一杯水
栈顶为杯口，栈底理解为杯底
而水只能从杯口出入，栈内的数据也只能从栈顶提取/输入
不借助任何工具，喝水时你总是喝到离杯口最近的水，往水杯里加水你也不可能从水杯中间加水
栈也是如此，你只能从栈顶按顺序提取数据，所以插入数据你需要将索引位置以上的数据都提取出来，再插入，而后将提取出的数据再依次存入
基本算法
1．进栈（PUSH）算法
① 若 TOP≥n 时，则给出溢出信息，作出错处理（进栈前首先检查栈是否已满，满则溢出；不满则作 ②）；
② 置 TOP=TOP+1（栈指针加 1，指向进栈地址）；
③S(TOP)=X，结束（X 为新进栈的元素）；
2．退栈（POP）算法
① 若 TOP≤0，则给出下溢信息，作出错处理(退栈前先检查是否已为空栈， 空则下溢；不空则作 ②)；
②X=S(TOP)，（退栈后的元素赋给 X）：
③TOP=TOP-1，结束（栈指针减 1，指向栈顶）。
栈常应用于实现递归功能方面的场景，例如斐波那契数列。
好理解吧！
栈就是一种特殊的线性表，仅能在线性表的一端操作，栈顶允许操作，栈底不允许操作
栈的特点是：先进后出，或者说是后进先出，从栈顶放入元素的操作叫入栈，取出元素叫出栈。
队列
队列和栈一样，也是一种线性表
队列的结构长这样：
但也有队列也有和栈的不同之处：
可以简单理解为队列为没有杯底的杯子，一端负责进水，一端负责出水
也就是：先进先出，从一端放入元素的操作称为入队，取出元素为出队
使用场景：因为队列先进先出的特点，在多线程阻塞队列管理中非常适用
