复杂度分析

这一课你将能做到

1. 用 Big-O 描述一段代码、一条 SQL、一个接口的最坏时间与空间复杂度
2. 区分 O(1)、O(log n)、O(n)、O(n log n)、O(n²) 的增长速度与工程含义，并能手算简单递推式
3. 解释均摊分析的典型场景，以及 P、NP、NP 完全问题的直觉含义

为什么要学

复杂度是工程师之间的「速度方言」。说「这个接口有点慢」无法沟通；说「这是 O(n²)，n 是提交记录数，当前 500 万，大约 25 万亿次操作」，问题的严重程度和优化方向立刻清楚。

它在三个层面直接救命：

• 写代码：嵌套循环可能是 O(n²) 陷阱；递归每层拷贝列表可能让空间暴涨
• 写 SQL：全表扫描 O(n) 与走索引 O(log n) 的差距，在百万行表上就是 2 秒与 2 毫秒
• 做容量规划：判题平台要支撑 10 万用户同时提交，先估每个环节的量级再谈加机器

Big-O 不精确预测毫秒数，它回答的是更本质的问题：输入规模翻倍，时间或空间涨多少？

先建立图像

复杂度增长对照（n 从 10 到 1,000,000）
复杂度        n=10      n=1000     n=100万      工程含义
O(1)         1         1          1            哈希查找、数组取元素
O(log n)     ~3        ~10        ~20          二分、平衡树、索引定位
O(n)         10        1000       100万        单次遍历、全表扫描
O(n log n)   ~33       1万        2000万       排序，能接受的重操作上限
O(n²)        100       100万      1万亿         嵌套循环，n 上万就危险
O(2ⁿ)        1024      天文数字    ——           暴力枚举，n≤30 才可行

增长曲线示意（数字代表操作量级）
O(1)   ───────────────────── 平
O(logn)───────
O(n)   ╱─────
O(n²)  ╱╱──── 陡升
       0───n 增大──▶

一句直觉：log n 几乎不随 n 增长（2²⁰ 已是百万），所以看到 O(log n) 就可以当作「很快」；看到 O(n²) 就要追问 n 的实际上限。

跟着做

步骤 1：从代码数出复杂度

public class CountComplexity {

    // O(n)：一层循环，操作数与 n 成正比
    public static long sum(int[] a) {
        long s = 0;
        for (int x : a) {
            s += x;
        }
        return s;
    }

    // O(n²)：两层独立规模 n 的循环嵌套
    public static int pairs(int n) {
        int count = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {   // 共 n(n-1)/2 次
                count++;
            }
        }
        return count;                            // 常数系数 1/2 在 Big-O 中丢弃
    }

    // O(log n)：每轮规模减半
    public static int halvings(int n) {
        int rounds = 0;
        while (n > 1) {
            n /= 2;
            rounds++;
        }
        return rounds;                           // 结果约等于 log₂n
    }

    public static void main(String[] args) {
        System.out.println(sum(new int[]{1, 2, 3}));
        System.out.println(pairs(100));          // 4950
        System.out.println(halvings(1_000_000)); // 19
    }
}

Big-O 的三条化简规则：只保留增长最快的项（n² + n → O(n²)）、丢弃常数系数（3n → O(n)）、常数时间统一记 O(1)。它描述上界与增长趋势，不描述单次操作是 1 纳秒还是 1 毫秒——但当复杂度跨量级时，常数差异毫无意义，O(n) 永远赢 O(n²)。

步骤 2：分析递归——展开法与主定理直觉

public class RecursionCost {

    // 递归式：T(n) = 2T(n/2) + O(n) —— 归并排序形态
    // 直观展开：每一层都有 O(n) 的工作量，共 log n 层 ⇒ O(n log n)
    public static void printLevels(int n, int depth) {
        if (n <= 1) {
            System.out.println("叶子, 深度 " + depth);
            return;
        }
        System.out.println("规模 " + n + ", 深度 " + depth);
        printLevels(n / 2, depth + 1);
        printLevels(n / 2, depth + 1);
    }

    public static void main(String[] args) {
        printLevels(8, 0);
    }
}

分析递归的通用直觉就两步：树有几层（每层规模怎么缩小）× 每层总工作量。常见三种结论：对半缩小但每层 O(n) → O(n log n)；缩小一半且每层 O(1) → O(log n)；只缩小常数（n→n-1）且每层 O(n) → O(n²)。这就是主定理的直觉版，面试中绝大多数递推式都能这样口算。

