正文

ACM算法分类2006-05-29 21:31:00

【评论】 【打印】 【字体: 】 本文链接:http://blog.pfan.cn/edwardguo/15184.html

分享到:

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)

阅读(3439) | 评论(0)


版权声明:编程爱好者网站为此博客服务提供商,如本文牵涉到版权问题,编程爱好者网站不承担相关责任,如有版权问题请直接与本文作者联系解决。谢谢!

评论

暂无评论
您需要登录后才能评论,请 登录 或者 注册