复杂度分析

这一课你将能做到

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)）、。它描述上界与增长趋势，不描述单次操作是 1 纳秒还是 1 毫秒——但当复杂度跨量级时，常数差异毫无意义，O(n) 永远赢 O(n²)。