why n(n-1)/2 = (n-1)+(n-2)+...+1 ~ N*N/2
http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/runsums/triNbProof.html
图-广度优先运行时间为 边数+顶点数 能够有效找出边数最少的，但找出的不一定是总值最小的
Dijkstra's Algorithm 适用于 "非负权边的有向图"
有负权边的可以使用 贝尓曼-福德(bellman-ford) 算法
贪婪算法：每个局部最优解逐步完成到全局，就可以认为是全局最优解
数学上，给定集合 S，其幂集是以 S的全部子集为元素的集合
https://zh.wikipedia.org/wiki/%E5%86%AA%E9%9B%86 2的n次方
NP完全问题的简单定义是，以难解著称的问题，如旅行商问题和集合覆盖问题
怎样判断NP问题：
1.元素较少时算法的运行速度非常快，但随着元素数量的增加，速度会变得非常慢。
2.涉及 "所有组合" 的问题通常是NP完全问题。
不能分解为小问题的，必须考虑各种情况的。可分的用动态规划
3.如果问题涉及序列（如旅行商问题中的城市序列）且难以解决，它 "可能" 就是NP完全问题。
4.如果问题涉及集合（如广播台集合）且难以解决，它 "可能" 就是NP完全问题。
5.如果问题可转换为集合覆盖问题或旅行商问题，那它 "肯定" 是NP完全问题。
旅行商问题与最短路径问题的区别：https://www.zhihu.com/question/270419595
动态规划：
1.从网格开始（行为各商品[每一行表示之前所有商品]，列为从小到大各种容量的背包，值为价值）
2.cell[i][j] = max(cell[i-1][j], 当前商品价值+cell[i-1][j-当前商品重量])
贪婪算法不同：贪婪是每次都拿最高的，直到不能拿
动态规划用于解决离散的，不会互相依赖的子问题
推荐系统：k最近邻算法
更好的方案为 余弦相似度 KNN
* selection sort 选择排序 N*N/2 次比较，N次交换
开始时整个数列为扫描列表。
每次扫描找出当前扫描列表中最小的那个，交换移到扫描列表最前，然后排除出扫描列表
循环至扫描列表长度为1结束
特点1：运行时间与输入无关，无论何种输入排序时间相差无几。上一次扫描无法为下一次扫描提供可用的信息
特点2：数据移动少，交换次数与数组大小是线性关系
* insert sort 插入排序平均 N*N/4 次比较与交换，最差情况为 N*N/2 次比较与交换，最好为 N-1 比较 0 交换
对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。未排序数组逐渐减少。
因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
特点1：与输入有关，越接机排序顺序的输入序列所用时间越短
特点2：如果要优化着重于减少移动的操作次数（比如用向右平移代替元素两两交换）
* shell sort 希尔排序 https://zh.wikipedia.org/wiki/%E5%B8%8C%E5%B0%94%E6%8E%92%E5%BA%8F 使用列的模式更容易理解
希尔排序是基于插入排序的以下两点性质而提出改进方法的：
1.插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率（越后期越有序）
2.但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位（按间隔组成子数组进行插入排序，移动位置较远，能更快达到最终位置）
中心思想是使数组中间隔为 n(n逐步减少) 的元素组成的子数组都是有序的
最好步长算式：
9*(Math.pow(4,i)) - 9*(Math.pow(2,i)) + 1 => 1，19，109，505...
Math.pow(2,i+2) * (Math.pow(2,i+2)-3) + 1 => 5，41，209，929...
result => 1, 5, 19, 41, 109...
特点1：比较在希尔排序中是最主要的操作，而不是交换。
特点2：用这样步长序列的希尔排序比插入排序要快，甚至在小数组中比快速排序和堆排序还快，但是在涉及大量数据时希尔排序还是比快速排序慢。
* merge sort (sub) 归并排序
merge 函数：
接收数组A，全拷贝至另一数组B，B数组分2段[逻辑上,各自要有序]，分别给予变量 i,j 进行索引。
比较 B[i],B[j], 较小的值写回 A，较小的索引变量自增。
某一索引先到其逻辑上分段尾部时，另一段剩余的直接全部写回 A
主要缺点是需要额外空间来归并跟 N 成正比 (归并2个已排序数组的操作其实可以使用各种方式)
由于排序路径跟二叉树相似，所以时间跟 NlgN 成正比
自顶向下的排序算法就是把数组元素不断的二分，直到子数组的元素个数为一个，因为这个时候子数组必定是已有序的。
然后将两个有序的序列合并成一个新的有序的序列，两个新的有序序列又可以合并成另一个新的有序序列，以此类推，直到合并成一个有序的数组
最坏 NlgN，最好 1/2N*lgN。一共在logN个维度上进行比较，每个维度最多需要比较N次，最少比较N/2次(一方都比另一方小)
最多访问 6NlgN 次数组，拷贝数组2N[原数组与新数组], 赋值2N[两数组之间], 比较2N[应该只有1N?]
自底向上的归并排序算法的思想就是数组中先一个一个归并成两两有序的序列（不需要递归分割，直接扫描两两处理）。
两两有序的序列归并成四个四个有序的序列，然后四个四个有序的序列归并八个八个有序的序列，以此类推直到归并的长度大于整个数组的长度，此时整个数组有序。
* quick sort
结合了额外空间小（可以原地）和 NlgN 复杂度（快速）的特点
该算法还可以进一步改进
当数组长度小于M的时候（high-low <= M），终止递归不进行快排，而进行插排
转换参数M的最佳值和系统是相关的，一般来说，5到15间的任意值在多数情况下都能令人满意
三数取中法(取比较基准)：分别取出数组的最左端元素，最右端元素和中间元素，在这三个数中取出中位数，作为基准元素。
对于大量重复元素的数组，不同于普通的两切分，甚至可以考虑三切分 [ 小于x1 (x1) 大于x1小于x2 (x2) 大于x2 ]
* heap sort
构造堆: 如果是二叉堆，堆（二叉堆）可以视为一棵完全的二叉树。可用数组索引表示堆情况，构造完后此时最大元素在顶部
如果数组索引0放第一个元素，则
父节点i的左子节点在位置 2i+1;
父节点i的右子节点在位置 2i+2;
子节点i的父节点在位置 floor((i-1)/2);
如果索引0放空，则 2i，2i+1，floor(i/2)
最大堆调整（Max-Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点
创建最大堆（Build-Max-Heap）：将堆所有数据重新排序，使其成为最大堆
堆排序（Heap-Sort）：移除位在第一个数据的根节点，最后的节点移到空缺处，并做最大堆调整的递归运算
能平衡有效的利用空间与时间，但由于无法缓存，所以使用较少
稳定排序：插入排序，归并排序
原地排序：除了归并排序都可以
算法： 时间复杂度 空间复杂度
选择排序 N平方 1
插入排序 N~N平方 1 依赖输入数据
希尔排序
快速排序 NlogN lgN
并归排序 NlogN N
堆排序 NlogN 1(因为用本身的数组来表示堆)
* 二叉查找树 BST：
也称二叉搜索树，有序二叉树，排序二叉树
左子树上所有节点的值均小于它的根节点的值，右子树上所有节点的值均大于它的根节点的值，没有键值相等的节点
在进行插入操作时，不必移动其它结点，只需改动某个结点的指针（不需要旋转调整）
树层级较高时，查找效率较低
范围查询使用中序遍历
删除节点：由于二叉查找树的性质，如果将当前节点替换为左子树中最大的或者右子树中最小的一定不会破坏二叉查找树的结构
* 平衡查找树 [能够保证在最差的情况下也能达到lgN的效率]：
其中有以下实现：
2-3搜索树，2-3-4树，红黑树，AVL树等
* 2-3 搜索树
任一节点只能是 2-结点 或 3-结点 [2-结点：一个键(值)二条链接，3-结点：两个键三条链接]
各叶子节点到根节点距离相同
插入时：
2-结点 之间插入变为 3-结点
3-结点 临时创建为 4-结点 后中心元素上提，并不断递归向上提(消除4-结点)
由于这种性质，树是由下向上生长。
* 红黑树：
由二叉查找树(全 2-结点)+额外信息(红黑数据)来表示
节点是红色或黑色。根和叶子是黑色。每个红色节点必须有两个黑色的子节点。
从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点
好处是可以用二叉树的方法查找(简洁高效)，并且表示出 2-3树(平衡查找树) 因为是黑色平衡的(每条路径黑链数相同)
进行添加或删除后，通过左旋或右旋保证上述红黑树的性质
z
x /
/ \ --(左旋)--> x 旋转后仍然保持原二叉树的性质
y z /
y
y
x \
/ \ --(右旋)--> x
y z \
z
红黑树结点的插入：
1.作为普通二叉树插入结点
2.着色为红色，然后调整树满足上述关系（分不同几种情况递归进行旋转与重新着色处理）
[如果设为黑，根到叶子路径上多个额外黑节点，很难调整。设为红，可能会出现连续红色的冲突，可以通过颜色调换和树旋转来调整]
红黑树结点的删除：
1.作为普通二叉树删除结点
2.然后调整树满足上述关系（分不同几种情况递归进行旋转与重新着色处理）
https://zh.wikipedia.org/wiki/%E7%BA%A2%E9%BB%91%E6%A0%91
* 无向图
连通分支（Connected Component）是指：在一个图中，某个子图的任意两点有边连接，并且该子图与去掉该子图剩下的任何点都没有边相连
强连通分支是指子图点i可以连接到点j，同时点j也可以连接到点i。
弱连通（只对有向图）分支是指子图点i可以连接到点j，但是点j可以连接不到点i。
图的表示有以下3种
* 深度优先
* 广度优先（原理用先进先出队列，结果路径可能较短）
无向图的生成树：具有该图所有顶点，同时边数最少的子图，一个图的生成树可能有多个
加权无向图: 边上有对应的权重
最小生成树: 是一副连通加权无向图中一棵权值最小的生成树
Prim算法是用于解决最小生成树的算法之一
延时版：
将顶点0添加到最小生成树中,将它的邻接表中的所有边添加到优先队列中(将横切边添加到优先队列).
将顶点7和边0-7添加到最小生成树中,将顶点的邻接表中的所有边添加到优先队列中.
将顶点1和边1-7添加到最小生成树中,将顶点的邻接表中的所有边添加到优先队列中.
将顶点2和边0-2添加到最小生成树中,将边2-3和6-2添加到优先队列中,边2-7和1-2失效.
将顶点3和边2-3添加到最小生成树中,将边3-6添加到优先队列之中,边1-3失效.
将顶点5和边5-7添加到最小生成树中,将边4-5添加到优先队列中,边1-5失效.
从优先队列中删除失效边1-3,1-5,2-7. [为什么不前面的操作时直接删?]
将顶点4和边4-5添加到最小生成树中,将边6-4添加到优先队列中,边4-7,0-4失效.
从优先队列中删除失效边1-2,4-7,0-4. [为什么不前面的操作时直接删?]
将顶点6和边6-2添加到最小生成树中,和顶点6关联的其他边失效.
在添加V个顶点与V - 1条边之后,最小生成树就构造完成了,优先队列中剩余的边都为失效边
即时版：
将顶点0添加到最小生成树之中,将它的邻接表中的所有边添加到优先队列中(这些边是目前唯一已知的横切边).
将顶点7和边0-7添加到最小生成树,将边1-7和5-7添加到优先队列中,将连接顶点4与树的最小边由0-4替换为4-7.
将顶点1和边1-7添加到最小生成树,将边1-3添加到优先队列.
将顶点2和边0-2添加到最小生成树,将连接顶点6与树的最小边由0-6替换为6-2,将连接顶点3与树的最小边由1-3替换为2-3.
将顶点3和边2-3添加到最小生成树.
将顶点5和边5-7添加到最小生成树,将连接顶点4与树的最小边4-7替换为4-5.
将顶点4和边4-5添加到最小生成树.
将顶点6和边6-2添加到最小生成树.
在添加了V - 1条边之后,最小生成树构造完成并且优先队列为空.
Kruskal算法
按照边的权重顺序（从小到大）将边加入生成树中，但是若加入该边会与生成树形成环则不加入该边。
* 有向图
强连通图: 指每一个顶点皆可以经由该图上的边抵达其他的每一个点的有向图
强连通分量: 指一张有向图G的极大强连通子图G'
极大强联通子图：一个图的（强）连通子图，并且加入任何一个不在它的点集中的点都会导致它不再（强）连通
有向无环图（DAG图）: 一个有向图从任意顶点出发无法经过若干条边回到该点
* 深度优先遍历后
背向边：如（A，B）和（I，H）
前向边：如（C，D）和（C，E），它们从树的一个节点通向一个后裔；
交叉边：如（F，C）和（G，F），它们把不直接相关的两个树节点连接起来；
一个有向图是无圈图当且仅当它没有背向边
* 最短路径问题
Dijkstra(广度优先的动态规划,存在负数环会失效), Bellman–Ford(能算最短路径，也可以检测负数环,n-1 次循環，不断利用已經找到的最短路徑去更新其它點的)
https://www.cs.usfca.edu/~galles/visualization/Dijkstra.html
https://www-m9.ma.tum.de/graph-algorithms/spp-bellman-ford/index_en.html
基础：计数排序、基数排序
-----------------------------
计数排序：
首先会对每个输入进行频率统计，得到元素的频率表
例子：[9, 7, 6, 3, 9, 2, 7, 3, 2, 8]排序，最小元素2/最大元素9
元素 频率(出现次数)
2 2
3 2
4 0
5 0
6 1
7 2
8 1
9 2
每个元素减去最小值再加1作为索引，使用一个count[]表示上表
count[] = {0, 2, 2, 0, 0, 1, 2, 1, 2}
元素 开始索引
2 0
3 2
4 4 (实际不存在这个元素)
5 4 (实际不存在这个元素)
6 4
7 5
8 7
9 8
对于不存在的元素，使用下一个元素的开始索引，某元素的开始索引恰好是小于它的元素个数
{0, 2, 4, 4, 4, 5 ,7, 8}
利用count[]数组，可以根据每个元素的开始索引，一个个将其填充到临时数组中的对应位置，最后再将临时数组中的数据写回原数组即可
原数组排序后是[2, 2, 3, 3, 6, 7, 7, 8, 9, 9]
-----------------------------
基数排序(radix-sort)：
比如对于数字2985，从右往左就是先以个位为关键字进行排序，然后是十位、百位、千位，总共需要四轮。
一定要注意每一轮排序中排序方法必须是稳定的。否则基数排序不能得到正确的结果
目的是在较高位字符相同的情况下，保持着较低位的顺序；在较高位字符不同的情况下，保证较高位要有序，低位的顺序已经没有意义
低位优先（Least-Signifcant-Digit First，LSD）的字符串排序
要求被排序的每个字符串长度都相等
从字符串的右边开始向左检查字符（相当于从数字的最低位到高位）
高位优先（Most-Significant-Digit First，MSD) 的字符串排序
不要求被排序的字符串等长
不一定需要检查所有的输入就能完成排序
该算法将从左开始向右检查字符（就像通常我们比较字符串那样）
使用和"快速排序"类似的方法将字符串排序
----------------------
Three-way string quicksort
MSD的基础上，我们可以按照每个位置的字符作为比较元素，然后划分为3个partition。
根据之前所了解的三路快排，我们知道中间的那份partition包含的元素是相同的，因此在进行子问题递归的时候，比较元素的位置+1。
而另外两个，则继续在该位置上进行子问题计算
一个节点的所有子孙都有相同的前缀，也就是这个节点对应的字符串，而根节点对应空字符串
一般情况下，不是所有的节点都有对应的值，只有叶子节点和部分内部节点所对应的键才有相关的值
trie树常用于搜索提示。如当输入一个网址，可以自动搜索出可能的选择。当没有完全匹配的搜索结果，可以返回前缀最相似的可能
词频：用一个整型变量count来计数。对每一个关键字执行插入操作，若已存在，计数加1，若不存在，插入后count置1
KMP算法：
KMP算法的本质是构造一个DFA（确定性有限状态自动机）
然后通过自动机对输入的字符串进行处理，每接收一个字符，就能转移到一个新的状态。
如果自动机能够达到特定的状态，那么就能够匹配字符串，否则就匹配失败。
朴素[暴力]查找算法在查找的时候，其实文本字符串的某些字符在前面就已经能获取相关的信息了
但是因为算法的局限，为了不漏掉中间能够匹配的字符，下一次回退的时候，又重新匹配了一次或多次，这样浪费了一定的时间
相比朴素的查找算法，KMP的优势在于，基本流程是一致的，不需要进行不必要的回退操作。
它是用一个dfa数组（有地方叫做Next数组）来指示匹配失败的时候下一步j应该放到哪，也就是对齐的位置
这个位置不一定是朴素查找算法中的右移的一位，可能是多位，效率更高
DFA[r][j] 行是匹配串字母表，列是索引 DFA[r][j] 表示"在已匹配 j 个字符时，若当前字符串字母为 r ，已匹配数量会变成多少"
动态规划
匹配过程：
private final int R; // the radix
private int[][] dfa; // the KMP automoton
private String pat;
public KMP(String pat) {
this.R = 256; //设置字典大小
this.pat = pat;
//构造pat对应的dfa
int M = pat.length();
dfa = new int[R][M];
dfa[pat.charAt(0)][0] = 1;
for (int X = 0, j = 1; j < M; j++) { //X记录匹配失败时的索引位置,j指向pat
for (int c = 0; c < R; c++) { //对于匹配失败的情况，直接复制重启状态
dfa[c][j] = dfa[c][X];
}
dfa[pat.charAt(j)][j] = j + 1; //匹配成功的指向下一个状态
X = dfa[pat.charAt(j)][X]; //更新重启位置X
}
}
boyer-moore算法；
http://www.ruanyifeng.com/blog/2013/05/boyer-moore_string_search_algorithm.html
=============================================
正则，DFA，NFA
NFA，Nondeterministic Finite Automata，不确定的有限状态自动机。
要先理解FA先，也就是有限状态自动机，其实就是个识别器，只能对每个可能的输入串简单地回答“是”或“否”。
然后NFA是一种FA，其特点是在某个状态S下输入某个字符a，可以进入多个不同状态，还有就是空串ε也可以作为输入字符标号。
DFA，Deterministic Finite Automata，确定的有限状态自动机。
是一种特殊的NFA，因为DFA规定了每个状态对每个字符输入只有一个后继状态，而且不用空串ε作为输入字符，其余和NFA一样。
而DFA更方便计算机去运算执行。嗯，至于NFA，则是正则表达式转DFA中间的一个过渡图。因为一步到位搞不定，而且有时候ε作为输入是蛮方便的
http://www.evanlin.com/moocs-coursera-automata-note1/
霍夫曼编码：
变长编码表是通过一种评估来源符号出现机率的方法得到的，出现机率高的字母使用较短的编码，反之出现机率低的则使用较长的编码
霍夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。使用自底向上的方法构建二叉树，权重越大的字符出现在越高的地方
example:
encode => we will we will r u
字符 频率
=== ===
null 5
w 4
l 4
e 2
i 2
r 1
u 1
按出现频率高低将其放入一个优先级队列中: u, r, i, e, l, w, [null] min -> max
构造二叉树：
empty(2), i(2), e(2), l(4), w(4), [null](5)
/ \
u(1) r(1)
empty(4), e(2), l(4), w(4), [null](5)
/ \
empty(2) i(2)
/ \
u(1) r(1)
4 > 2,调整位置
e(2), empty(4), l(4), w(4), [null](5)
/ \
empty(2) i(2)
/ \
u(1) r(1)
循环直至构建完成
字符 编码
=== ===
null 10
w 01
l 00
e 110
i 1111
r 11101
u 11100
we will we will r u =>
01 110 10 01 1111 00 00 10 01 110 10 01 1111 00 00 10 11101 10 11100
还有 LZW字典 和 算数编码 2种方式 https://segmentfault.com/a/1190000011425787
后缀数组：用于求最长公共子串