Skip to content
Published on

实战 Big-O：没有数学焦虑的复杂度

🇰🇷KO🇺🇸EN🇯🇵JA🇨🇳ZH
필사 모드
分享
Authors

引言 — Big-O 带来的焦虑

一提到 Big-O，很多人会想起大学时代的极限和证明,不由得畏缩。但在实务中，Big-O 不是考试题，而是一件直觉的工具。它是为了回答一个非常实用的问题:"如果输入变成十倍，这段代码会慢多少?"

这篇文章先把数学上的严谨放到一边，只整理出一个在职工程师所需要的那份 Big-O。目标不是极限也不是证明,而是培养判断"这段代码在大输入下扛得住吗"的直觉。如果想亲眼看看不同复杂度的排序算法是怎样不同地运作的,不妨把本站的排序可视化工具一起打开看看。

O() 实际上意味着什么

Big-O 表示的是当输入规模变大时，运行时间(或内存)如何增长。关键词是"增长(growth)"。它说的是增长的形状,而不是绝对速度。

这里有几个重要的性质。

  • 丢弃常数:2n 和 100n 都是 O(n)。Big-O 只看输入变大时的趋势,所以会忽略前面的常数倍数。
  • 丢弃低阶项:n² + n + 5 是 O(n²)。当 n 非常大时,n² 这一项会压倒其余部分,所以只保留主导项。
  • 以最坏情况为基准:通常 Big-O 说的是最坏情况(worst case)。它给出的不是"运气好就快",而是"无论多差,也不会差过这个程度"的保证。

这里有一个容易被误解的地方。Big-O 不会告诉你"这段代码要花几秒"。它只告诉你"输入变大时,会沿着怎样的曲线变慢"。所以要比较两个算法的实际速度时,光靠 Big-O 有时是不够的,这一点后面还会再提到。

常见的复杂度类别

实务中会遇到的复杂度,其实就压缩成那么几种。让我们逐一配上现实例子来看。

O(1) — 常数时间。 与输入规模无关,始终花费相同的时间。数组的索引访问、哈希表(字典)的查找是典型代表。

# 输入无论多大,都只需一次访问
value = my_dict[key]      # O(1)
first = my_list[0]        # O(1)

O(log n) — 对数时间。 每一步都把问题规模减半。有序数组中的二分查找是典型。即使输入有一百万个,大约 20 步就能结束。

# 在有序数组中每次丢弃一半 -> O(log n)
import bisect
idx = bisect.bisect_left(sorted_list, target)

O(n) — 线性时间。 把输入扫描一遍。在列表中找最大值、统计满足条件的元素数量,这类"把每个元素都看一遍"的大多数工作都属于这里。

# 把每个元素恰好看一次 -> O(n)
total = 0
for x in numbers:
    total += x

O(n log n) — 拟线性时间。 高效排序算法(归并排序、快速排序、Timsort)的复杂度。各语言标准库的 sort() 大多属于这一类。它实际上是"给 n 个元素排序"这项任务的下限。

O(n²) — 二次时间。 比较所有配对的工作。它源自两个嵌套循环各自遍历整个输入的形式。输入小时还好,一旦变大就会急剧变慢。

# 比较所有配对 -> O(n²)
for i in range(len(items)):
    for j in range(len(items)):
        compare(items[i], items[j])

这些类别之间实际差多少,用一张表看就有感觉了。

nO(log n)O(n)O(n log n)O(n²)
10约 310约 33100
1,000约 101,000约 10,0001,000,000
1,000,000约 201,000,000约 2000 万1 万亿

n 为一百万时,O(n²) 是一万亿次运算。就算是现代计算机也要跑上好一阵子。相比之下 O(n log n) 只有 2000 万次,眨眼就完成。这一张表就把"为什么算法选择很重要"浓缩地展示了出来。

常数取胜的时候 — 小 n 与缓存

