| English | 释义 | 拼音 |
|---|---|---|
| Big-O/bɪɡ əʊ/ | 大O表示法 | dà O biǎo shì fǎ |
| time complexity/taɪm kəmˈpleksɪti/ | 时间复杂度 | shí jiān fù zá dù |
| space complexity/speɪs kəmˈpleksɪti/ | 空间复杂度 | kōng jiān fù zá dù |
| depth-first/depθ fɜːst/ | 深度优先 | shēn dù yōu xiān |
| breadth-first/bredθ fɜːst/ | 广度优先 | guǎng dù yōu xiān |
| binary tree/ˈbaɪnəri triː/ | 二叉树 | èr chā shù |
会比宇宙活得更久的算法
- 一位推销员必须访问 25 座城市并按最短路线回家。把每种顺序都试一遍,大约有 $10^{23}$ 种。一台每秒检查十亿种的机器要花三百万年。
- 再加一座城市,工作量乘以 25。这不是一台需要更快的计算机;这是一种在任何速度、任何硬件上都永远行不通的方法。
- 在写程序之前就知道这一点,正是复杂度分析的用途。它是"选择一个算法"和"几个月后发现你的算法扩展不了"之间的差别。
- 这一课讲时间和空间的大O表示法(Big-O),以及抽象数据类型怎样塑造建立在它们之上的算法。
时间复杂度
- 时间复杂度(time complexity)描述运行时间怎样随输入规模 $n$ 增长。它用大O表示法书写,只保留主导项、丢掉常数。
- $O(1)$ 常数,时间根本不依赖 $n$。$O(\log n)$ 对数,如二分查找。$O(n)$ 线性,如线性查找。$O(n \log n)$,那些好的排序。$O(n^2)$ 平方,如冒泡和插入排序。
- 丢掉常数的理由是:它们会被淹没。一个 $O(n^2)$ 的算法在 $n = 10$ 时可能胜过 $O(n \log n)$ 的,但在 $n = 10{,}000$ 时,常数救不了它。

