时间复杂度与空间复杂度

为什么需要复杂度分析

写代码不难，写好代码才难。衡量一段代码"好不好"，有两把尺子：它跑得有多快（时间），以及它吃了多少内存（空间）。

但直接测量运行时间存在问题——同一段代码在配置不同的机器上跑出的毫秒数相差悬殊，在不同数据量下的表现也截然不同。在真实的工程评估中，我们需要的不是"在我的 MacBook Pro 上跑了 3ms"，而是一个与硬件无关、能反映规律的度量。

这就是复杂度分析的价值：它用数学语言描述随着输入规模增大，算法消耗的时间/空间以什么速率增长。

大 O 记法

大 O 记法（Big O Notation）是描述算法复杂度的标准语言。

f(n) = O(g(n)) 的直觉含义：当输入规模 n 足够大时，f(n) 的增长速度不超过 g(n) 的某个常数倍。换句话说，大 O 描述的是渐近上界——最坏情况下的增长趋势。

化简规则

计算出精确的操作数之后，按以下规则化简为大 O 形式：

1. 去掉常数系数：3n → O(n)，因为常数 3 不影响增长趋势
2. 只保留最高阶项：n² + 100n + 50 → O(n²)，低阶项在 n 很大时可忽略
3. 不同变量分开：若有两个独立规模参数，写成 O(m + n) 而非合并

// 示例：计算下面这段代码的时间复杂度
int sum = 0;                    // O(1)
for (int i = 0; i < n; i++) {  // 循环 n 次
    sum += i;                   // O(1)
}
// 总操作数 ≈ 1 + n × 1 = n + 1
// 化简后：O(n)

常见时间复杂度

从快到慢排列，并附上直觉感受：

O(1)：常数时间

无论 n 多大，执行次数固定。常见于哈希表的 get/put、数组的随机访问。

int first = arr[0];          // O(1)
map.put("key", "value");     // O(1) 摊销

O(log n)：对数时间

每次操作把问题规模缩小一半。这就像查字典——每翻一页都能去掉一半的候选范围，100 万个词只需翻约 20 次。

// 二分查找：每次排除一半
int left = 0, right = n - 1;
while (left <= right) {
    int mid = left + (right - left) / 2;
    if (arr[mid] == target) return mid;
    else if (arr[mid] < target) left = mid + 1;
    else right = mid - 1;
}

O(n)：线性时间

通常是一个单层循环遍历所有元素。

for (int x : arr) {   // 遍历 n 个元素
    sum += x;
}

O(n log n)：线性对数时间

通常由"对每个元素做一次 O(log n) 的操作"产生，或者"分治 + 合并"。归并排序、快速排序（平均）都属于这一级别。

O(n²)：平方时间

典型特征是双层嵌套循环，每层都是 O(n)。

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        // 每对 (i, j) 都处理一次
    }
}

O(2ⁿ) 与 O(n!)：指数和阶乘

这两类只在 n 极小时才可接受。暴力枚举所有子集是 O(2ⁿ)（每个元素选或不选），暴力枚举全排列是 O(n!)（n 个位置依次填入）。

复杂度分析的三种情形

同一个算法面对不同输入，性能可能截然不同。因此需要区分三种情形：

最坏情况（Worst Case）

在所有可能的输入中，算法耗时最长的情况。这是最常用的分析对象，因为它提供了性能保证的上界。

评估系统“时间复杂度”时，架构师默认关注的是最坏情况。

顺序查找 target：
- 最好情况：target 在第一位，O(1)
- 最坏情况：target 在最后一位，或不存在，O(n)
- 通常说：时间复杂度 O(n)

最好情况（Best Case）

在最理想输入下的消耗，实际意义有限，通常不单独关注。

平均情况（Average Case）

对所有可能输入的期望消耗，分析时需要概率模型，较为复杂。快速排序的平均时间复杂度 O(n log n) 就是平均情况分析的结论。

摊销复杂度

摊销复杂度（Amortized Complexity）处理的是这样一种场景：大多数操作很快，偶尔有一次很慢，整体均分下来每次操作的代价依然可接受。

以 ArrayList 的 add() 方法为例。数组底层容量有限，大多数时候 add 只需 O(1) 赋值；但当容量满了，需要扩容——分配 2 倍空间并拷贝所有元素，这一次是 O(n)。

把扩容的代价"摊"到之前的每次 add 上：

容量从 n 扩到 2n 时，需要拷贝 n 个元素。
但在这之前，已经执行了 n 次 O(1) 的 add。
平均每次 add 的额外代价 = n / n = O(1)

