2. 复杂度分析与代码基本功

算法面试的第一道隐形门槛，往往不是“你会不会这道题”，而是“你写出来的代码能不能被信任”。复杂度分析决定了面试官如何判断你的方案是否可扩展，代码基本功决定了他们是否愿意继续听你讲下去。本章围绕时间复杂度、空间复杂度、均摊分析、递归复杂度、边界条件与手写规范六个方面展开，目标是让你在面试中既能算得清，也能写得稳。

一、时间复杂度：从“数操作”到“看增长”

时间复杂度的本质不是精确计时，而是描述当输入规模 n 增大时，基本操作次数的增长量级。面试中常见的误区是只背结论，不会推导。正确的做法是：先明确“基本操作”是什么，再写出操作次数关于 n 的表达式，最后取最高阶项并去掉常数系数。

例如下面这段代码：

int sum = 0;
for (int i = 0; i < n; i++) {
    for (int j = i; j < n; j++) {
        sum += i * j;
    }
}

内层循环执行次数为 (n - i) 次，总次数为 n + (n-1) + ... + 1 = n(n+1)/2。展开后是 0.5n² + 0.5n，取最高阶并去掉系数，得到 O(n²)。这里的关键判断依据是：当 n 从 100 增加到 1000 时，操作次数约增长 100 倍，符合平方增长。

面试中还需要掌握常见量级的相对速度。以 n = 10⁵ 为参考：O(n²) 约 10¹⁰ 次操作，通常超时；O(n log n) 约 1.7×10⁶ 次，安全；O(n) 约 10⁵ 次，非常宽裕。这个数量级直觉能帮你在面试中快速排除不可行方案，而不是等写完才发现超时。

二、空间复杂度：别忽略递归栈与隐式分配

空间复杂度统计的是算法运行过程中额外占用的存储空间，不包括输入本身。面试中常被忽略的是递归调用栈。例如归并排序的递归实现，每层合并需要 O(n) 的辅助数组，递归深度为 O(log n)，但辅助数组在任意时刻只存在一份，因此额外空间是 O(n)，而不是 O(n log n)。

再比如二叉树的中序遍历递归写法，没有显式创建数组，但递归栈深度等于树高。最坏情况下树退化成链表，空间复杂度为 O(n)；平衡情况下为 O(log n)。面试官问“空间复杂度是多少”时，如果你只回答“没有额外空间”，就会暴露对调用栈的忽视。

判断空间复杂度时，建议按三步走：第一，列出所有显式分配的数据结构；第二，加上递归调用栈的最大深度；第三，确认是否有原地修改输入的情况。若允许修改输入，原地算法的额外空间可以降到 O(1)，但要在面试中主动说明“我修改了输入数组”。

三、均摊分析：解释“偶尔很贵”的操作

均摊分析用于描述一系列操作中，虽然某一次可能代价很高，但平均到每次操作上代价较低。最典型的例子是动态数组的扩容。假设初始容量为 1，每次容量不足时翻倍，并复制所有元素。

插入第 1 个元素：容量 1，不扩容，代价 1。
插入第 2 个元素：扩容到 2，复制 1 个，代价 2。
插入第 3 个元素：扩容到 4，复制 2 个，代价 3。
插入第 5 个元素：扩容到 8，复制 4 个，代价 5。

可以看到，第 2、3、5、9……次插入是昂贵的，但两次昂贵操作之间间隔越来越长。把 n 次插入的总代价加起来，复制总次数不超过 2n，因此均摊到每次插入是 O(1)。面试中回答“动态数组尾部插入的时间复杂度”时，应说“均摊 O(1)，最坏 O(n)”，而不是简单说 O(1)。

四、递归复杂度：用递归树与主定理快速估算

递归复杂度不能只看递归深度。以归并排序为例，递推式为 T(n) = 2T(n/2) + O(n)。用递归树展开：每层总代价为 O(n)，共有 log n 层，因此总复杂度为 O(n log n)。

再以二分查找为例，递推式为 T(n) = T(n/2) + O(1)。每层代价为常数，层数为 log n，因此复杂度为 O(log n)。

面试中如果记不住主定理，可以用递归树口算：写出每层代价和层数，相乘即可。对于 T(n) = 2T(n/2) + O(n)，每层 O(n)，层数 log n，结果 O(n log n)；对于 T(n) = T(n-1) + O(1)，每层 O(1)，层数 n，结果 O(n)。这种方法足够应对大多数面试题。

五、边界条件：面试官最常埋的坑

边界条件是代码正确性的第一道防线。面试中常见的边界包括：空输入、单元素、全相同元素、已排序、逆序、极值、溢出。以二分查找为例，下面是一份边界处理较完整的写法：

int binarySearch(int[] nums, int target) {
    if (nums == null || nums.length == 0) return -1;
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) return mid;
        else if (nums[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

这里有两个关键点：第一，mid 用 left + (right - left) / 2 而不是 (left + right) / 2，避免 left + right 溢出；第二，循环条件是 left <= right，保证单元素区间也能被检查。面试中写完代码后，建议主动用三个用例验证：空数组、单元素数组、目标值不存在。这能显著降低被追问时翻车的概率。

六、代码规范与手写要求

面试手写代码不是写生产代码，但必须清晰、可读、无歧义。变量命名要有意义，避免 a、b、c；边界判断要前置；循环不变量要能在注释中一句话说清。例如在滑动窗口题中，可以写“窗口为 [left, right)，窗口内元素满足条件”，这样面试官能快速跟上你的思路。

手写时还要注意：不要写伪代码混搭真实语法；不要省略分号或括号；不要用未定义的辅助函数。如果确实需要辅助函数，先声明再调用，或者直接内联。面试官更看重的是逻辑完整，而不是代码长度。

七、一份可执行的面试自检清单

下面这份清单可以直接在面试练习中使用，每道题写完代码后逐项检查：

检查项	判断标准	常见反例
时间复杂度	能写出递推式或循环次数表达式，并说明最高阶项	只说“大概是 O(n)”，没有推导
空间复杂度	包含递归栈与辅助数组，说明是否原地修改	忽略递归深度，声称 O(1)
均摊分析	动态扩容、哈希冲突等场景说明均摊与最坏区别	把均摊 O(1) 说成最坏 O(1)
边界条件	空、单元素、全相同、极值至少覆盖三类	只测正常用例，不测空数组
代码规范	命名清晰、边界前置、无未定义函数	变量名为 a、b、c，逻辑跳跃

把这份清单用在每次模拟面试中，你会发现大部分“低级错误”其实可以在写完后 30 秒内自查出来。复杂度分析与代码基本功不是一次学会的知识点，而是每次写代码时都要重复的动作。练到形成条件反射，面试中的手写环节就会从“紧张应付”变成“稳定输出”。