持续更新
三个渐近复杂度符号：
$\Theta：紧确界\quad O：上界\quad \Omega：下界$
哨兵
在首或尾增加哨兵等于目标，循环中寻找目标时不管索引是否超过界限，找到目标再查看索引是哨兵的索引还是真正目标的索引。
KMP算法
求模式串的失配链接值是关键。向下取整floor(小于但是最大)和向上取整(大于但是最小)celling
三元组表的快速转置
找出原表中每行/每列第一个元素转置后在新表中的位置，记录在cpot[]数组中，num[]数组记录源矩阵中每列非零元素的个数。关键是保持三元组的次序-即按行/按列排序。
三元组和十字链表
选用十字链表是为了在稀疏矩阵间需要运算，而两稀疏矩阵非零元素位置差异较大，每次运算都需要移动大量元素的位置，耗时耗力，所以利用链表特性存储稀疏矩阵。
重连通图
关节点是指图中某点，当删除此点及其关联边时，图的一个连通分量会被分割为两个或以上连通分量。无关节点的图为重连通图，重连通图中，任一顶点到其它顶点有两条及以上路径。若在连通图上至少需要删除k个顶点才能破坏图的连通性则称图的连通度为k。系统的连通度越高越安全。(电路设施、通信网络、物资运输线路)
图的最小路径算法
Dijkstra算法：
建立最短路径数组，元素值表示当前顶点到数组下标对应顶点的最短距离。同时建立bool数组记录某顶点是否已经被提取过。初始化bool数组为全false，初始化最短路径数组为源点到各顶点直接距离，不存在直接边则距离为无穷大。然后从当前最小距离数组中寻找最小距离，确定这个这个最小的最小距离对应的顶点，将其在bool数组中置为已提取(true)在邻接矩阵中依次比较此顶点到其它未提取顶点距离与当前最小的最小距离之和与最小距离数组中对应到各顶点的最小距离，若前者更小则替换之，更新最小距离数组(比较次数每个循环会减一)，然后继续寻找最小的最小距离(去除已提取的顶点)。 但是这里面没有记录到每个顶点最小距离的相对应路径。可以置路径数组用来记录到达对应数组元素下标的顶点的上一个结点。 path[j] = min_num;path[j]记录d[j]暂时最短路径的最后一个中途节点min_num，表明d[j]最后一段从节点min_num到节点j，而到结点j的路径自然会由其它最短路径记录，由此可以达到记录路径的目的。
最小生成树算法
Prim算法
从任一顶点开始建立顶点集和空边集，利用辅助数组记录当前顶点集到图顶点集各点的最小距离，初始化也即为初始顶点到其余各顶点的距离(数组元素是结构体，包括邻接顶点和最小距离，不存在边时距离记为无穷大，到自己的距离记为0)，然后循环n-1次，每次增加一条边和一个顶点，该边是辅助数组中最小的最小距离(增加顶点的形式是把辅助数组对应位置的最小距离置零，增加边是打印该点在数组中的邻接顶点值和该点的值)，然后更新辅助数组，用新顶点和图中其它顶点的距离比较当前对应位置最小距离，若更小则更新邻接顶点为当前顶点并更新最小距离，然后重复下一次循环。如此可以保证辅助数组中的最小距离始终是当前顶点集到图中其余顶点的最小距离，并能记录是当前顶点集的哪一个顶点到图中顶点距离最小，如此循环n-1次就能添加完所有的必要边。复杂度为$O(n^2)$，与边数无关，适合稠密图。
Kruskal算法(避圈法)
初始状态最小生成树为n个顶点无边的非连通图，连通分量为n，每次选择代价最小并能减少一个连通分量的边，直至所有顶点共属一个连通分量。需要利用堆对图中所有边按长进行排序，从小到大依次处理，并利用辅助数据结构并查集(数组即可，不同的连通分量记为不同序号值)检查新边的两顶点是否属于同一连通分量。
- 破圈法
- 索林(
Sollin)算法：类似聚类的凝聚法，合并平凡树
寻找有向图的强连通分量
Tarjan算法
寻找图的最大匹配
匈牙利算法
二叉排序树
AVL树(二叉平衡树)
任意结点左右子树平衡因子满足$-1\leq 平衡因子 \leq 1$
B树
2-3树
B+树：
求欧拉图中欧拉回路的算法：
- Fleury算法：能不走桥就不走桥
- 逐步插入回路法
货郎担问题：
利用哈希表的滑动窗口字符串匹配——Robin-Karp算法
把pattern作整体计算哈希值，类比处理母串，滑动处理。
Huffman算法
求带权最优二叉树
递归思想及原则：
- 函数调用其自身（直接的或间接的都算）
- 有明确的终止条件
尾递归(函数所做的最后一件事情是一个函数调用（递归的或者非递归的)可以大大减少栈空间的占用
线段树
回溯和深度优先搜索dfs
遍历所有当前选择（做出选择，记录选择，下一次选择（递归），回退选择）
1、路径：也就是已经做出的选择。
2、选择列表：也就是你当前可以做的选择。
3、结束条件：也就是到达决策树底层，无法再做选择的条件。
关联分析
还没看