步骤 3：均摊分析——ArrayList 扩容

import java.util.ArrayList;
import java.util.List;

public class AmortizedDemo {
    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();   // 默认容量 10
        for (int i = 0; i < 30; i++) {
            int before = list.size();
            list.add(i);                           // 容量不够时：翻倍 + 拷贝全部元素
            if (list.size() <= before) {
                System.out.println("发生扩容");
            }
        }
        System.out.println("最终大小: " + list.size());
    }
}

单次 add 在扩容那一刻是 O(n)，能不能说 add 是 O(n)？这会过度悲观。均摊分析算总账：容量 1→2→4→8…→n，历次拷贝总量 1+2+4+…+n/2 < 2n，摊到 n 次 add 上每次 O(1)。所以动态数组的尾插是「均摊 O(1)」。同类例子还有 HashMap 扩容、并查集的路径压缩。

步骤 4：空间复杂度别忽略隐式开销

import java.util.ArrayList;
import java.util.List;

public class SpaceCost {

    // O(n) 额外空间：递归深度 n，调用栈占 O(n)
    public static long sumRecursive(int n) {
        if (n == 0) return 0;
        return n + sumRecursive(n - 1);
    }

    // O(n) 堆空间：每层递归新建列表，合计 n+(n-1)+... ⇒ O(n²)
    public static List<Integer> build(int n) {
        if (n == 0) return new ArrayList<>();
        List<Integer> list = build(n - 1);
        list.add(n);
        return list;
    }

    public static void main(String[] args) {
        System.out.println(sumRecursive(100));
        System.out.println(build(5));
    }
}

常见认知盲区：只盯着显式数组，忘记递归深度本身就是空间复杂度；忘记字符串拼接、流收集、序列化产生的临时副本。判题平台限制用户程序内存时，堆、栈、元空间和这些瞬时峰值都要算进去。

步骤 5：把复杂度用到接口和 SQL 上

场景一：查询某用户的全部提交记录
  无索引全表扫描        O(N)，N=提交表总行数（5亿行）→ 灾难
  user_id 索引 + 分页   O(log N + k)，k=本页行数 → 毫秒级

场景二：排行榜 Top 50
  全量排序             O(N log N)，每次请求都做 → CPU 打满
  维护堆/Redis ZSET     插入 O(log M)，取 Top50 O(50 log M)，M=上榜人数

场景三：判题调度扫描全部实例找空闲机
  线性扫描             O(W)，W=实例数；上万实例且每秒千次调度时不可忽视
  维护空闲队列          offer/poll 均摊 O(1)

复杂度分析的终点不是写在注释里，而是在方案评审时用量级排除坏设计。

讲清楚要点

1. Big-O 描述渐近上界：关注 n 足够大时的增长，常数与低阶项被忽略；还有 Big-Ω（下界）、Big-Θ（同阶紧界），工程沟通中 Big-O 最常用且通常被当作「典型情况」讲。
2. 最好/最坏/平均/均摊是四种视角：如快排最坏 O(n²)、平均 O(n log n)；动态数组尾插最坏单次 O(n)、均摊 O(1)。评价方案要说清用的是哪种。
3. log 的底数在 Big-O 中可省略：换底只差常数系数，所以 O(log₂n) = O(log n)；但指数的底数不能省，O(2ⁿ) 与 O(3ⁿ) 不同阶。
4. 空间换时间是最常见的工程交易：哈希表、缓存、索引、预计算都在用更多存储换更低的时间复杂度；反之压缩、流式处理用时间换空间。
5. P / NP 的直觉：P 是能在多项式时间（n、n² 这一级）内解出的问题；NP 是答案能在多项式时间内被验证的问题。NP 完全（如旅行商判定、3-SAT、背包的一般形式）是 NP 中「最难」的一类，目前没人找到多项式解法，遇到它们应转向近似算法、贪心或限制输入规模，而不是硬刚。

你可能会懵的地方

• O(n) 和 O(n²) 在 n 很小时差不多，为什么这么计较？ Big-O 关心的是规模增长后的行为。n=10 时确实无所谓；n=100 万时，O(n) 是百万操作（毫秒级），O(n²) 是万万亿（算不完）。判题平台的数据只会增长，今天的 n=1000 不代表明年。

• 均摊 O(1) 和平均 O(1) 有什么区别？ 平均通常涉及概率假设（输入随机分布、哈希均匀）；均摊不需要概率，是对连续操作序列算总账——即使最坏的那一次确实发生了，摊薄后仍然便宜。ArrayList 尾插是均摊，HashMap 查找是平均。

