数据结构与算法中常见算法的分类、核心思想及时间复杂度、空间复杂度的详细说明，帮助理解算法的效率特性：
一、基础排序与查找算法
1. 排序算法
| 算法类型 | 具体算法 | 核心思想 | 时间复杂度（平均 / 最好 / 最坏） | 空间复杂度 | 稳定性 |
|---|
| 比较类排序 | 冒泡排序 | 相邻元素两两比较，逆序则交换，重复至有序 | O (n²) / O (n)（已排序） / O (n²) | O(1) | 稳定 |
| 选择排序 | 每次选剩余元素中的最值，放到已排序序列末尾 | O(n²) / O(n²) / O(n²) | O(1) | 不稳定 |
| 插入排序 | 将元素逐个插入到已排序序列的合适位置（类似整理扑克牌） | O (n²) / O (n)（已排序） / O (n²) | O(1) | 稳定 |
| 归并排序 | 分治法：拆分数组为两半，分别排序后合并 | O(n log n) / O(n log n) / O(n log n) | O(n) | 稳定 |
| 快速排序 | 分治法：选基准元素，分割数组为 “小于 / 大于基准” 两部分，递归排序 | O(n log n) / O(n log n) / O(n²) | O (log n)（递归栈） / O (n)（最坏） | 不稳定 |
| 堆排序 | 利用堆的特性，每次提取堆顶最值，重新调整堆结构 | O(n log n) / O(n log n) / O(n log n) | O(1) | 不稳定 |
| 非比较类排序 | 计数排序 | 统计每个元素出现次数，直接计算其在有序数组中的位置（适用于整数） | O (n + k)（k 为数据范围） / O (n + k) / O (n + k) | O(n + k) | 稳定 |
| 基数排序 | 按数字每一位（从低到高）排序，依赖计数排序作为子过程 | O (d*(n + k))（d 为位数，k 为基数） | O(n + k) | 稳定 |
| 桶排序 | 将数据分到多个桶中，桶内单独排序后合并（适用于均匀分布数据） | O (n + k) / O (n + k) / O (n²)（桶内无序） | O(n + k) | 稳定 |
2. 查找算法
| 算法名称 | 核心思想 | 时间复杂度（平均 / 最坏） | 空间复杂度 | 适用场景 |
|---|
| 顺序查找 | 逐个遍历元素，匹配目标值 | O(n) / O(n) | O(1) | 无序集合、数据量小 |
| 二分查找 | 有序数组中，每次取中间元素比较，缩小查找范围 | O(log n) / O(log n) | O (1)（迭代）/ O (log n)（递归） | 有序数组 |
| 插值查找 | 基于目标值与首尾元素的比例动态计算中间位置（二分查找的改进） | O (log log n)（均匀分布） / O (n)（极端分布） | O(1) | 均匀分布的有序数组 |
| 斐波那契查找 | 利用斐波那契数列分割数组，减少比较次数 | O(log n) / O(log n) | O(1) | 有序数组，减少乘法 / 除法操作 |
| 哈希查找 | 通过哈希函数直接定位元素存储位置（依赖哈希表） | O (1) / O (n)（哈希冲突严重时） | O(n) | 需快速查找，允许少量哈希冲突 |
二、递归与分治算法
| 算法 / 问题 | 核心思想 | 时间复杂度 | 空间复杂度 | 备注 |
|---|
| 归并排序 | 分治法：拆分 + 排序 + 合并 | O(n log n) | O(n) | 见排序算法 |
| 快速排序 | 分治法：选基准 + 分割 + 递归 | O(n log n) | O(log n) | 见排序算法 |
| 二分查找（递归） | 分治法：递归缩小查找范围 | O(log n) | O(log n) | 递归栈开销 |
| 大整数乘法 | 将大整数拆分为小整数，通过公式减少乘法次数 | O(n^log3) ≈ O(n^1.585) | O(n) | 传统方法为 O (n²) |
| 矩阵乘法（Strassen 算法） | 将矩阵分块，用 7 次乘法替代传统 8 次，递归计算 | O(n^log7) ≈ O(n^2.807) | O(n²) | 传统方法为 O (n³) |
| 汉诺塔问题 | 递归移动圆盘：n 个圆盘从 A→C（借助 B），分解为 n-1 个圆盘的子问题 | O(2ⁿ) | O(n) | 指数级复杂度，仅理论意义 |
三、动态规划（DP）
| 算法 / 问题 | 核心思想 | 时间复杂度 | 空间复杂度 | 备注 |
|---|
| 斐波那契数列（DP 优化） | 存储子问题结果（f (n)=f (n-1)+f (n-2)），避免重复计算 | O(n) | O (1)（滚动数组） | 递归未优化为 O (2ⁿ) |
| 最长公共子序列（LCS） | 定义 dp [i][j] 为两个字符串前 i/j 位的 LCS 长度，通过子问题推导 | O(m*n) | O (m*n)（可优化为 O (min (m,n))） | m、n 为字符串长度 |
| 最长递增子序列（LIS） | 维护 “最小尾元素数组”，二分查找优化更新 | O(n log n) | O(n) | 传统 DP 为 O (n²) |
| 0-1 背包 | 定义 dp [i][j] 为前 i 件物品、容量 j 时的最大价值，通过状态转移推导 | O(n*C) | O (n*C)（可优化为 O (C)） | n 为物品数，C 为背包容量 |
| 完全背包 | 物品可无限选，状态转移时允许重复选取 | O(n*C) | O(C) | 优化后空间复杂度降低 |
| Floyd-Warshall 算法 | 动态规划求任意两点间最短路径，通过中间节点更新距离 | O(n³) | O(n²) | n 为顶点数 |
| 编辑距离 | 定义 dp [i][j] 为两个字符串前 i/j 位的最小修改次数（插入 / 删除 / 替换） | O(m*n) | O(m*n) | m、n 为字符串长度 |
四、贪心算法
| 算法名称 | 核心思想 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|
| 哈夫曼编码 | 合并频率最低的节点生成最优前缀码树，用于数据压缩 | O(n log n) | O(n) | 字符频率不均的压缩场景 |
| 活动选择问题 | 每次选择结束时间最早的活动，最大化不重叠活动数量 | O (n log n)（排序） | O(1) | 无权重的活动调度 |
| Prim 算法 | 从顶点出发，每次添加连接树内外的最短边，构建最小生成树 | O (E log V)（邻接表 + 优先队列） | O(V) | 稠密图（边多）更优 |
| Kruskal 算法 | 按边权排序，依次添加不形成环的边，构建最小生成树 | O (E log E)（排序） | O(V) | 稀疏图（边少）更优 |
| Dijkstra 算法 | 贪心选择当前最短路径节点，更新邻接节点距离，求单源最短路径 | O (E log V)（优先队列） | O(V) | 非负权图 |
| 零钱兑换（贪心适用场景） | 优先选择最大面额硬币，直到凑齐金额（仅适用于特定面额，如 1,5,10） | O (k)（k 为硬币种类） | O(1) | 面额满足 “贪心选择性质” |
五、图论算法
| 算法名称 | 核心思想 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|
| 图的遍历 | | | | |
| 深度优先搜索（DFS） | 从起点出发，尽可能深入遍历，无路可走时回溯 | O(V + E) | O (V)（递归栈 /visited 数组） | 检测环、连通分量 |
| 广度优先搜索（BFS） | 从起点出发，按层次遍历所有可达节点 | O(V + E) | O (V)（队列 /visited 数组） | 无权图最短路径、层次遍历 |
| 最短路径 | | | | |
| Bellman-Ford 算法 | 迭代松弛所有边，可检测负权环 | O(V*E) | O(V) | 含负权边的单源最短路径 |
| Floyd-Warshall 算法 | 动态规划求任意两点间最短路径（见动态规划） | O(V³) | O(V²) | 多源最短路径 |
| 最小生成树 | | | | |
| Prim 算法 / Kruskal 算法 | 见贪心算法部分 | O(E log V) / O(E log E) | O(V) | 连通无向图 |
| 其他图算法 | | | | |
| 拓扑排序 | 对有向无环图（DAG）节点排序，使所有边从左到右 | O(V + E) | O(V) | 任务调度、依赖关系处理 |
| Kosaraju 算法（强连通分量） | 两次 DFS：第一次按完成时间排序，第二次在反向图中遍历 | O(V + E) | O(V + E) | 有向图的强连通分量求解 |
| Tarjan 算法（强连通分量） | 一次 DFS，通过栈和低链接值识别强连通分量 | O(V + E) | O(V) | 有向图的强连通分量求解 |
| Edmonds-Karp 算法（最大流） | 基于 BFS 的 Ford-Fulkerson 实现，寻找增广路径 | O(V*E²) | O(V + E) | 网络流问题 |
六、字符串匹配算法
| 算法名称 | 核心思想 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|
| 朴素匹配 | 逐个比较文本与模式串的字符，不匹配则回溯 | O(n*m) | O(1) | 模式串 / 文本短，简单场景 |
| KMP 算法 | 预处理模式串得到 “部分匹配表”，避免文本指针回溯 | O(n + m) | O(m) | 单模式串匹配，文本 / 模式串长 |
| BM 算法 | 从模式串尾部比较，利用 “坏字符” 和 “好后缀” 规则跳过无效比较 | O (n/m)（平均） / O (n*m)（最坏） | O(m) | 单模式串匹配，实际效率高于 KMP |
| Rabin-Karp 算法 | 通过哈希值比较文本子串与模式串，不匹配则直接跳过 | O (n + m)（无哈希冲突） / O (n*m)（冲突多） | O(1) | 多模式串匹配初步筛选 |
| AC 自动机 | 基于字典树（Trie）和失败指针，同时匹配多个模式串 | O (n + m + z)（n 为文本长，m 为总模式串长，z 为匹配数） | O(m) | 多模式串匹配（如敏感词过滤） |
七、其他重要算法
| 算法名称 | 核心思想 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|
| 回溯算法 | 尝试所有可能解，不满足条件则回溯（如 N 皇后、子集和） | O (k*2ⁿ)（k 为操作复杂度） | O (n)（递归栈） | 组合优化、解空间小的问题 |
| 分支限界法 | 类似回溯，但通过 “界限” 剪枝，优先扩展更优分支（如旅行商问题） | O (2ⁿ)（最坏） | O(n) | 求最优解，解空间较大 |
| 位运算算法 | 利用二进制位操作（如判断奇偶、计数 1 的个数） | O (1)（单操作） | O(1) | 整数运算优化、状态压缩 |
| 滑动窗口算法 | 维护一个 “窗口”，通过移动边界解决子串 / 子数组问题（如最长无重复子串） | O(n) | O (k)（k 为窗口内元素类型数） | 连续子序列 / 子串问题 |
| 前缀和 | 预处理数组前缀和，快速计算区间和 | O (n)（预处理） / O (1)（查询） | O(n) | 频繁区间和查询 |
| 差分 | 预处理差分数组，快速实现区间更新 | O (n)（预处理） / O (1)（更新） | O(n) | 频繁区间更新 + 最终查询 |
总结
- 时间复杂度：反映算法随数据规模增长的执行效率，优先选择低复杂度算法（如 O (n log n) 优于 O (n²)）。
- 空间复杂度：反映算法对内存的占用，需在时间与空间之间权衡（如归并排序用空间换时间）。
- 适用场景：算法选择需结合数据特性（如有序 / 无序、是否含负权）、规模（n 大小）及稳定性要求（如排序是否需保持相等元素的相对顺序）。
理解时空复杂度是分析算法效率的核心，实际应用中需根据问题场景选择最优解。
