算法分类.md

前言

ACM相关的算法有很宽的广度和很高的深度，如果只是为了锻炼编程能力、辅助理解计算机的运行原理，不需要在每个方向都钻研清楚，而只梳理出一些基础的、常见的、有代表意义的，侧重训练下，就可以了。

以下是从网络上找到的算法分类，做了一些调整，加上注解。

算法分类

原文：https://www.cnblogs.com/zxj015/archive/2011/04/12/2740239.html

1. 时间复杂度（渐近时间复杂度的严格定义，NP问题，时间复杂度的分析方法，主定理）

时间复杂度是需要时刻关注的，要保持足够的敏感性。平常写代码做了某种决策，用到某种容器，做了某种操作，要能大概地感觉到对应的时间复杂度、空间复杂度。

如果是做题目，根据题目给的条件、限制，就要能大概猜到符合要求的算法复杂度，再枚举符合这种复杂度的算法，一个个去匹配看是否能解题。

主定理：一个推导递推算法复杂度的定理，参考：http://www.voidcn.com/article/p-dxexrxys-bmd.html

2. 排序算法（平方排序算法的应用，Shell排序，快速排序，归并排序，时间复杂度下界，三种线性时间排序，外部排序）

要熟悉各种排序，能手写快速排序、归并排序、堆排序(也就是能手写堆结构)。

3. 数论（整除，集合论，关系，素数，进位制，辗转相除，扩展的辗转相除，同余运算，解线性同余方程，中国剩余定理）

不需要做太深入的题目。同余方程、中国剩余定理不需要涉及。了解什么是交集、并集、笛卡尔乘积。实现寻找素数的筛法。

4. 指针（链表，搜索判重，邻接表，开散列，二叉树的表示，多叉树的表示）

需要熟练掌握。要掌握二级(双重)指针。了解一个操作技巧：二级指针实现链表删除 (https://coolshell.cn/articles/8990.html) 。

5. 按位运算（and，or，xor，shl，shr，一些应用）

需要熟悉定义。

6. 图论（图论模型的建立，平面图，欧拉公式与五色定理，求强连通分量，求割点和桥，欧拉回路，AOV问题，AOE问题，最小生成树的三种算法，最短路的三种算法，标号法，差分约束系统，验证二分图，Konig定理，匈牙利算法，KM算法，稳定婚姻系统，最大流算法，最小割最大流定理，最小费用最大流算法）

只需要关注：图的矩阵表示、邻接表表示；最短路算法(三种)、最小生成树算法(三种)、KM算法、求强连通分量、并查集

这块算法在理解原理以后，应用都比较机械，难度不会太高，但是很适合锻炼编程能力。

7. 计算几何（平面解几及其应用，向量，点积及其应用，叉积及其应用，半平面相交，求点集的凸包，最近点对问题，凸多边形的交，离散化与扫描）

简单了解即可，不需要深入。

8. 数据结构（广度优先搜索，验证括号匹配，表达式计算，递归的编译，Hash表，分段Hash，并查集，Tarjan算法，二叉堆，左偏树，二斜堆，二项堆，二叉查找树，红黑树，AVL平衡树，Treap，Splay，静态二叉查找树，2-d树，线段树，二维线段树，矩形树，Trie树，块状链表）

重点学习。

Hash表、哈希算法很重要，需要深入了解。但做OJ题目很少会遇到Hash表相关的，Leetcode可能会有一些。

红黑树往后的数据结构可以不管。但红黑树、AVL数需要了解(what、why、how)。线段树了解下，题目不用做。

9. 组合数学（排列与组合，鸽笼原理，容斥原理，递推，Fibonacci数列，Catalan数列，Stirling数，差分序列，生成函数，置换，Polya原理）

了解即可。数学上的排列组合知识要复习下。鸽笼原理要知道应用案例。

10. 概率论（简单概率，条件概率，Bayes定理，期望值）

了解简单概率、条件概率。

11. 矩阵（矩阵的概念和运算，二分求解线性递推方程，多米诺骨牌棋盘覆盖方案数，高斯消元）

不需要。

12. 字符串处理（KMP，trie树，后缀树，有限状态自动机，Huffman编码，简单密码学）

需要熟练掌握简单的字符串处理。

KMP了解即可，要知道是怎么实现的，复杂度为什么是O(n)。trie树、后缀树要知道原理、复杂度、及应用。自动机不用管。

Huffman编码要了解。密码学要了解对称加密、非对称加密、RSA算法。

13. 动态规划（最长单调队列，凸完全单调性，树型动规，多叉转二叉，状态压缩类动规，四边形不等式）

需要熟练掌握基础的动态规划算法，如经典题目：最长单调子序列、最长公共子序列、背包问题等。

不需要做太复杂的。

14. 博奕论（Nim取子游戏，博弈树，Shannon开关游戏）

了解即可。

15. 搜索（A*，ID，IDA*，随机调整，遗传算法）

了解即可。

16. 微积分初步（极限思想，导数，积分，定积分，立体解析几何）

不用管。

复习数学上的极限思想。

具体的算法上，这个领域要学会：牛顿迭代法，二分法求平方根。