• 递归方法的空间复杂度为什么不是 O(1)？ 每层调用在虚拟机栈上压入一个栈帧（局部变量、返回地址），深度 n 就占 n 份；尾递归优化（Java HotSpot 不保证做）可以消除它，所以不能默认递归不占空间。

• NP 完全问题等于「很难的问题」吗？ 不严谨。NP 完全有严格定义：属于 NP 且所有 NP 问题都能归约到它。它难在「没有已知多项式时间精确解」，但小规模可暴力、大规模可用近似解（如旅行商用启发式算法得到足够好的路线）。

• 复杂度低就一定快吗？ 不一定。Big-O 忽略常数，而常数受硬件、缓存、I/O、语言运行时影响。n 很小时 O(n²) 的插入排序可以赢 O(n log n) 的归并（第 3 课讲过）；I/O 密集场景下 O(n) 的内存计算远快于 O(log n) 但要跨网络的调用。先用复杂度选量级，再用基准测试定方案。

错法对照

错法	问题	正解
用「实际跑了 50ms」评价算法好坏	数据规模与硬件一变结论就失效	先给 Big-O，再用不同 n 实测验证增长
循环条件减半却写成 n = n - 1 的复杂度	把 O(log n) 误判/误写成 O(n)	明确每轮规模如何变化，再数层数
认为 HashMap 查找严格 O(1)	极端冲突下是 O(n)	表述为平均 O(1)，理解链地址退化
嵌套两层循环每层都查数据库	实际是 O(n²) 次网络往返，灾难	批量查询 O(1) 次 + 内存组装
遇到 NP 完全问题坚持要精确最优解	规模稍大即不可行	近似/贪心/限界，或与业务确认可接受误差

卡点急救

1. 一个接口数据量上来就雪崩：先数代码与 SQL 的操作量级（几层循环、是否走索引、N+1 查询），找到跨量级的那一步优先改，通常收益 10 倍起。
2. 递归/批处理内存溢出：算空间复杂度时计入递归深度与累积集合；改成迭代、分页流式处理（游标/分批），让空间与单批大小而非总量挂钩。
3. 容量评审说不清楚要几台机器：按「单请求操作量 × QPS」估算 CPU，按「对象大小 × 峰值数量」估算内存/带宽，用 Big-O 先确认方案随规模怎么涨，再乘以常数得到具体数字。

面试常问

• Big-O、Big-Ω、Big-Θ 的区别？工程中怎么用？ Big-O 是渐近上界，Big-Ω 是下界，Big-Θ 是同阶紧界（上下同阶）。工程中统一用 Big-O 表达「增长不超过某量级」，重点用于方案比较和规模增长预判。

• ArrayList 的 add 复杂度是多少？ 尾插均摊 O(1)：扩容时翻倍并拷贝，单次最坏 O(n)，但累计拷贝量小于 2n，摊到 n 次插入仍为 O(1)；指定位置插入因为要移动元素是 O(n)。

• 什么是 P、NP、NP 完全？对工程有什么意义？ P 是多项式时间可解，NP 是多项式时间可验证，NP 完全是 NP 中最难、彼此可归约的一类。意义：遇到排程、组合优化这类问题认出它没有已知多项式精确解，及时改用近似算法或加约束，而不是写出必然超时的暴力方案。

自测三问

1. 给你三段代码（单层循环、对半递归、双层嵌套），能否各在 30 秒内报出时间复杂度并说明理由？
2. n 从 100 万增长到 1 亿，O(n)、O(n log n)、O(n²) 的操作量分别约涨多少倍？
3. 为什么说「全表扫描是 O(n)」时要强调 n 是表的总行数而不是结果集大小？

小结一句话

Big-O 剥掉常数和硬件差异，只保留「规模翻倍、代价如何增长」这一个维度——它是程序员预判风险、比较方案、沟通性能的最小公倍语言。

延伸

• Khan Academy：算法效率与 Big-O 简介——渐进符号的入门权威讲解
• 《算法设计手册》（Skiena）主页——复杂度、NP 完全与实战取舍的经典参考
• Big-O Cheat Sheet——常见结构与排序算法复杂度速查
• 下一课：离散数学基础——复杂度里的对数、指数有了直观感受，下一课补上集合论、逻辑、图论与数论的直觉，看懂哈希、权限位与图算法背后的数学。