ACM算法分类 对ACM竞赛的算法大概分了一下类，分成了数学、数据结构和算法三大块。里面肯定有许多重复和错误……请补充、更正，谢谢！     一 数学(Mathematics)   1 离散数学(Discrete Mathematics)   1.1 图论(Graph Theory)图的遍历(Graph Traversal): DFS, BFS最小生成树(Minimum Spanning Tree): Prim, Kruskal最短路径(Shortest Path): Dijkstra, Floyd传递闭包(Transitive Closure)关节点(Articulation Point - UndiGraph)拓扑排序(Topological Sort - AOV-Network)关键路径(Critical Path - AOE-Network)回路问题: 欧拉路(Euler Path), 汉密尔顿回路(Hamilton Tour)差分约束(Difference Constraints): Bellman-Ford二部图匹配(Bipartite Matching)网络流(Network Flow)...   1.2 组合数学(Combinatorics)   2 数论(Number Theory) 2.1 素数: GCD, LCM...2.2 同余   3 计算几何(Computational Geometry)线段相交, 多边形面积, 内点外点的判断, 凸包(Convex Hull), 重心(Bary Center)...   4 线性代数矩阵(Matrix), 线性方程组(Linear Equations)...   5 概率论   6 初等数学与解析几何   7 高等数学点积(Dot Product), 差积(Cross Product), 积分(Integral), 微分(Differential)...   二 数据结构(Data Structure)   1 线性结构线性表(Linear List)栈(Stack), 队列(Queue)数组(Array), 串(String), 广义表(General List)   2 非线性结构树(Tree)堆(Heap)图(Graph) 3 排序   3.1 插入排序直接插入排序(Insert Sort) O(n^2)折半插入排序(Binary Insert Sort)希尔排序(Shell Sort)   3.2 交换排序冒泡排序(Bubble Sort) O(n^2)快速排序(Quick Sort)  O(nlogn)   3.3 选择排序直接选择排序(Select Sort) O(n^2)锦标赛排序(Tournament Sort) O(nlogn)堆排序(Heap Sort) O(nlogn)   3.4 归并排序(Merge Sort) O(nlogn)   3.5 基数排序(Radix Sort) O(d(n+radix)) 4 查找   4.1 二分(Binary Search)   4.2 树型 二叉搜索树(Binary Search Tree)平衡搜索树(AVL Tree)并查集(Union-Find Set)   4.3 哈希(Hashing)   三 算法(Algorithm)   1 模拟算法   2 搜索算法2.1 枚举搜索(Enumeration)2.2 深度优先(Depth First Search)2.3 广度优先(Breadth First Search)2.4 启发式搜索(Heuristic Search)   3 以“相似或相同子问题”为核心的算法3.1 递推3.2 递归(Recursion)3.3 贪心法(Greedy)3.4 动态规划(Dynamic Programming)

评论