常见概念
时间复杂度
常见的算法时间复杂度由小到大依次为：Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n^2)＜Ο(n^3)＜…＜Ο(2n)＜Ο(n!)
例如：
1、时间复杂度为Ο(1)
sum = n*(n+1)/2
2、时间复杂度O(n)
for(int i = 0; i < n; i++){
printf("%d ",i);
}
3、时间复杂度O(n^2)
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
printf("%d ",i);
}
}
4、O(log2n)
int i = 1, n = 100;
while(i < n){
i = i * 2;
}
数组
查询时间复杂度0（1）删除和插入 0（N）
常用排序算法的时间复杂度
| 算法名称 | 最差时间分析 | 平均时间复杂度 | 稳定度 | 空间复杂度 |
|---|---|---|---|---|
| 冒泡排序 | O(n²) | O(n²) | 稳定 | O(1) |
| 快速排序 | O(n²) | O(n*log2n) | 不稳定 | O(log2n)~O(n) |
| 选择排序 | O(n²) | O(n²) | 稳定 | O(1) |
| 二叉树排序 | O(n²) | O(n*log2n) | 不稳定 | O(n) |
| 插入排序 | O(n²) | O(n²) | 稳定 | O(1) |
| 堆排序 | O(n*log2n) | O(n*log2n) | 不稳定 | O(1) |
| 希尔排序 | O | O | 不稳定 | O(1) |
空间复杂度
空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度，记做S(n)=O(f(n))
分为算法本身需要的存储空间、输入数据所占用的存储空间、运行过程所需要的存储空间
数据结构
数据存储结构
顺序存储方式：优点：逻辑顺序排序、数据长度固定
链式存储方式：解决顺序存储的存储空间利用不灵活，扩充困难特性
算法分析方法
穷举法
穷举法也可以对问题进行分析，这样可以减少穷举对次数
回溯法
穷举法的改进
分治法
将问题拆分为若干哥子问题，使问题简单话，然后分别求解各个子问题，再得到原题的解
例如二分查找法求最大值
减治法
贪心法
求最优解的时候
动态规划法
与分支方法类似，只是划分的子问题之间往往有联系
例如斐波拉契数列可以用递归也可以用动态规划 先计算子的
/**
* 递归
*
* @param i
* @return
*/
private static int getSum(int i) {
if (i < 1) {
return 0;
}
if (i <= 2) {
return 1;
}
return getSum(i - 1) + getSum(i - 2);
}
/**
* 动态规划
* @param i
* @return
*/
private static int demoTwo(int i) {
if (i < 1) {
return 0;
}
if (i <= 2) {
return 1;
}
int tempNext = 1;
int tempNextNext = 1;
int temp = 0;
for (int j = 2; j < i; j++) {
temp = tempNext + tempNextNext;
tempNext = tempNextNext;
tempNextNext = temp;
}
return temp;
}
队列与栈
栈是只只能在表【尾部】进行插入和删除操作等线性表，后进先出，
入栈：它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素
出栈：它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素
java中的栈是用Stack,Stack继承了Vector Vector与ArrayList类似只是Vector是
线程安全的，所有操作方法都加了synchronized
push 压栈 pop出栈，peek获取栈顶的元素。
栈的线性存储结构：
其实就是记录栈顶的数组index，每次插入或者删除都是操作栈顶的数组index
栈的链表存储结构：
单链表的header节点就当作 栈的头指针
public void push(Node node) {
if (header == null) {
header = node;
} else {
node.next = header;
header = node;
}
}
public Object pop() {
if (header == null) {
return null;
} else {
Object object = header.object;
header = header.next;
return object;
}
}
队列是只只能在一端插入，在另外一端删除等线性表，
允许插入的是【队列尾部】，允许删除的叫【队列头部】
=》尾e,d,c,b,a头=》
队列 ：先进先出 FIFO(First Input First Output)
新元素（等待进入队列的元素）总是被插入到队列的尾部，
而读取的时候总是从队列的头部开始读取。
栈就是一个桶，后放进去的先拿出来，它下面本来有的东西要等它出来之后才能出来。（后进先出）
栈的概念bai是弹压，就像子弹壳装弹，一du粒一粒压进去，zhi但是打出来的dao时候是从上面打出来zhuan的，
最先shu压进去的最后弹出来，如果进去顺序是123，打出来顺序是321，这就是后进先出
队列只能在队头做删除操作,在队尾做插入操作.而栈只能在栈顶做插入和删除操作。（先进先出）
队列的概念就是我们平时排队，按次序来，你排在第1个，那你就第一个轮到，就是先进先出，先到先来
字符串搜索KMP算法
避免不必要的回溯，利用已经部分匹配这个有效信息，保持i指针不回溯，通过修改j指针，让模式串尽量地移动到有效的位置
j指针可以基于next数组，j的值多少是基于当前字符串之前的串的前后缀相似度
next[j] 公式
1、j=1 next[1]=0
2、max{k|1<k<j} 并且 p[1~k-1]=p[j-k+1~j-1] 时候
3、其他情况 next[j]=1
next数组推导
public static int[] getNext(char[] p) {
//next数组
int[] next = new int[p.length];
//初始化等于0
next[0] = 0;
//后缀
int j = 1;
//前缀
int k = 0;
while (j < p.length - 1) {
// //next[j]表示的是当T[i]和P[j]不同是，j要回到哪个位置
if (k == 0 || p[j] == p[k]) {
++j;
++k;
/**
* next[j+1] == k + 1 == next[j] + 1
*/
next[j] = k;
} else {
//不匹配 k值回溯 模式串的自我匹配 找到p[k]对应的next[k]
//例如
/**
* j 1 2 3 4 5 6 7 8 9
*
* a b a b a a a b a
*
* k 0 1 2 2 3 4 2 2 3
*
* 当就j=6 k=4的时候 出现不匹配
* p[j]=a p[4]=b
* 这个时候就要回溯长度更短的相同前缀后缀
* 需要将k的值回溯（因为前面已经有了4个相同的了，所以k要往回移动4位）
* k=next[k] ==> k=next[4]=2
* p[k]=p[2]=b 还不相等 继续回溯
* k=next[2]=1
* p[k]=p[2]=a 与p[j]=a相等
* next[7]=2
*
* 如果直接用k=k-1会有问题
*
*/
//next[k]表示当前节点前面有相同前缀的最大数量
k = next[k];
/**
* next[k]表示p[k]前面有相同前缀尾缀的长度(这个长度是按最大算的)，
* p[next[k]]表示相同前缀的最后一个字符，如果p[next[k]]==p[j]，
* 则可以肯定next[k+1]=next[k]+1,如果p[next[k]]!=p[j]，
* 既然next[k]长度的前缀尾缀都不能匹配了，是不是应该缩短这个匹配的长度，
* 到底缩短多少呢，next[next[k]]表示p[next[k]]前面有相同前缀尾缀的长度(这个长度是按最大算的)，
* 所以一直递推就可以了，因为这个缩小后的长度都是按最大的算的
*/
}
}
return next;
}
跳跃表
https://www.jianshu.com/p/168423ad0ab9
https://www.cnblogs.com/cofjus/p/13602564.html
跳跃表是一种可以替代平衡树的数据结构，跳跃表让已经排序好的数据分布在多层次的链表中，
默认是将key值升序排列，以0到1决定一个数字是否爬升到高层次到链表中。
它通过容许一些数据到冗余，达到以"空间换时间"的目的
跳跃表的效率和 AVL 相媲美，查找、添加、插入、删除操作都能够在 O(LogN) 的复杂度内完成
规则
一个跳跃表应该有若干个层（Level）链表组成；
- 跳跃表中最底层的链表包含所有数据； 每一层链表中的数据都是有序的；
- 如果一个元素 X 出现在第i层，那么编号比 i 小的层都包含元素 X；
- 第 i 层的元素通过一个指针指向下一层拥有相同值的元素；
- 在每一层中，-∞ 和 +∞ 两个元素都出现(分别表示 INT_MIN 和 INT_MAX)；
- 头指针（head）指向最高一层的第一个元素；
树记录
树有以下种类：
多叉树->平衡多路搜索树-> B(Balanced Tree)树、与B+树
二叉树->二叉搜索树（BST二叉排序树）->普通二叉搜索树
->平衡二叉搜索树 红黑树与AVL树
树
度
结点拥有的子树称为结点的度，
树的度为树内各节点的度的最大值
叶子
度为0的节点为叶子节点
结点
结点的子树称为该结点的孩子
层次
结点的层次从根开始定义，根为第一层，根的孩子为第二层
树的最高层次为树的高度(根节点的高度)
树的存储结构
a
b c
双亲表示法
在每个结点中，加个父结点在数组中的位置
下标 data parent
0 a -1
1 b 0
2 c 0
缺点：无法知道结点的孩子结点有那些，需要遍历整个数组
孩子表示法
数组+单链表存储，头指针放到线性表里面，叶子节点做成单链表
下标 data firstchild
0 a 链表[1]->[2]
1 b 无
2 c 无
优点：要查询某个结点的孩子或者兄弟 很方便
缺点：无法知道某个结点的父结点
双亲孩子表示法
在孩子表示法基础上加个父辈结点的索引
下标 data parent firstchild
0 a -1 链表[1]->[2]
1 b 0
2 c 0
二叉树
二叉树是树的另外一种树形结构，
二叉树的特点：每个结点最多有两颗树，子树有左右之分
二叉树存储结构
顺序存储结构
适用于完全二叉树，对于一般的二叉树会浪费存储空间
缺点：查询父子结点不方便
下标 1 2 3 4 5
a b c d e
二叉链表
二叉树的每个结点最多有两个孩子，所以设计一个数据域与两个指针域
满二叉树
一颗树深度为h，最大层数为k，深度与最大层数相同，k=h;
叶子数为2h;
第k层的结点数是：2^k-1;;
总结点数是：2^k-1，且总节点数一定是奇数。
完全二叉树
如果一个二叉树与满二叉树前m个节点的结构相同，这样的二叉树被称为完全二叉树
二叉排序树（二叉排序树）
任何节点的键值一定大于其左子树中的每一个节点的键值，并小于其右子树中的每一个节点的键值。
平衡二叉树
当左右节点数量接近，这棵树就越平衡，一般平均的二叉树时间复杂度可以认为是树的高度
也就是o(h)=O(logn)
4
2 6
1 3 5
当二叉树退化成链表的时候性能会变成O（N）
1
2
3
4
5
6
所以二叉树要有平衡的概念，才会引出来后面的红黑树与AVL树
AVL树
特点：
具有二叉查找树的全部特性。
每个节点的左子树和右子树的高度差至多等于1。
在插入的过程中，会出现一下四种情况破坏AVL树的特性，我们可以采取如下相应的旋转。
1、左-左型：做右旋。
2、右-右型：做左旋转。
3、左-右型：先做左旋，后做右旋。
4、右-左型：先做右旋，再做左旋。
插入和删除操作中需要大量且复杂的操作来保持ALV树的平衡（左旋和右旋），
因此ALV树适用于大量查询，少量插入和删除的场景中
参考：https://mp.weixin.qq.com/s/dYP5-fM22BgM3viWg4V44A
红黑树
大量查询，大量插入和删除，现在使用ALV树就不太合适了，
因为ALV树大量的插入和删除会非常耗时间，那么我们是否可以降低ALV树对平衡性的要求从而达到快速的插入和删除呢
二叉树排序前序、中序、后序
二叉树排序（根节点和孩子结点，子树是指最子的叶子结点）
前序：遍历顺序为，根节点、前序遍历左子树、前序遍历右子树；
中序：遍历顺序为，中序遍历左子树、根节点、中序遍历右子树；
后序：遍历顺序为，后序遍历左子树左子树、后序遍历左子树右子树、根节点
如上图的根为A ,左子树为（bde）, 右子树为（cf）,
前序（根左右）,a 再对左子树进行前序就是（b,d,e）, 再对右边子树就是cf
中序（左根右），左子树为中序就是（dbe）,a ,右子树中序就是（fc）
后序（左右根），左子树后续就是（deb）,右边子树就是（fc） a
如上图的根为1 ,左子树为（24678）, 右子树为（35）,
前序（根左右）,1 再对左子树进行前序就是（2，4，678，）, 再对右边子树就是（35）
中序（左根右），左子树为中序就是（4，768，2）,1 ,右子树中序就是（35）
后序（左右根），左子树后续就是（786，4，2）,右边子树就是（53） 1
B树
是一种平衡的多路搜索树，一般用户文件系统，数据库实现
B-树
我们知道二叉查找树查询的时间复杂度是O（logN），查找速度最快和比较次数最少，既然性能已经如此优秀，
但为什么实现索引是使用B-Tree而不是二叉查找树，关键因素是磁盘IO的次数, 减少磁盘IO的次数就必须要压缩树的高度，
让瘦高的树尽量变成矮胖的树，所以B-Tree就在这样伟大的时代背景下诞生了。
首先B-Tree是为磁盘等外存储设备设计的一种平衡查找树。因此在讲B-Tree之前先了解下磁盘的相关知识。
系统从磁盘读取数据到内存时是以磁盘块（block）为基本单位的，位于同一个磁盘块中的数据会被一次性读取出来，
而不是需要什么取什么
InnoDB存储引擎中有页（Page）的概念，页是其磁盘管理的最小单位。InnoDB存储引擎中默认每个页的大小为16KB
而系统一个磁盘块的存储空间往往没有这么大，因此InnoDB每次申请磁盘空间时都会是若干地址连续磁盘块来达到页的大小16KB。
InnoDB在把磁盘数据读入到磁盘时会以页为基本单位，在查询数据时如果一个页中的每条数据都能有助于定位数据记录的位置，
这将会减少磁盘I/O次数，提高查询效率
B-Tree结构的数据可以让系统高效的找到数据所在的磁盘块。为了描述B-Tree，首先定义一条记录为一个二元组[key, data]
，key为记录的键值，对应表中的主键值，data为一行记录中除主键外的数据。对于不同的记录，key值互不相同
m阶B-Tree满足以下条件：
1、每个节点最多拥有m个子树
2、根节点至少有2个子树
3、分支节点至少拥有m/2颗子树（除根节点和叶子节点外都是分支节点）
4、所有叶子节点都在同一层、每个节点最多可以有m-1个key，并且以升序排列
B+树
B+Tree是在B-Tree基础上的一种优化，使其更适合实现外存储索引结构，InnoDB存储引擎就是用B+Tree实现其索引结构
B-Tree结构图中可以看到每个节点中不仅包含数据的key值，还有data值。而每一个页的存储空间是有限的，
如果data数据较大时将会导致每个节点（即一个页）能存储的key的数量很小，
当存储的数据量很大时同样会导致B-Tree的深度较大，增大查询时的磁盘I/O次数，进而影响查询效率。
在B+Tree中，所有数据记录节点都是按照键值大小顺序存放在同一层的叶子节点上，
而非叶子节点上只存储key值信息，这样可以大大加大每个节点存储的key值数量，降低B+Tree的高度。
B+Tree是B树的变种，有着比B树更高的查询性能，来看下m阶B+Tree特征：
1、有m个子树的节点包含有m个元素（B-Tree中是m-1）
2、根节点和分支节点中不保存数据，只用于索引，所有数据都保存在叶子节点中。
3、所有分支节点和根节点都同时存在于子节点中，在子节点元素中是最大或者最小的元素。
4、叶子节点会包含所有的关键字，以及指向数据记录的指针，并且叶子节点本身是根据关键字的大小从小到大顺序链接。
B+Tree与B-Tree区别
非叶子结点的子树指针与关键字个数相同；
非叶子结点的子树指针P[i]，指向关键字值属于[K[i], K[i+1])的子树（B-树是开区间）；
为所有叶子结点增加一个链指针；
非叶子节点只存储键值信息，不存储data；叶子节点不存储指针
所有关键字都在叶子结点出现；
为什么数据索引用B+tree
1、更加高效的单元素查找，与二叉树相比可以大幅度减少IO次数，与B树相比，因为B+树的数据都是存在叶子节点的，
所以同样大小的磁盘页可以容纳更多的节点元素
2、叶子节点形成有顺链表，范围查找性能更优
比如查询3到8的数据，如果是二叉树或者b树，io次数会远大于B+树
图
图按照有无方向分为 无向图与有向图
无方向图由顶点和边组成
图的存储结构
领接矩阵
{1 若Vy可以访问到Vj 则为1
a[i][j]=
{0 反之为0
v0-> v1,v2,v3
v1->v0,v2
v2->v1,v3
v3->v0,v2
顶点数组 v0,v1,v2,v3
边数组
v0 v1 v2 v3
v0 0 1 1 1
v1 1 0 1 0
v2 1 1 0 1
v3 1 0 1 0
查找算法
查找定义：根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素（或记录）。
查找算法分类：
1）静态查找和动态查找；
静态或者动态都是针对查找表而言的。动态表指查找表中有删除和插入操作的表。
2）无序查找和有序查找。
无序查找：被查找数列有序无序均可；
有序查找：被查找数列必须为有序数列
顺序查找
从数据结构线形表的一端开始，顺序扫描，依次将扫描到的结点关键字与给定值k相比较，若相等则表示查找成功；若扫描结束仍没有找到关键字等于k的结点，表示查找失败。
时间复杂度为O(n)
二分查找
说明：元素必须是有序的，如果是无序的则要先进行排序操作。
也称为是折半查找，属于有序查找算法。用给定值k先与中间结点的关键字比较，中间结点把线形表分成两个子表，若相等则查找成功；
若不相等，再根据k与该中间结点关键字的比较结果确定下一步查找哪个子表，这样递归进行，直到查找到或查找结束发现表中没有这样的结点
时间复杂度为O(log2n)
场景场景
海量数据场景
海量无重复数据排序
例如电话号码排序，可以使用bitMap
假设有一个数组有10亿个int需要排序，如果使用传统的格式那就需要10*4/(1024*1024*1024)=3.72G左右
如果使用bitMap算法，将int值存放到bit对应的位上面去，可以节省32倍空间
海量重复数据求排序
1、先hash,切割多个文件，然后再每个文件排序，再合并各个文件
海量重复数据求topK
1、对数据进行hash 然后取模分配到不同文件。
2、维护一个topK的最小堆， 依次读取每个文件里面的的记录，如果次数小于堆顶就丢弃
算法的时间复杂度：
分小文件 O(n)
hashmap统计 O(n)
维护最小堆 O(n'logK) n'是不同的单词数，K是topK
两个海量数据取重复记录
1、先hash，然后取模到多个文件，然后再挨个比较每个文件。
在2.5亿个整数中找出不重复的整数
采用2-Bitmap（每个数分配2bit，00表示不存在，01表示出现一次，10表示多次，11无意义）进行