曲线只交叉一次,此后一切都由阶决定
How running time grows with n
Slide n upward and compare the curves: O(1) and O(log n) stay almost flat, O(n) rises steadily, O(n²) explodes. This is why Big-O — not a stopwatch — is how we compare algorithms on large inputs.
Which Big-O describes binary search?
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
Halving the range each step is logarithmic — O(log n).
Which Big-O describes bubble sort in the worst case?
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
Two nested loops over n elements give O(n²).
Match each algorithm to its time complexity.
难度 2/5 · 今日首次完成可获 140 金币及少量额外奖励
Linear search is O(n), binary search O(log n), bubble sort O(n²).
例题:输入翻倍会怎样
- 一个算法处理 1000 项要 4 秒。若它是 $O(n)$,估计处理 2000 项要多久;若它是 $O(n^2)$ 呢?
- $O(n)$:$n$ 翻倍时间翻倍,所以约 8 秒。
- $O(n^2)$:$n$ 翻倍时间变为四倍,所以约 16 秒。到 10,000 项时会是原来的 100 倍,约 400 秒。
- $O(\log n)$ 只会多一步,而 $O(1)$ 根本不变。从阶来推理,不要套公式。
An O(n squared) algorithm takes 4 seconds on 1,000 items. Roughly how many seconds will it take on 2,000?
难度 2/5 · 今日首次完成可获 140 金币及少量额外奖励
Doubling n quadruples an O(n squared) time. The same doubling would take an O(n) algorithm from 4 seconds to 8.
空间复杂度
- 空间复杂度(space complexity)是算法在输入本身之外所需的额外内存。
- 冒泡和插入排序用 $O(1)$ 的额外内存:它们原地工作,只需要几个变量。归并排序用 $O(n)$,因为它要建第二个数组。
- 递归占用的栈内存与它的深度成正比,因为每个未完成的调用都保留自己的栈帧。
- 常常存在时间与内存的取舍:像记忆化那样把结果存起来以免重算,就是用空间换速度。
还有什么决定选择
- 大O说的是增长,不是绝对速度。对小的 $n$,一个简单的 $O(n^2)$ 算法可能胜过一个复杂的 $O(n \log n)$ 算法,而且更容易写对。
- 当列表已按另一个字段排过序时,稳定性很要紧。简单性也要紧,因为简单的算法能藏 bug 的地方更少。
- "选哪个算法"的诚实答案往往同时说出阶和条件:选这个,因为 $n$ 很大而且数据到达时无序。
An "in place" sort:
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
In-place algorithms (like bubble and insertion sort) sort within the original array, using constant extra space.
Why is bubble sort's space complexity O(1) even though it sorts an array of n items?
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
It sorts in place. Merge sort is O(n) because it builds a second array, and recursion costs memory proportional to its depth.
算法内部的抽象数据类型
- 第 10 单元的抽象数据类型是算法赖以搭建的机械,而选择哪一种会塑造算法本身。
- 栈给出深度优先(depth-first)搜索:把邻居压入,取最新的一个,于是搜索沿一条路径一头扎下去,再回退。递归正是用调用栈做这件事。
- 队列给出广度优先(breadth-first)搜索:把邻居入队,取最旧的一个,于是搜索像涟漪一样一圈圈向外扩散,这正是在无权图中找到最短路径的方式。
- 二叉树(binary tree)让值保持有序,使每一步搜索都丢掉剩余节点的一半,在一个还能生长的结构上给出二分查找的 $O(\log n)$。
Which statements about Big-O are correct? Select 所有 that apply.
难度 2/5 · 今日首次完成可获 140 金币及少量额外奖励
Big-O says nothing about seconds; it is about growth. That is why the crossover with a simpler algorithm exists at small sizes.
例题:同一张图,两种搜索
- 从一个入口探索迷宫。对比使用栈和使用队列。
- 用栈,最近发现的路径最先被探索,所以搜索沿一条路走到底,遇到死路再回溯。它占用的内存与路径深度成正比。
- 用队列,最早发现的路径最先被探索,所以搜索先看完所有走一步能到的位置,再看走两步的。它最先找到最短路线,但内存里要装下当前距离上的每个位置。
- 说出抽象数据类型、说出由此产生的探索顺序,再说出后果。
A stack (LIFO) naturally drives a depth-first traversal, while a queue (FIFO) drives a breadth-first traversal.
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
The ADT you choose decides the search order — stack goes deep first, queue explores level by level.
Match each ADT to the search it produces and its consequence.
难度 2/5 · 今日首次完成可获 140 金币及少量额外奖励
Most recent first, or oldest first. That single choice decides whether the search goes deep or wide.
容易丢掉的分
- 大O描述的是随输入规模的增长,不是秒数。"它很快"不是复杂度的答案。
- 输入翻倍会让 $O(n)$ 的时间翻倍、让 $O(n^2)$ 的时间变四倍。要从阶来推理。
- 空间复杂度是额外内存,这就是原地排序即使数组有 $n$ 那么大也是 $O(1)$ 的原因。
- **栈给出深度优先,队列给出广度优先。**把这一对搞对方向,就是好几道题的全部。
你掌握了
- 用大O表示的时间复杂度描述随 $n$ 的增长:$O(1)$、$O(\log n)$、$O(n)$、$O(n \log n)$、$O(n^2)$;丢掉常数是因为在大规模下由阶说了算
- $n$ 翻倍会让 $O(n)$ 翻倍、让 $O(n^2)$ 变四倍;与"更差"算法的交叉点只存在于小的 $n$
- 空间复杂度是额外内存:原地排序是 $O(1)$,归并排序是 $O(n)$,递归的代价是栈深度
- 栈给出深度优先搜索,队列给出广度优先,二叉树每一步丢掉剩余节点的一半