名词解释教学工作区 · 课程 0003 · 形态 对比组 · 约 5 分钟 · 前置:0002 · 编辑器 / 编译器 / 解释器 / IDE · 2026-10-01

时间复杂度与空间复杂度:同一个算法的两笔账

1 | 定义

这两个词数的是同一个算法的两笔开销,只是数的东西不同:一笔数要做多少件事,一笔数要占多少地方。各给一条正式定义和一句生活说法:

• ① 时间复杂度(time complexity) 用输入规模 n 描述一个算法要做多少次基本操作(比较、赋值、访问)的量级,并扔掉常数与低阶项;它说的是"数据量变大时操作次数怎么长",不是"跑了几毫秒"。 就像约人见面先估"路上要多久":不看今天堵不堵、开什么车,只看路从一站变成十站,工夫大致也要跟着涨。
• ② 空间复杂度(space complexity) 用同样的方式描述算法在运行中额外占用的内存峰值,输入数据本身占的那一份不算。 就像出门前算一趟车得占几个座位:自己坐的那个不算,只看顺路还要捎上几个箱子。

一句话把两者绑在一起:它们都只回答"规模翻倍时会怎么长",答案写成大 O 记法(Big O notation,写作 O(...)),所以换机器、换输入都作数。

2 | 它们解决什么麻烦

这两个词要解决的麻烦只有一个:同一件事有很多种写法,得有一种不依赖具体机器的方式,比出谁更扛得住规模增长。

• ① 秒表量不出可比性。同一段代码在高配机器和单片机上能差几十倍;同一个排序,输入本来就排好和完全逆序,耗时天差地别 —— 测出来的数字换台机器、换份数据就作废。
• ② 小规模看不出来,大规模又来不及改。数据只有几十条时任何写法都很快;真正的差距要等规模涨上去才露头,而那时代码早已铺开,再换写法代价很大。
• ③ 两笔开销容易被混成一句"好不好"。时间不够只是慢,内存开不出来就是跑不了;把两笔账混在一起,在内存紧的地方就会挑错东西。
• ④ 不可能每次都拿全量数据试。需要一条只看代码、不看机器就能算出增长形状的判断依据 —— 这就是复杂度给出的东西。

3 | 特征矩阵

两行都是能一眼看出来的事,不是"它是什么":拿一段代码分别问两列问题,哪一行答得上来,它数的就是哪笔账。

"会不会随规模增长"这一列两行正好相反,是两笔账最容易混的地方。哈希表还顺带说明另一件事:同一个结构可以同时有平均 O(1) 与最坏 O(n) 两个量级,因为口径不同。

两行共用一套读法:大 O 记法写的是增长趋势,不是具体数字,所以换机器、换输入它都不变。

4 | 各自怎么做

• ① 时间这一侧先找出随规模变的那一步。在比较、赋值、访问这些操作里,挑出次数真的随数据量变化的那一种,把它的次数写成 n 的函数;其余与数据量无关的操作,统统归成固定开销。
• ② 只留最高阶的那一项。n 足够大时最高阶项会压倒其余全部,所以 3n² + 100n + 5000 写成 O(n²);n 还小的时候,反倒是那个 5000 在决定快慢 —— 这正是后面"小数据量下 O(n²) 可能更快"的根源。
• ③ 再把系数也扔掉。2n 与 10n 同属 O(n):大 O 说的是"顶多按这个量级长",具体倍数多少,留给实测去分。
• ④ 空间这一侧数两件事。一是额外(输入本身占的那一份不算),二是同时活着(数峰值,不是把全程开过的内存加起来)。
• ⑤ 递归要算调用栈(call stack)。每深入一层就有一份调用记录同时活着,深度 n 的递归,光这一项空间就是 O(n) —— 代码写得出来却跑不起来,常常就卡在这里。
• ⑥ 量级的直观差别:O(1) < O(log n) < O(n) < O(n log n) < O(n²)。把数据量从一千涨到一百万:O(log n) 只多几次操作,O(n) 多一千倍,O(n²) 多一百万倍 —— 差距是被规模放大的,不是被机器放大的。
• ⑦ 偶尔贵一次也能摊平。哈希表扩容那一下要把整张表重排一遍,单看那次是 O(n);但把许多次操作合起来算,平均仍是 O(1) —— 这种口径叫摊还(amortized)。

5 | 各自的代价

• ① 只描述增长趋势,给不出绝对耗时。同一量级的两种写法谁更快,它答不上来 —— 常数被扔掉了。而常数的一半取决于谁来执行这段代码:同一个算法交给不同的编译器或解释器,跑出来就是两个数。真要选谁,还得自己测。
• ② 被藏起来的常数会骗人。数据量小的时候,常数更小的那个写法完全可能先到终点,O(n²) 赢 O(n) 也常见。量级只在数据量大到让最高阶项压倒其余时才说了算。
• ③ 最坏、平均、摊还是三个口径。报最坏得到的是安全下限,报平均才接近日常;拿一门的"最坏"去比另一门的"平均",比出来的结论没有意义。
• ④ 空间这一侧最容易被漏算。递归没返回的每一层、临时开的表、缓存的副本都要算进去;漏了它,代码在内存紧的机器上就是跑不起来。
• ⑤ 它替代不了实测。复杂度给的是趋势,给不了"这一台机器上跑多少毫秒";把量级当性能结论,早晚要翻车。

6 | 区分使用场景

先把这一句话归位:它在数操作次数,还是在数内存占用。前者是时间那一侧,后者是空间那一侧。

再按手头这件事挑,每条都落在一侧:

• ① 内存很紧(嵌入式、单片机、树莓派这类单板计算机)→ 优先省空间。宁可多算几遍,也别开一块跟数据量一样大的表:这里内存开不出来就是跑不起来,慢一点还能忍。
• ② 响应时间卡得死(实时控制、界面每次刷新都要跟手)→ 优先省时间。多占一点内存换更短的等待,是划算的。
• ③ 数据量本来就小(几百条以内)→ 别过早优化。两种写法都快,这时挑写得清楚的,比挑量级更低的更值。
• ④ 同一份结果要反复用 → 用空间换时间。把算过的结果放进缓存(cache),下次直接取;Gradle 这类构建工具的增量构建就是这个思路 —— 上次的产物留着,能复用就不重算。

两笔账不是二选一,多数时候是拿一换一。反过来也提醒一句:能提前算好的,就别留到每次都要用的时候再算。

7 | 常见误解

• ① 「O(n) 一定比 O(n²) 快。」要看规模与常数。数据只有几十条时,常数更小的那个写法常常先到;只有数据量大到让最高阶项压倒其余,量级才开始说了算。
• ② 「复杂度就是跑一遍计个时。」计时量的是这一台机器、这一份输入;复杂度是从代码里数出来的趋势,换机器、换输入都不变 —— 两者回答的不是同一个问题。
• ③ 「空间复杂度不重要。」时间不够只是慢,内存开不出来是直接跑不了。递归没返回的每一层、临时表、缓存副本,都在额外的这一份里。
• ④ 「O(1) 就是快。」它只说操作次数不随数据量变。同为常量级的两个操作,耗时也能差好几个数量级。

8 | 练习

三题自测,每题只有一个正确选项;选完立刻看到解释。