所以 ArrayList.add() 的摊销时间复杂度是 O(1)，即便偶尔会触发 O(n) 的扩容。

操作序列：add add add ... add (第 n+1 次触发扩容)
代价：      1   1   1  ...  1       n
总代价：n + n = 2n
平均代价：2n / (n+1) ≈ O(1)  ✓

这就像一家工厂平时生产稳定，偶尔需要停线检修，但把检修时间平摊到每件产品上，单件成本依然可控。

空间复杂度

空间复杂度衡量算法额外使用的存储空间随输入规模的增长趋势。注意关键词"额外"——输入数据本身占用的空间通常不计入。

三类空间消耗

1. 暂存变量：临时变量、局部变量
2. 栈帧空间：递归调用产生的调用栈
3. 输出数据：算法产生的结果（有时计入，有时不计）

常见空间复杂度

O(1)：常数空间

只使用固定数量的额外变量，无论 n 多大，额外内存不变。

// 双指针反转数组：O(1) 额外空间
int left = 0, right = arr.length - 1;
while (left < right) {
    int tmp = arr[left];
    arr[left++] = arr[right];
    arr[right--] = tmp;
}

O(n)：线性空间

额外空间与输入规模成正比，通常出现在需要存储中间状态的情况。

// 创建辅助数组：O(n) 空间
int[] copy = Arrays.copyOf(arr, arr.length);

O(n) 递归调用栈

递归函数的调用栈深度即为空间复杂度。

// 递归求 n!：递归深度 n，空间复杂度 O(n)
int factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);
}

调用栈：
factorial(5)
  factorial(4)
    factorial(3)
      factorial(2)
        factorial(1)  ← 栈最深处，占用 5 层栈帧

O(log n)：对数空间

二分查找的递归版本，每次问题规模减半，递归深度 log n。

int binarySearch(int[] arr, int left, int right, int target) {
    if (left > right) return -1;
    int mid = left + (right - left) / 2;
    if (arr[mid] == target) return mid;
    if (arr[mid] < target) return binarySearch(arr, mid + 1, right, target);
    return binarySearch(arr, left, mid - 1, target);
}
// 空间复杂度：O(log n)，来自递归深度

时间与空间的权衡

时间和空间往往是一对矛盾：用更多内存换取更快速度（空间换时间），或节省内存代价性能下降（时间换空间）。

经典案例：

在架构评审中，当我们给出一个基础解法后，通常需要进一步思考："能优化时间复杂度吗？允许使用更多空间"——这正是在引导你思考这种权衡。

如何快速估算复杂度

工程评估时快速心算的口诀：

单层循环            → O(n)
双层嵌套循环        → O(n²)
每次减半（二分）    → O(log n)
分治 + 合并         → O(n log n)
枚举所有子集        → O(2ⁿ)
枚举全排列          → O(n!)
递归深度 × 每层工作 → 乘法原则

嵌套循环的特殊情况：

// 外层 n，内层从 i 到 n
// 总操作数 = n + (n-1) + ... + 1 = n(n+1)/2 ≈ O(n²)
for (int i = 0; i < n; i++) {
    for (int j = i; j < n; j++) {
        // ...
    }
}

// 内层不依赖 i，但 n 不同
// 外层 n，内层固定 k 次 → O(nk) = O(n)（k 为常数）
for (int i = 0; i < n; i++) {
    for (int j = 0; j < 10; j++) {  // 常数 10
        // ...
    }
}

工程实践中的常见误区

误区一：混淆时间复杂度和实际运行时间

O(n²) 不一定比 O(n log n) 慢——当 n 很小时，常数系数可能逆转结果。但生产系统中处理的通常是大 n 场景，渐进复杂度才是关键。

误区二：忽略递归的空间复杂度

很多人只分析时间复杂度，忘了递归的调用栈也消耗空间。尤其是深度优先搜索（DFS）等递归算法，空间复杂度可能是 O(n) 或 O(树的高度)。

误区三：哈希表操作不一定是 O(1)

哈希表在良好实现下的平均查找是 O(1)，但最坏情况（所有元素哈希冲突）是 O(n)。Java 的 HashMap 在同一 bucket 中元素超过 8 个时，会将链表转为红黑树，将最坏情况从 O(n) 降至 O(log n)。

小结

掌握了复杂度分析，就有了衡量所有后续算法的"度量衡"。从下一篇开始，每道题都会给出时间和空间复杂度的分析。