算法复杂度与递归：先学会估成本和拆问题

第一次碰到“算法复杂度与递归：先学会估成本和拆问题”，我以为把定义和代码记下来就算学会了。真正动手时才暴露出问题：我会背 O(n)、O(log n)，却解释不清两层循环为什么不一定就是 O(n²)，递归一深更是只会凭感觉判断。这次重学我刻意放慢了速度，先看它为什么出现，再看规则怎样工作，最后才落到实现。

算法学习最容易被低估的一步，就是复杂度和递归。很多人一上来刷二分、动态规划、图算法，但真正卡住的地方往往不是语法，而是两个问题：

这段代码随着数据规模变大，会不会炸？
递归到底什么时候停、每一层又返回给谁？

复杂度是判断算法成本的语言，递归是理解分治、回溯、树、图和动态规划的入口。把这两个打稳，后面的算法才不会像一堆模板。

它从哪里来

复杂度记号来自十九世纪末的数学分析，后来由 Donald Knuth 等人系统带入算法分析。它让不同机器、不同语言上的程序拥有共同的增长尺度。递归则把“一个问题由更小的同类问题组成”直接写进程序，调用栈负责保存尚未完成的现场。

复杂度到底在看什么

复杂度与递归学习地图

图：复杂度描述输入规模变大时，时间和空间成本如何增长

复杂度不关心机器有多快，也不关心某一次运行刚好用了多少毫秒，它关心的是：当输入规模 n 变大时，执行次数按什么级别增长。

常见复杂度从低到高大致是：

复杂度	含义	常见场景
`O(1)`	常数时间	数组下标访问、哈希表平均查询
`O(log n)`	每次缩小一半	二分查找、平衡树查询
`O(n)`	扫一遍	线性遍历、求最大值
`O(n log n)`	每层处理 n，共 log n 层	归并排序、平均快排
`O(n²)`	两层枚举	暴力两数关系、简单 DP
`O(2^n)`	每个元素选或不选	子集、指数级搜索
`O(n!)`	全排列	排列类回溯

学习时不要机械背表，而要能把代码和复杂度对应起来。

看循环：不是有几层就一定是多少

最简单的情况：

for (int i = 0; i < n; i++) {
    System.out.println(i);
}

执行 n 次，是 O(n)。

两层完整嵌套：

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

执行大约 n * n 次，是 O(n²)。

但如果内层不是完整跑 n 次，就要重新分析：

for (int i = 1; i < n; i *= 2) {
    count++;
}

i 每次翻倍，执行次数是 log₂n，所以是 O(log n)。这也是二分、堆、平衡树经常出现 log n 的原因：每次都把问题规模按比例缩小。

看递归：递归树比直觉更靠谱

递归复杂度要看两个部分：

每一层做多少事。
一共有多少层，或者分裂出多少子问题。

例如二分：

int binarySearch(int[] nums, int target, int left, int right) {
    if (left > right) return -1;
    int mid = left + (right - left) / 2;
    if (nums[mid] == target) return mid;
    if (nums[mid] < target) {
        return binarySearch(nums, target, mid + 1, right);
    }
    return binarySearch(nums, target, left, mid - 1);
}

每层只做常数工作，规模每次减半，所以时间复杂度是 O(log n)。递归深度也是 O(log n)，如果没有尾递归优化，空间复杂度是调用栈的 O(log n)。

再看归并排序：

void mergeSort(int[] nums, int left, int right) {
    if (left >= right) return;
    int mid = left + (right - left) / 2;
    mergeSort(nums, left, mid);
    mergeSort(nums, mid + 1, right);
    merge(nums, left, mid, right);
}

每层所有区间合起来处理 n 个元素，一共有 log n 层，所以是 O(n log n)。

递归三件套

写递归前，我会强迫自己写清楚三件事：

函数定义：这个函数负责解决什么子问题。
终止条件：什么时候不用继续拆。
递推关系：当前问题如何依赖更小的问题。

比如求阶乘：

long factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);
}

函数定义：factorial(n) 返回 n!。
终止条件：n <= 1。
递推关系：n! = n * (n-1)!。

如果这三件事说不清楚，就不要急着写代码。很多递归 bug 都来自“感觉应该这么写”，但函数定义根本没站稳。

空间复杂度也很重要

空间复杂度不只看你有没有 new 数组，也要看递归调用栈。

void dfs(TreeNode root) {
    if (root == null) return;
    dfs(root.left);
    dfs(root.right);
}

这段代码没有显式创建大数组，但递归栈深度取决于树高。平衡树是 O(log n)，退化成链表就是 O(n)。

工程里空间有时比时间更敏感。比如缓存、搜索、推荐、日志处理，数据量上来后，一个看起来“多开几个数组”的写法就可能把内存打满。

我踩过的几个坑

把常数项看得太重：O(2n) 仍然写作 O(n)。
只看平均复杂度：哈希表平均 O(1)，但极端冲突会退化。
忽略输入分布：快排平均快，但接近有序数据可能触发最坏情况，需要随机化或三路切分。
忽略递归深度：小数据没问题，大数据可能栈溢出。
混淆时间和空间：归并排序时间好，但需要额外数组。

工程场景

复杂度分析在真实开发里不是为了炫技，而是为了提前判断风险。

例如一个接口要对 10 万条数据做两两比较，O(n²) 就是 100 亿级操作，基本不能在线请求里做。此时要考虑哈希、排序、索引、分桶、离线计算或近似算法。

再比如递归 DFS 很适合写树结构，但如果数据来自用户输入，层级可能非常深，就要考虑改成显式栈，避免栈溢出。

面试题

O(log n) 为什么常出现在二分和平衡树中？
递归算法的空间复杂度为什么要算调用栈？
快排为什么平均 O(n log n)，最坏可能 O(n²)？
O(n) 一定比 O(n log n) 快吗？为什么小数据下不一定？
如何判断一段双层循环是不是一定 O(n²)？

小结

复杂度让你判断算法的规模边界，递归让你理解问题如何拆分。后面学习二分、排序、回溯、动态规划、图算法时，都离不开这两个基础。真正要形成的能力不是背结论，而是看到代码能估成本，看到问题能拆子问题。