基于期末考试数学与复习提纲整理
| 算法名称 | 核心思路 | 时间复杂度 | 空间复杂度 | 稳定性 | 算法特性 |
|---|---|---|---|---|---|
| 归并排序 | 分治策略，将数组递归分成两半分别排序，然后合并 | O(n log n) | O(n) | 稳定 | 分治算法，需要额外空间，适合外部排序 |
| 快速排序 | 分治策略，选取主元分区，递归排序子序列 | 平均O(n log n) | O(log n) | 不稳定 | 分治算法，原地排序，最坏情况O(n²) |
| 二分搜索 | 每次比较中间元素，将搜索范围减半 | O(log n) | O(1) | - | 要求有序数组，分治思想 |
| 逆序对统计 | 分治策略，在归并排序过程中统计逆序对 | O(n log n) | O(n) | - | 基于归并排序修改，最大逆序对数为n(n-1)/2 |
| 钢条切割(DP) | 动态规划，自底向上计算各长度钢条的最优解 | O(n²) | O(n) | - | 动态规划典型问题，具有最优子结构 |
| 最长公共子序列(LCS) | 动态规划，填表记录子问题解，回溯找结果 | O(mn) | O(mn) | - | 动态规划典型问题，可优化空间复杂度 |
| 0-1背包问题 | 动态规划，决策每个物品是否放入背包 | O(nW) | O(nW) | - | NP完全问题，动态规划伪多项式时间算法 |
| 哈夫曼编码(贪心) | 贪心策略，合并频率最小的节点构建最优二叉树 | O(n log n) | O(n) | - | 贪心算法，构造前缀编码，用于数据压缩 |
| 活动选择问题(贪心) | 贪心策略，每次选择结束时间最早且与已选活动兼容的活动 | O(n log n) | O(1) | - | 贪心算法，按结束时间排序是关键 |
| BFS(广度优先搜索) | 队列实现，逐层遍历图/树的节点 | O(V+E) | O(V) | - | 求解无权图单源最短路径，找到的路径是最短路径 |
| DFS(深度优先搜索) | 栈/递归实现，深度优先遍历图/树的节点 | O(V+E) | O(V) | - | 用于拓扑排序、连通分量、环路检测等 |
| Prim算法(MST) | 贪心策略，从顶点扩展，每次添加连接树与非树节点的最小权边 | O(V²)或O(E log V) | O(V) | - | 最小生成树算法，适合稠密图 |
| Kruskal算法(MST) | 贪心策略，从边扩展，按权值排序，使用并查集避免环 | O(E log V) | O(E+V) | - | 最小生成树算法，适合稀疏图 |
| Dijkstra算法 | 贪心策略，维护源点到各点的最短距离，每次扩展最短路径 | O(V²)或O(E log V) | O(V) | - | 单源最短路径，不能处理负权边 |
| Bellman-Ford算法 | 动态规划思想，松弛所有边V-1次 | O(VE) | O(V) | - | 单源最短路径，可处理负权边，能检测负环 |
关键区别总结: 贪心算法每次选择后不可撤回，动态规划会考虑所有可能的选择；贪心算法不解决所有子问题，动态规划解决所有相关子问题。
常见函数增长速度排序（从慢到快）:
记忆口诀：常对幂指阶（常数、对数、多项式、指数、阶乘）
状态定义: dp[i][w] 表示考虑前i个物品，背包容量为w时的最大价值
状态转移方程:
解释:
初始化: dp[0][w] = 0 (0个物品时价值为0)
最终答案: dp[n][W]，其中n为物品总数，W为背包总容量