核心 · 算法第 1 课 / 共 8 课免费阅读

大 O：数步数 · 数据结构与算法

怎么判断代码在一百万条数据时还快不快？

为什么需要它

在 10 条数据上瞬间完成的代码，到 1000 万条可能要跑几个小时。面试官一定会问「复杂度是多少？」，真实系统也会因为选错方法而崩掉。大 O 就是描述工作量随输入增长的速度的简写。

直觉理解

不要掐表计时，而是数步数，看它随 n 怎么增长：

代码的样子	n 个元素要多少步	大 O
一个固定操作	1	O(1)
一层循环遍历列表	n	O(n)
循环里套循环	n × n	O(n²)
每次把问题砍掉一半	大约 log₂ n	O(log n)

常数和小项都忽略：3n + 5 仍然是 O(n)。重要的是形状：n 从 1,000 变到 1,000,000，O(n) 的工作量涨 1,000 倍，O(n²) 却涨 1,000,000 倍。

定义

时间复杂度

How the number of steps grows with the input size n, written in Big-O, such as O(n) or O(n²). It describes the worst case unless said otherwise.
步数随输入规模 n 增长的方式，用大 O 表示，比如 O(n) 或 O(n²)。没有特别说明时，指的是最坏情况。

空间复杂度

How much extra memory grows with n. Using a set of seen items is O(n) space; a few variables is O(1).
额外占用的内存随 n 增长的方式。用一个集合记录见过的元素是 O(n) 空间；只用几个变量是 O(1)。

示例

数一数步数

动手试试

两个函数都回答「有没有重复？」。数一数它们各做了多少次比较。

def dup_pairs(xs):
    steps = 0
    for i in range(len(xs)):
        for j in range(i + 1, len(xs)):
            steps += 1
    return steps

def dup_set(xs):
    steps = 0
    seen = set()
    for x in xs:
        steps += 1
        seen.add(x)
    return steps

for n in [10, 100, 400]:
    data = list(range(n))
    print(n, dup_pairs(data), dup_set(data))

逐步执行

L4每一对都要比较：大约 n × n / 2 次。
L11只走一遍：n 步。
L18400 个元素时：79800 对 400。元素多 4 倍，配对多 16 倍。400 79800 400

常见错误

藏起来的循环

x in 某个列表 和 列表.index(x) 都会遍历列表。放在另一个循环里，就是 O(n²)。x in 某个集合 平均是 O(1)。

用小数据计时

10 条数据时什么都快。先分析增长的形状，再用大输入测试。

小测验

1. 一个函数把列表遍历一次，每个元素做固定量的工作。复杂度是多少？

AO(1)
BO(n)
CO(n²)

查看答案

答案：B

n 个元素 × 固定的工作量 = O(n)。

2. 这段代码会输出什么？

n = 16
steps = 0
while n > 1:
    n = n // 2
    steps += 1
print(steps)

A
```
4
```
B
```
8
```
C
```
16
```

查看答案

答案：A

16 → 8 → 4 → 2 → 1：砍了四次一半。就是 log₂ 16。

动手练习

3 道练习，分三层：先预测程序的输出，再按新需求改程序，最后从零写一个。代码在浏览器里运行，提交马上判题。

预测输出数工作量
准确写出这段程序的输出。
改需求改成 O(n)
has_duplicate 比较每一对，是 O(n²)。改写它，用一个集合记住见过的元素，让它变成 O(n)。速度测试用 5,000 个互不相同的数。
从零写最大差值
写一个函数 max_gap(xs)，返回非空列表中任意两个数之间的最大差值（最大值减最小值）。遍历一次列表就够了：O(n)。

在互动课里练这一课

打开互动课，这些例子都能直接改、直接运行，练习题提交马上判题。免费开始，不用注册。

打开互动课课程地图

本课术语

术语	中文	英文定义
Big-O notation	大 O 记法	A description of how work grows with input size, such as O(n).
Time complexity	时间复杂度	How the number of steps grows with n.