这里出现了实务中的微妙之处。Big-O 讲的是"n 足够大"时的故事。可现实中的 n 常常很小。而当它小的时候,被丢弃的常数会重新变得重要。

比如来看看 O(n²) 的插入排序和 O(n log n) 的归并排序。理论上归并排序应该胜出,但当 n 小到 10~20 这种程度时,插入排序往往更快。这是因为归并排序背负着递归调用、数组切分、为合并分配临时数组这类附带开销(常数)。实际上,Python 和 Java 的标准排序在小区间内都会切换成插入排序。

缓存对常数的影响也很大。现代 CPU 读取连续内存时要快得多(缓存局部性)。所以即使理论上的复杂度相同或稍差,连续访问内存的数组,实际上往往比东奔西跑追踪指针的链表更快。

  只看理论复杂度的话:
    链表中间插入 O(1)  vs  数组中间插入 O(n)  -> 链表赢?

  现实中(因为缓存局部性):
    在中小规模下,数组胜过链表的情况很常见
    -> 追踪指针带来的缓存缺失,比遍历数组查找的成本更高

教训是这样的。Big-O 告诉你"大局",但实际性能取决于常数和硬件。当两个候选方案的 Big-O 相同或相近时,答案不在理论里,而在于实测。

潜藏的 O(n²) — 嵌套循环与 N+1 查询

O(n²) 之所以可怕,是因为它常常很难被察觉。明摆着的双重 for 循环容易发现,但陷阱通常都藏得很深。

第一个陷阱是藏在循环里的线性操作。

# 表面上只有一个循环,看起来像 O(n),但...
result = []
for item in items:           # 反复 n 次
    if item in result:       # 列表的 in 检查是 O(n)!
        continue
    result.append(item)
# 实际上是 O(n²) - 每次迭代都要把 result 全部扫一遍

在 item in result 中,由于 result 是列表,in 检查每次都是 O(n)。这被放进了 O(n) 的循环内部,整体就变成了 O(n²)。解决办法是把 in 检查变成 O(1),也就是使用集合(set)。

# 集合的 in 检查是 O(1) -> 整体是 O(n)
seen = set()
result = []
for item in items:
    if item in seen:
        continue
    seen.add(item)
    result.append(item)

第二个陷阱是后端开发中臭名昭著的 N+1 查询问题。

# 取回 100 篇文章(1 次查询)之后...
posts = db.query("SELECT * FROM posts LIMIT 100")
for post in posts:
    # 用单独的查询取每篇文章的作者 -> 100 次查询!
    author = db.query("SELECT * FROM users WHERE id = ?", post.author_id)
    print(author.name)
# 总共 1 + 100 = 101 次查询

文章数量越多,查询次数就线性增长,数据一旦变大,响应就会急剧变慢。由于每次查询都带着一次网络往返成本,体感只会更糟。解决办法是用一次查询把所需数据一并取回来(join、IN 子句,或 ORM 的 eager loading)。

# 一次性取回所需的作者 -> 2 次查询
posts = db.query("SELECT * FROM posts LIMIT 100")
author_ids = [p.author_id for p in posts]
authors = db.query("SELECT * FROM users WHERE id IN (...)", author_ids)
# 总共只用 2 次查询就解决了

N+1 光看代码就是个普通循环,很难被发现。加上 ORM 在背后代替你发出查询,就更加隐蔽了。养成开启查询日志、确认"打开这个页面一次要发出多少次查询"的习惯,能防住这个陷阱。

别忘了空间复杂度

Big-O 不只用于时间。空间复杂度用同样的方式表示算法额外使用了多少内存。

# 时间 O(n),空间 O(1) - 额外内存只是几个变量
def sum_list(numbers):
    total = 0
    for x in numbers:
        total += x
    return total

# 时间 O(n),空间 O(n) - 建立一个与输入规模成比例的新列表
def double_all(numbers):
    return [x * 2 for x in numbers]

