评价一个算法好不好，不能靠”感觉快慢”，得有一个统一的标尺——这就是复杂度分析。

而复杂度分析里最重要的工具，就是 Big-O（大 O 记号）。

为什么需要 Big-O

假设你写了一个查找函数，怎么评价它快不快？

有人会说”在测试机器上跑了 10ms”。但换个机器、换个数据量，结果就变了。

Big-O 解决的就是这个问题：它描述的是”随着数据量增大，运行时间怎么增长”的趋势，而不是具体的运行时间。

比如：

  • O(1)：数据量翻倍，时间不变
  • O(n)：数据量翻倍，时间也翻倍
  • O(n²)：数据量翻倍，时间变 4 倍

Big-O 到底怎么算

算 Big-O，核心就一句话：

忽略常数和低阶项，只保留增长最快的项。

举例：

1
3n² + 2n + 100  →  O(n²)

为什么可以忽略？因为当 n 足够大时，n² 那一项会完全主导，2n 和 100 都微不足道。

所以：

  • 3n → O(n)
  • n² + n → O(n²)
  • 2^n + n² → O(2^n)

常见复杂度量级（从小到大）

量级 名称 例子
O(1) 常数 数组按下标访问、哈希表查找
O(log n) 对数 二分查找、平衡树查找
O(n) 线性 遍历数组、链表
O(n log n) 线性对数 快排、归并排序、堆排序
O(n²) 平方 冒泡、选择排序、双重循环
O(2^n) 指数 子集枚举、斐波那契递归
O(n!) 阶乘 全排列

记住一个经验法则：能到 O(n log n) 就别 O(n²)，能到 O(log n) 就别 O(n)。

怎么估算一段代码的复杂度

1. 单层循环

1
for (int i = 0; i < n; i++) { ... }

循环 n 次，O(n)。

2. 嵌套循环

1
2
for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++) { ... }

外层 n 次，内层 n 次，O(n²)。

3. 每次循环规模减半

1
while (n > 1) { n = n / 2; }

每次减半，需要 log₂(n) 次，O(log n)。二分查找就是这个量级。

4. 递归

1
2
3
4
int fib(int n) {
    if (n <= 1) return n;
    return fib(n-1) + fib(n-2);
}

每次调用分成两个子调用，形成一棵二叉树，总节点数约 2^n，所以是 O(2^n)。这就是为什么递归求斐波那契慢得吓人。

空间复杂度

空间复杂度同理，衡量的是额外占用内存随数据量增长的趋势。

  • 原地算法（in-place）：O(1) 额外空间，比如快排、堆排
  • 需要辅助数组：O(n)，比如归并排序

时间和空间常常是权衡关系：用空间换时间（比如缓存、哈希表），或者用时间换空间（比如原地排序）。

均摊复杂度（摊还分析）

有一种特殊的情况：大部分时候操作很快，偶尔会很慢（比如动态扩容）。

比如 ArrayList 的 add：大部分时候直接加到末尾是 O(1)，但偶尔满了要扩容、整体拷贝一次是 O(n)。

如果把扩容的成本平均分摊到每一次 add 上，均摊下来还是 O(1)。这就是”均摊复杂度”。

所以别看到”偶尔 O(n)”就说 add 是 O(n)，要说”均摊 O(1)”。

写在最后

复杂度分析是基本功里的基本功。它的意义不只是应付面试，更在于：

写代码之前，先能判断”这个方案大概是什么量级、能不能撑住目标数据量”。

这是一种工程直觉。有了它，你才能在写代码前就淘汰掉那些”数据量一大必挂”的方案。

下一篇讲 SOLID 原则，把视角从”算法”拉回到”代码设计”。