算法基础知识整理（数据结构）
算法定义：
在算法导论一书中，对于算法的定义为：任何良定义的计算过程，该过程取某个值或集合作为输入，并产生某个值或值得集合作为输出
我们也可以把算法看成是用于求解良说明的计算问题的工具。一般来说，问题陈述说明了期望的输入/输出关系。算法则描述一个特定的计算过程来实现该输入/输出。
算法复杂度：
评估一个算法的优劣，是根据算法的复杂度来决定的。复杂度分为两类，一类为时间复杂度，一类为空间复杂度。
时间复杂度并不是指的是评估算法运行的绝对时间，而是算法的运算次数。（一般来说，时间复杂度是一个渐进的概念，我们往往会忽略相关常数）
空间复杂度指的是算法所开辟变量和运行时的所占空间。
在一般场景下，我们认为时间复杂度优于空间复杂度。原因是现在的机器硬件足以撑起一定体量的数据（超大型的数据例外），而运算的快慢则相对成为决定算法优劣的主要因素。
比如：数据存储的“以空间换时间”的概念，虽然它违反了数据的第三范式
时间复杂度：
再次说明，时间复杂度度不是对预估算法的执行时间，而是预计次数。
定义为：若存在函数f(n)，使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于
零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n))，称为
O(f(n))，O为算法的渐进时间复杂度，简称为时间复杂度。
时间复杂度，有几种类型：
线性：
最简单的for循环，执行次数由自变量的大小决定，因此是一个线性结构。复杂度为O(n)
常量：
这类执行为具体常数，比如以下标在数组中进行获取数据，就是O(1),必须需要说明的是在算法中，哪怕你循环的次数特别巨大，但是只要是一个特定的值，那么他也是为O(1)
对数：
这种类型主要用于树。在一个二叉树中，若要查找一个数，第一次在根节点判断（2^0），第二次在第二层判断(2^1),第三次在第三层判断（2^2），依次类推（N=a^x，因为二叉数，a为2）。
那么反过来，树的高度和节点的关系就是以2为底，树的节点总数n的对数。（y=
log
a
N
），复杂度为O(log(n))
多项式：
这种复杂度可以理解为，多层for循环，然后内层循环的自变量随着外层循环变化。
for(int i =0;i<n;i++){
for(int j = 0;j<i;j++){
}
实际上，这么看时间复杂度很抽象，但是我们要结合数学来进行看，这边画一下图，会有很直观的感受。
通过函数图，我们就可以直观明了的看出各个算法的优劣。
但是实际上，算法还是有几个原则的。
1.如果运行时间是常数量级，则用常数1表示
2.只保留时间函数中的最高阶项
3.如果最高阶项存在，则省去最高阶项前面的系数
比如 T(n)= 100n，时间复杂度是O(n)，他省略了系数
T(n)= 5n^2+3^n+10，时间复杂度是O(n^2 )，只保留了最高阶且省略了系数。
T(n)= 500,时间复杂度是O(1)，常量级别。
空间复杂度：
空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度，用大O表示，记作S(n)=O(f(n))。
空间复杂度如下：
常量空间：var = 1 空间为O(1)
线性空间 int[] array = new int[]; 空间为O(n)
二维空间 int[][] 一个二维数组 O(n^2)
递归 也就是方法调用本地方法，是方法调用栈
数据结构：
数据结构是一种存储和组织数据的方式，意在便于访问与修改。
数据结构总体上有很多种，诸如线性数据结构，树，图，以及其他数据结构（跳表，hash链表，位图）
算法与数据结构直接相互依赖，在我的理解中数据结构决定内部结构，算法决定计量的方式。
数据结构又分为逻辑结构与物理结构。
物理结构主要为顺序存储结构和链式存储结构。物理结构是真实存储在内存上的结构，这里指数组和链表。
而逻辑结构指的是，在对应的物理结构之上，所衍生出来的结构，比如顺序表，栈，队列。他们在内存上的存储结构均是数组（链式存储结构）
这里先描述两个物理结构：
数组：
数组是由有限个相同类型的变量所组成的有序集合，它的物理存储方式
是顺序存储，访问方式是随机访问。利用下标查找数组元素的时间复杂
度是O(1)，中间插入、删除数组元素的时间复杂度是O(n)。
需要说明的是：它本身是一个有序的数据结构，在磁盘上所占用的空间是连续的代码块
查找所需要的时间复杂度为O(1) 是因为直接根据下标在物理地址上 找到了对应的数据
所谓更新和删除所需要O(n)是因为，需要修改被更新或者删除之后所有元素的index下标
链表
链表是一种链式数据结构，由若干节点组成，每个节点包含指向下一节
点的指针。链表的物理存储方式是随机存储，访问方式是顺序访问。查
找链表节点的时间复杂度是O(n)，中间插入、删除节点的时间复杂度是
O(1)。
如果说，数组是内存排序中连续而不间断的存在，那么链表便是离散的。他可以有效的利用琐碎而不连续的空间
链表又分单向链表和双向链表。本质上是多一个指向的node
链表的插入异常简单，只需要修改对应的指向node节点
但是链表的查询，只能以链式的方式进行依次查找
栈
本身是FILO，入栈和出栈均为O(1)，实现也很简单，拿到第一个节点或者最后一个节点，往里面塞或者删除就可以进行操作
栈的一个很好的使用叫做，面包屑导航，通俗的讲，你在浏览网页是时候的后退后退后退
需要说明的是，栈是逻辑结构，本质上的实现方式 可以分为数组和链表
数组实现如下：
链表实现如下：
队列
本身是一个FLFO，入栈和出栈也均为 O(1), 操作和栈差不了多少
但是对于数组形式的队列（链表形式的队列和栈真差不多），有一个循环队列的操作
场景为，数据在被删除的情况下，进行新增，若这个时候依次排序，新插入的数据在队尾，但是没有空间了。
这个时候处理的方式为，数据照常插入，但是队尾就变成了原本被删除的第一个元素的位置，依次循环。
一直到（队尾下标+1）%数组长度 = 队头下标 时，代表此队列真的已
经满了。
需要注意的是，队尾指针指向的位置永远空出1位，所以队列最大容量比数组长度小1
由于队列的FIFO的特性，他的应用场景是那些对顺序有要求的，比如公平锁竞争
而结合队列和栈的特性，有一个双端队列，它可以既是先进先出 也是后进先出
散列表
散列表也叫作哈希表 （hash table），这种数据结构提供了键（Key）
和值（Value） 的映射关系。只要给出一个Key，就可以高效查找到它
所匹配的Value，时间复杂度接近于O(1) 。
提到HashTable必须要涉及到一个东西，那就是hash算法，以java的hashTable来看，他本身是一个Entry的key，value的形式，在进行set key的时候，我们在内存上存储的不会是一个具体的key，而是一个取得hash算法后的key
jdk代码如下
这边hash算法大概的意思是无符号位移16位
但是hash是会有冲突的，我查阅了相关的资料：哈希是通过对数据进行再压缩，提高效率的一种解决方法。
但由于通过哈希函数产生的哈希值是有限的，而数据可能比较多，导致经过哈希函数处理后仍然有不同的数据对应相同的值。这时候就产生了哈希冲突。
现在的场景是这样的，有一个key它已经插入到了内存对象中，他的key通过hash位移之后变成了一个特定的值，然后恰好第二个key也是这个值，这个时候两个hash值就冲突了
已经冲突的第二个key很多种处理方法，包括开放地址方法，链式地址法，建立公共溢出区，再哈希法
在jdk hashMap中的处理方法时链式地址法，也就是说，我虽然hash冲突了，但是我在这个冲突的hash值上挂了多个key。
所以综上所述，他的get其实就是key转hash值，去匹配，若匹配到hash值一样，key一样则获取
他的put为，key转hash值，put key和hash。若hash值冲突，则以链表的形式挂上去
当然这里会有涉及到一个自动扩容后的重新hash，为了减少hash冲突的概率，让hash变得尽量均匀
树：
树是一个大家族，从结构上定义，树有 二叉树，满二叉树，完全二叉树，二叉搜索树，平衡二叉树，多路平衡二叉树，红黑树。
而之说以有这么多数的不同结构与定义，在本质上面我们都希望树，变得更加“平衡”。
树的产生，在我看来是由“分冶 ”而产生的，也就是我们常说的，在100内猜一个数，我们会择中而取，然后比大小
但是在某些极端的场景下，树会变成一长条（塞值的顺序和值的大小相对一致），那么这个时候它的时间复杂度是O(n)，为了降低时间复杂度，不同的树提供了不同的解决策略
平衡二叉树（AVL）提供了旋转（LL,LR,RL,RR）
B树 提供了分裂合并
之前也说了，树其实算是逻辑结构，那从物理结构上来讲，无论是数组还是链表我们都可以实现他。
链表的实现相对来说比较简单，我们看一下结构图
而数组的结构如下：（我其实费了比较大的劲画出来的，其实我不太认可这种存储方式）
在设计这个模式的时候，我们必须知道每一行，最多的节点有多少个k^(n-1)次方。其中的k在二叉树的概念中，指的是2.这是由定义决定的
因为二叉树是分为2叉。其中的n指的是层（从1开始）
既然知道了这个，那么以二叉树为列子。
整体数据结构如下
二叉树的遍历分为两大类，一类为深度优先遍历，一类为广度优先遍历。
深度优先遍历：
1. 前序遍历。输出顺序是根节点、左子树、右子树。
2. 中序遍历。输出顺序是左子树、根节点、右子树
3. 后序遍历。输出顺序是左子树、右子树、根节点。
广度优先遍历：
4. 层序遍历。就是二叉树按照从根节点到叶子节点的层次关
系，一层一层横向遍历各个节点。
二叉堆：
二叉堆是一个完全二叉树，二叉堆又分为两个类型，分别是最大堆和最小堆。
最大堆的任何一个父节点的值，都大于等于左右子节点的值
最小堆的任何一个父节点的值，都小于等于左右子节点的值
二叉堆的自我调整
二叉堆的插入和删除是有区别的，因为他需要保证整个堆的大小结构问题
当插入一个元素时，他会从底部最后一个元素插入，然后进行比较他的父节点与自己值的大小，（最大堆要保持父节点最大，最小堆要保持父节点最小）来决定是否上浮
若是删除一个元素时，会从底部拿一个元素来进行替换删除的元素位置，在进行下沉。以此来调整整个树的结构
关于树的时间复杂度：
需要说明的是，树的复杂度并不是不变的，我们通常以最坏时间复杂度，最好时间复杂度，以及平均时间复杂度来描述他
对于非平衡的二叉树来说，他的最坏时间复杂度为O(n)，所有元素均在一端排列
而对于平衡的二叉树来说，他的最坏事件负责度和平均时间复杂度一致，是O(logn
)
在平衡树中，
查找一个数字，
第一次在根节点判断（2的0次方），第二次在第二层节点判断（2的一次方），第三次在第三层判断（2的2次方）
以此类推，树的高度是多少就会判断多少次
树的高度和节点的关系就是以2为底，树的节点总数n的对数