算法

算法是对特定问题求解步骤的精确描述，它由一系列有限的指令组成，接受输入产生输出，并在有限时间内终止。衡量算法好坏的核心指标是时间复杂度和空间复杂度，通常用大 O 表示法描述。一个 O(n log n) 的排序算法在数据量增大时，性能优势会远超 O(n^2) 的算法——这种差距在百万级数据下尤为明显。

提示

算法知识体系，涵盖常见算法范式、解题思路与经典问题分类

核心算法范式

分治

分治将问题分解为若干规模更小的子问题，递归求解后合并结果。归并排序是最典型的分治算法：将数组一分为二，分别排序后合并两个有序数组。分治的关键在于子问题之间相互独立，不存在重叠计算，否则应该考虑动态规划。

动态规划

动态规划适用于具有最优子结构和重叠子问题性质的问题。与分治不同，动态规划会缓存子问题的解，避免重复计算。实现方式分为自顶向下的记忆化搜索和自底向上的表格填充。背包问题、最长公共子序列、编辑距离都是经典题目。状态转移方程的设计是动态规划的核心难点。

贪心算法

贪心算法在每一步都做出局部最优选择，期望最终得到全局最优解。贪心的适用条件是问题具有贪心选择性质——局部最优能推导出全局最优。活动选择、哈夫曼编码、最小生成树（Kruskal、Prim）都属于贪心。贪心算法效率高，但适用范围比动态规划窄。

回溯

回溯通过穷举所有可能的解来找到答案，本质上是深度优先搜索。当发现当前路径不可能得到有效解时，回退并尝试其他分支。N 皇后、数独求解、全排列、组合总和都是回溯的经典应用。回溯的核心在于剪枝——尽早排除不可能的分支，减少搜索空间。

滑动窗口

滑动窗口是处理数组/字符串子区间问题的高效技巧。维护一个窗口，通过左右指针的移动来扩大或缩小窗口，每个元素最多进入和离开窗口各一次，因此时间复杂度为 O(n)。最小覆盖子串、最长无重复子串、字母异位词匹配都是滑动窗口的典型应用。

解题方法论

面对一道算法题，首先判断问题类型：

• 求最值且有重叠子问题 -> 动态规划
• 求最值且无重叠 -> 分治或贪心
• 求所有解 -> 回溯
• 涉及子数组/子串 -> 滑动窗口或前缀和
• 涉及层级遍历 -> BFS
• 涉及连通性 -> 并查集或 DFS

确定范式后，再选择合适的数据结构。哈希表用于快速查找，堆用于动态维护最值，栈用于处理嵌套结构，队列用于 BFS。数据结构和算法是相辅相成的，掌握常用数据结构的特性（增删改查的时间复杂度）是解题的基础。

复杂度分析

常见复杂度从低到高排列：

复杂度	名称	典型算法
O(1)	常数	哈希表查找
O(log n)	对数	二分查找
O(n)	线性	遍历数组
O(n log n)	线性对数	归并排序
O(n^2)	平方	冒泡排序
O(2^n)	指数	子集枚举

在面试和实际开发中，O(n) 和 O(n log n) 的算法通常是可接受的，O(n^2) 在数据量较小时可以接受，而指数级算法几乎总是需要优化。

常见错误

混淆分治与动态规划

分治和动态规划都将问题分解为子问题，但关键区别在于子问题是否重叠。归并排序的子问题互不重叠（左右两半独立），所以用分治；爬楼梯问题中 f(5) 依赖 f(4) 和 f(3)，而 f(4) 也依赖 f(3)，子问题重叠，必须用动态规划。如果对重叠子问题使用分治，会导致指数级时间复杂度。

贪心算法的适用条件误判

贪心要求贪心选择性质（局部最优推导全局最优）和最优子结构。经典反例：0-1 背包问题不能用贪心（按性价比排序贪心选不到最优解），但分数背包可以。判断能否用贪心的方法：尝试构造反例——如果能找到一个局部最优但全局非最优的情况，就不能用贪心。

回溯忘记撤销选择

回溯的核心是"选择 - 递归 - 撤销"三步。最常见的 bug 是做出选择后递归，但递归返回时忘记撤销选择，导致后续分支的状态被污染：

// 错误：缺少撤销操作
path.add(candidates[i]);
backtrack(candidates, target - candidates[i], i);
// 缺少 path.remove(path.size() - 1)

// 正确：完整的选择-递归-撤销
path.add(candidates[i]);
backtrack(candidates, target - candidates[i], i);
path.remove(path.size() - 1);  // 撤销选择，恢复状态

复杂度分析时忽略隐含开销

哈希表查找虽然是 O(1)，但常数因子较大；数组访问也是 O(1)，但缓存友好度远高于链表。在数据量较小时，O(n^2) 的简单算法可能比 O(n log n) 的复杂算法更快。选择算法时要结合实际数据规模，不要只看渐进复杂度。