分类1
算法分类总览
算法是解决问题的系统化方法，根据问题的性质、解法的特点或应用场景，算法可以被分为以下几类。
1. 按设计思想分类
1.1 贪心算法 (Greedy Algorithm)
核心思想：局部最优解推导全局最优解。
应用场景：求解最小/最大值、选择问题等。
特点：快速，简单，但不能保证全局最优解。
典型问题：
- 最小生成树 (Prim/Kruskal)。
- 区间调度问题。
- 哈夫曼编码。
例子：
- 找零问题：用最少的硬币满足总额。
1.2 动态规划 (Dynamic Programming, DP)
核心思想：通过分解子问题并记录中间结果，避免重复计算。
应用场景：具有重叠子问题和最优子结构的问题。
特点：时间复杂度较高，适合复杂问题的精确解。
典型问题：
- 背包问题。
- 最长公共子序列。
- 编辑距离。
1.3 分治算法 (Divide and Conquer)
核心思想：将问题分解为更小的子问题，解决后合并结果。
应用场景：问题可以被递归分割并合并。
特点：利用递归解决问题。
典型问题：
- 快速排序。
- 归并排序。
- 二分搜索。
- 最大子数组和问题 (Kadane's Algorithm)。
1.4 回溯算法 (Backtracking)
核心思想：穷举所有可能解，遇到不符合条件的分支立即回溯。
应用场景：解约束满足问题。
特点：暴力搜索，适合求解组合、排列问题。
典型问题：
- N 皇后问题。
- 数独求解。
- 全排列/子集问题。
1.5 分支界限法 (Branch and Bound)
核心思想：系统搜索问题空间，通过剪枝减少计算量。
应用场景：需要搜索但有优化目标的问题。
典型问题：
- 旅行商问题 (TSP)。
- 0-1 背包问题。
1.6 图论算法
核心思想：解决图中的路径、连通性、最小生成树等问题。
典型问题：
- 最短路径：Dijkstra、Bellman-Ford、Floyd-Warshall。
- 拓扑排序。
- 最大流问题：Edmonds-Karp。
1.7 搜索算法
核心思想：在状态空间中寻找目标解。
分类：
- 深度优先搜索 (DFS)。
- 广度优先搜索 (BFS)。
- 双向搜索：从起点和终点同时搜索。
- 启发式搜索 (A 算法)*。
2. 按操作方式分类
2.1 排序算法
核心思想：对元素重新排列，满足特定顺序。
分类：
- 交换排序：冒泡排序、快速排序。
- 插入排序：直接插入排序、希尔排序。
- 选择排序：简单选择排序、堆排序。
- 归并排序：分治思想排序。
- 桶排序/计数排序：线性排序。
2.2 搜索算法
核心思想：在数据集合中查找目标元素。
分类：
- 顺序搜索：线性查找。
- 二分搜索：适用于有序数组。
- 哈希查找：基于哈希表。
2.3 数学算法
核心思想：通过数学理论解决问题。
分类：
- 数论算法：素数判定、最大公约数 (GCD)、快速幂。
- 组合数学：排列组合计算、Catalan 数。
- 概率与统计：随机数生成、蒙特卡罗方法。
3. 按数据结构分类
3.1 基于数组
- 滑动窗口。
- 双指针。
- 前缀和、差分数组。
3.2 基于栈和队列
- 单调栈/队列。
- 滑动窗口最大值。
- 括号匹配。
3.3 基于链表
- 快慢指针 (环检测)。
- 链表反转。
3.4 基于树和图
- 树的遍历：前序、中序、后序、层序。
- 最小生成树 (MST)：Prim、Kruskal。
- 二叉搜索树操作。
3.5 基于哈希
- 哈希表。
- LRU 缓存。
4. 按应用场景分类
4.1 字符串算法
典型问题：
- KMP、Rabin-Karp 字符串匹配。
- 字符串压缩。
- 最长回文子串。
4.2 图像处理算法
典型问题：
- 边缘检测：Sobel、Canny 算法。
- 图像压缩：JPEG。
4.3 机器学习算法
典型问题：
- 线性回归、逻辑回归。
- 支持向量机 (SVM)。
- 神经网络与深度学习。
5. 按复杂度分类
5.1 线性时间复杂度 (O(n))
- 单调栈。
- 滑动窗口。
5.2 对数时间复杂度 (O(\log n))
- 二分搜索。
- 平衡树操作。
5.3 多项式时间复杂度 (O(n^k))
- 动态规划。
- 图的遍历。
5.4 指数时间复杂度 (O(2^n))
- 子集枚举。
- 回溯算法。
总结
- 学习算法时需要掌握其基本思想和典型应用场景。
- 根据问题特性选择适合的算法类型。
- 不同算法之间往往可以结合使用（如动态规划 + 贪心、分治 + 搜索）。