时间和空间常常是一种权衡(trade-off)关系。前面去重时用集合就是一个很好的例子。用 seen 集合多花 O(n) 的额外内存作为代价,把时间复杂度从 O(n²) 降到了 O(n)。这是多花一点内存,换来时间上的巨大节省。

在实务中,空间复杂度在大规模数据面前尤其重要。如果文件比内存还大,"全部读进列表"这种 O(n) 空间的做法根本行不通。这时就得换成一行一行流式处理的方式(空间 O(1))。就算时间再快,内存一旦爆掉,程序也跑不起来。

分摊成本 — 动态数组的秘密

一个微妙但重要的概念是分摊(amortized)复杂度。它的视角是:"偶尔会有一次昂贵的操作,但摊到很多次上平均下来是便宜的。"

Python 列表或其他语言的动态数组中,向末尾添加元素的 append 就是典型代表。大多数时候是 O(1),但当数组满了的时候,就得重新分配一个更大的数组,并把已有元素全部复制过去。这次复制是 O(n)。

  在容量为 4 的数组上持续 append:
  [a][b][c][d]  <- 满了
  下一次 append -> 扩容到 8,复制 4 个元素(这一次是 O(n))
  [a][b][c][d][e][_][_][_]
  之后的 5 次 append 又各自变回 O(1)

不过在扩容数组时,通常会把容量翻倍。正因如此,昂贵的复制操作发生的频率会越来越低。把添加 n 个元素的总成本加起来除以 n,每次 append 的平均成本会收敛到 O(1)。这就是分摊 O(1)。

关键在于,不要只盯着单次最坏情况(O(n))就被吓到。只有同时看清那次昂贵操作发生得有多稀少,才能正确理解实际的性能。哈希表的插入按同样的原理也是分摊 O(1)。

什么时候该停止优化

最后,也许是最重要的实务直觉。学了 Big-O 之后,会想把所有代码都拿去优化,但大多数代码根本不需要优化。

唐纳德·克努斯有一句名言:"过早优化是万恶之源(premature optimization is the root of all evil)。"对一段连是不是瓶颈都还不知道的代码提前做复杂的优化,只会损害可读性,没有任何收益。

判断标准可以这样归纳:

  • 如果 n 很小,而且以后也会一直很小:即使是 O(n²) 也没关系。用双重循环遍历一个 100 个元素的列表,眨眼之间就完成了。清晰的代码胜过优化过的代码。
  • 是不是热路径:这段代码是每秒被调用几千次的路径,还是一天才跑一次的批处理?先优化频繁执行的地方。
  • 先测量:不要凭猜测,用性能分析器(profiler)找出真正的瓶颈。开发者的直觉常常对瓶颈的位置判断错误。找出吃掉 90% 时间的那 10%,只在那里下功夫,才是高效的做法。
  • 先算法,后常数:如果确实需要优化,把 O(n²) 改进成 O(n) 这样的算法改进,效果要远远大于削减常数的微调。

换句话说,Big-O 不是一道"永远要优化"的命令,而是一台"提前发现有变大风险的地方"的雷达。对小数据选择清晰的代码,对会变大的数据选择良好的复杂度,这种平衡感才是实务的核心。

结语

Big-O 不是数学考试,而是工程师的直觉工具。它是为了回答"输入变大时,这段代码会怎样"这个问题而存在的。只要把 O(1)、O(log n)、O(n)、O(n log n)、O(n²) 这几个类别刻进身体里,大多数情况都能判断了。

同时也不要忘记,Big-O 并不是全部。在小 n 下,常数和缓存会赢;真正的瓶颈得靠性能分析器去找;而对大多数代码来说,清晰比优化更重要。懂得复杂度,就是懂得何时该优化,而更重要的是,懂得何时可以不用优化。

如果想亲眼看看排序算法在同一份数据上表现出多大的差异,不妨到排序可视化工具里,亲身感受一下 O(n²) 和 O(n log n) 之间的区别。这会比表格里的数字生动得多。

参考资料

Discuss on Twitter • View on GitHub