算法基础专题导读

在正式进入数组、链表这些"看得见摸得着"的数据结构之前，先花两篇文章把算法基础的底子打好。这个专题不涉及具体题目，却决定了你后面刷题时的"手感"：拿到一道题，能不能在写代码之前就判断出这个思路能不能过、会不会超时。

为什么复杂度分析是一切优化的起点

设想这样一个场景：你写了两个版本的解决方案，本地测试数据都能跑通，提交到 LeetCode 后一个通过一个超时。如果不具备复杂度分析能力，你只能反复试错；具备这个能力，你一眼就能看出 O(n²) 的解法在 n = 10⁵ 的数据规模下必然超时，直接换思路。

再举一个后端开发中的例子：接口响应慢，你怀疑列表查询逻辑有问题。如果核心循环是双重 for 遍历对比，那就是 O(n·m)，数据量一上来必慢；如果改成了先建 HashMap 再单层遍历查表，就是 O(n+m)。优化方向的选择，本质上就是对复杂度的判断。

所以复杂度分析的价值有两个：

• 事前判断：写代码之前估算这个方案在大数据量下的表现，避免无效编码。
• 定位瓶颈：出问题的时候知道瓶颈大概率在哪一层，而不是靠猜。

更实际的一点是，面试中几乎每道算法题的收尾都会问一句"你的时间复杂度和空间复杂度是多少"，答不上来等于这道题白做。

"事前判断"还有一条刷题专属的用法：看数据范围反推目标复杂度。LeetCode 每道题都标注了约束条件，它就是出题人给你的提示——多大输入配什么复杂度才能过，是有硬性对应关系的：

背下这张表，很多题在读题那一刻就有了方向。这也是为什么把复杂度分析放在全系列最前面——它决定了你读题的"第一反应"质量。

下面是一个典型的事前判断场景。两数之和的暴力解法，写之前就能断定它在 n = 10⁴ 时接近 10⁸ 次操作，属于临界偏危险的量级：

// O(n^2)：双重枚举所有数对
for (int i = 0; i < nums.length; i++) {
    for (int j = i + 1; j < nums.length; j++) {
        if (nums[i] + nums[j] == target) {
            return new int[]{i, j};
        }
    }
}
 
// O(n)：单层遍历 + 哈希查表，"有没有互补的数"交给 HashMap O(1) 回答
Map<Integer, Integer> seen = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
    if (seen.containsKey(target - nums[i])) {
        return new int[]{seen.get(target - nums[i]), i};
    }
    seen.put(nums[i], i);
}

同样的问题，方案一在多数用例下勉强能过、大数据用例超时，方案二稳过。会分析的人第一次就选方案二，不会分析的人靠提交反馈试错。

本专题覆盖的内容

算法基础专题包含以下几个模块，对应本系列的两篇文章：

1. 时间复杂度与空间复杂度（algo-03）

核心内容：

• 大 O 记号的真正含义：描述的是增长趋势，不是精确的执行时间。
• 常见复杂度阶的直观对比：O(1)、O(logn)、O(n)、O(nlogn)、O(n²)、O(2ⁿ)、O(n!)。
• 最好、最坏、平均三种情况的区分。
• 均摊分析：为什么动态数组（ArrayList）虽然扩容是 O(n)，单次插入仍算 O(1)。
• 空间复杂度的计算，以及递归带来的隐式栈开销。

学完这部分，你应该能对一段陌生代码逐行估算复杂度，而不是背出"for 循环套 for 循环就是 O(n²)"这种粗糙口诀。

2. 递归的性能问题（algo-04）

递归是二叉树、回溯、DP 三大专题的公共基础，很多新手栽在这里：

• 递归三要素：参数与返回值、终止条件、单层逻辑。
• JVM 调用栈的工作方式，以及 StackOverflowError 是怎么发生的。
• 重复计算：朴素递归求斐波那契是 O(2ⁿ)，加一层记忆化就降到 O(n)。
• 估算递归复杂度的通用方法：画递归树，节点数 × 单层成本。
• 递归转迭代的基本思路。

3. 内存消耗与库函数的时间成本

这两块内容分别回答两个高频疑问：

• 内存相关：Java 中一个 int、一个对象引用占多少字节，为什么刷题时明明没开数组却内存超限（答案往往在递归栈上）。
• 库函数相关：刷 LeetCode 用不用 Arrays.sort()？结论是用，但要清楚它底层是双轴快排、平均 O(nlogn)；再比如 String.indexOf()、substring() 这类函数各有自己的复杂度，面试时被追问"库函数复杂度是多少"要能答上来。

一个统一的判断标准：用库函数实现的是算法中的一小步操作没问题，把整个算法主体都交给库函数就失去了练习意义。

初学者常见误区

在正式展开之前，先把几个流传很广的错误观念摆出来，后续两篇文章会逐个修正：

• "复杂度就是运行时间"。大 O 描述增长趋势，不含常数因子，也不管机器快慢。两段同为 O(n) 的代码实测耗时可以差十倍。
• "循环次数少一层就一定快"。O(n²) 在 n=10 时完全可能比 O(n) 快，大 O 的结论只在 n 足够大时可靠。
• "没开数组就是空间 O(1)"。递归调用占栈，深度即空间；字符串拼接、集合扩容也都是隐式空间。
• "用了库函数就不算自己的复杂度"。Arrays.sort() 的 O(nlogn) 要计入整体，把 sort 放进循环，整体就是 O(n²logn)。
• "超时一定是代码写错"。逻辑正确的 O(n²) 在 n=10⁵ 下照样超时，这是复杂度问题，不是 bug，换思路才是正解。

给后续刷题建立统一的分析方法

这个专题最终要交付的不是知识点，而是一套"三问"习惯。以后每写完一段算法代码，强迫自己回答：

这三个问题在后续每个专题都会反复出现。比如数组专题里，滑动窗口之所以优于暴力枚举，就是因为把 O(n²) 降到了 O(n)；二叉树专题里，很多"超时"的真实原因是递归里做了重复计算。

学习建议

• 不要死磕数学证明。复杂度分析背后有渐近分析的理论，但刷题场景下只需要会算、会比较、会表达，不用抠主定理证明。
• 拿自己写过的代码练手。找一段你项目里或以前刷题的代码，逐行标出复杂度，再汇总成整体复杂度。练五段基本就熟了。
• 结合超时案例理解。LeetCode 上故意用错误复杂度提交一次，感受一下 O(n²) 在 n=10⁵ 下超时的样子，比看十篇理论文章印象都深。

小结

• 复杂度分析是"事前判断 + 定位瓶颈"的工具，也是面试必问项。
• 专题两大核心：复杂度度量（algo-03）与递归性能（algo-04），外加内存消耗和库函数成本两个补充话题。
• 学完标准：面对任何一段代码，能快速说出时间/空间复杂度，并能判断它在给定数据规模下会不会超时。

下一篇正式进入大 O 记号，把"衡量算法的尺子"讲透。

参考

• 代码随想录 · 算法基础专题