时间与空间复杂度：衡量算法的尺子

同样一个需求，有人写出 O(n)，有人写出 O(n²)，在数据量小的时候看不出差别，数据一上去就是秒级和天级的差距。复杂度分析就是那把"写代码之前就能预估差距"的尺子。这篇文章把尺子的刻度讲清楚。

大 O 记号到底在说什么

先纠正一个最常见的误区：大 O 表示的不是代码跑了多少毫秒，而是当输入规模 n 增大时，耗时（或空间）的增长趋势。

// 这两个方法都是 O(n)，虽然实际耗时差很多
void loop1(int n) {
    for (int i = 0; i < n; i++) {
        System.out.println(i);   // 有 IO，单次很慢
    }
}
 
void loop2(int n) {
    for (int i = 0; i < n; i++) {
        int x = i + 1;           // 纯计算，单次极快
    }
}

大 O 忽略常数因子和低阶项。严格推导上，O 定义的是增长速度的上界：当 n 足够大时，f(n) 不会超过 c·g(n)（c 是常数）。工程上记住两条规则即可：

1. 常数丢掉：O(2n) 写成 O(n)，O(100) 写成 O(1)。
2. 只保留最高阶：O(n² + n) 写成 O(n²)，O(nlogn + n) 写成 O(nlogn)。

另外一个常见疑问：logn 的底数重要吗？不重要。log₂n 和 log₁₀n 只差常数倍（换底公式），统一记成 O(logn)。

常见复杂度阶对比

把七个常见阶放在一起感受差距，假设 n = 10⁵、机器每秒 10⁸ 次基本操作：

这张表反过来读就是刷题时的重要经验：看数据范围反推目标复杂度。LeetCode 提示 n ≤ 10⁵，基本锁定 O(n) 或 O(nlogn)；n ≤ 20，八成是回溯指数级搜索。

最好、最坏与平均复杂度

同一段代码，输入不同，执行次数可能差很多。以"在无序数组中找目标值"为例：

int find(int[] nums, int target) {
    for (int i = 0; i < nums.length; i++) {  // 最多 n 次
        if (nums[i] == target) return i;     // 找到就提前返回
    }
    return -1;
}

• 最好情况：目标在第一个位置，1 次比较，O(1)。
• 最坏情况：目标不存在或在最后，n 次比较，O(n)。
• 平均情况：假设每个位置等概率出现，期望比较 (n+1)/2 次，O(n)。

日常讨论和面试默认用最坏复杂度，因为它给出的是性能保证（上界）。平均复杂度需要概率假设，只有在特定场景（如快排、哈希表）才单独讨论。

均摊分析：动态数组扩容

有一类操作"偶尔很贵、大多数时候很便宜"，用最坏情况去评价会显得过惨。典型例子是 ArrayList 的自动扩容：

// 简化的动态数组插入
public void add(int val) {
    if (size == data.length) {           // 空间满了
        data = Arrays.copyOf(data, size * 2);  // 一次 O(n) 的搬运
    }
    data[size++] = val;                  // 平时这步是 O(1)
}

单看最坏情况，一次 add 可能触发 O(n) 的扩容。但把 n 次插入放在一起算总账：从容量 1 扩到 n，总共搬运 1 + 2 + 4 + ... + n ≈ 2n 次，平摊到每次插入就是 O(1)。这就是均摊分析：总成本除以操作次数，得到平均成本。

这个视角能解释不少现象：HashMap 扩容 rehash、StringBuilder 拼接、责任链式的批量处理，都因为"贵的操作发生得足够稀疏"而把均摊成本压到 O(1)。

空间复杂度与递归栈

空间复杂度统计的是额外开辟的空间，输入本身不算。几个关键点：

• int[] tmp = new int[n] → O(n)。
• 只用了有限几个变量 → O(1)。
• 递归调用本身占栈空间，深度就是额外空间量级。

// 递归求和：栈深 O(n)，额外空间 O(n)
long sum(int n) {
    if (n == 0) return 0;
    return n + sum(n - 1);
}
 
// 迭代求和：额外空间 O(1)
long sum2(int n) {
    long s = 0;
    for (int i = 1; i <= n; i++) s += i;
    return s;
}

这两个版本时间都是 O(n)，但空间一个是 O(n) 一个是 O(1)。刷题时很多人只盯着时间优化，结果在内存限制上翻车——原因往往就是没算递归栈这笔账。

逐行分析示范

最后用四个 Java 片段完整过一遍分析流程。

片段一：单层循环 → O(n)

int sum(int[] nums) {
    int s = 0;                    // 1 次
    for (int x : nums) {          // 循环 n 次
        s += x;                   // 每次体内 1 次 → 总 n 次
    }
    return s;                     // 1 次
}
// 执行次数：n + 2 → 时间 O(n)；额外变量 1 个 → 空间 O(1)

片段二：双重循环 → O(n²)

int countPairs(int[] nums) {
    int cnt = 0;                          // 1
    for (int i = 0; i < nums.length; i++)      // n 轮
        for (int j = i + 1; j < nums.length; j++)  // 每轮 n-i-1 次
            if (nums[i] == nums[j]) cnt++;
    return cnt;
}
// 内层总次数：n-1 + n-2 + ... + 1 = n(n-1)/2 → 时间 O(n²)；空间 O(1)

注意内层是从 i+1 开始而不是 0 开始，这影响的是精确次数（减半）而非阶数——这就是"常数和低阶项不影响大 O"的体现。

片段三：循环变量倍增 → O(logn)

int cnt = 0;
for (int i = 1; i < n; i *= 2) {   // i: 1, 2, 4, 8, ...
    cnt++;
}
// i 每轮翻倍，k 轮后 i = 2^k ≥ n → 执行 log₂n 次 → 时间 O(logn)

片段四：嵌套但内外相关 → O(nlogn)

for (int i = 0; i < n; i++) {      // 外层 n 轮
    for (int j = 1; j < n; j *= 2) {   // 内层 logn 轮
        // O(1) 操作
    }
}
// 乘法关系：n × logn → 时间 O(nlogn)；空间 O(1)

分析方法总结成一句话：数出基本操作关于 n 的精确次数，丢常数、留最高阶。两层循环之间是"相加"（顺序执行）还是"相乘"（嵌套执行）是判断的核心。

易错点清单

• 把 O(2n)、O(3n) 当成不同复杂度——常数不计入。
• 认为 O(n²) 一定比 O(n) 慢——n 很小时前者可能更快，大 O 只保证 n 足够大之后的趋势。
• 忘记递归占栈空间，以为没开数组空间复杂度就是 O(1)。
• 混淆"最坏复杂度"和"均摊复杂度"：单次操作可能 O(n)，但均摊 O(1) 的说法只在总账视角下成立。
• 忽视库函数的复杂度：Arrays.sort() 是 O(nlogn)，把 sort 套进循环里整体就可能是 O(n²logn)。

对应 LeetCode 题目

复杂度分析本身没有单独的题目，但它是所有题目的隐形考点。推荐用下面几道题练"估算"：

参考

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