大 O 记号
复习
- 输入规模与增长速度：衡量算法看的是运行时间随规模的增长趋势
- 常数因子：常数因子和机器差异会干扰直接比较
- 增长趋势：增长更慢的算法，在大规模下终将胜出
TL;DR
- 大 O 记号描述增长速度的数量级，忽略常数和低阶项
- 它给出的是上界，回答“最多长多快”
- 常数、低阶项在规模足够大时可以忽略
- 大 O 是交流算法效率的共同语言
正文
我们已经确定：要比较算法，就看增长速度，并且忽略常数。现在，需要一个简洁的记号把这套想法固定下来。这就是大 O 记号（Big-O notation）。
一个直观的理解
大 O 做的事情，可以概括成一句话：只保留增长最快的部分，其余统统丢掉。
比如一个算法要花 3n² + 5n + 7 次操作。随着 n 变大：
3n²是主导项，增长最快5n和常数7相比之下微不足道
于是我们把它记作 O(n²)，读作“n 的平方级”。
定义上，f(n) = O(g(n)) 的意思是：存在某个常数 c 和某个规模 n₀，当 n 超过 n₀ 以后，f(n) 始终不超过 c · g(n)。换句话说，从足够大的规模开始，f 的增长不会超过 g 的某个常数倍。 它抓住的是“趋势的上限”，而不是精确的数值。
为什么要丢掉常数
你可能会舍不得那个 3：明明是 3n²，为什么写成 O(n²)？
因为常数取决于太多无关的东西：机器快慢、编程语言、代码细节。把它们留着，反而让“算法本身的趋势”变得模糊。大 O 想比较的，是在不同硬件上都成立的那部分。3n² 和 100n² 都被记为 O(n²)，因为它们属于同一个增长量级。
几个要点
使用大 O 时，有几件事要留心：
- 它是上界：
O(g)表示“不会比 g 增长得更快”，未必是精确的紧贴 - 只留最高阶：
O(n² + n)就是O(n²) - 不写常数和系数：通常写
O(n)，而不写O(2n)或O(n/2) - 它描述趋势：
O(1)不是“1 秒”，也不代表“一定很快”，只是说耗时与规模无关
有了这个共同的尺子，我们就能把常见算法按增长速度归类。下一章，看看这些“量级”都长什么样。
思考题 1
为什么
3n² + 5n + 7可以记为O(n²)？
思考题 2
O(1)是不是意味着“运行时间是 1 秒”或者“一定很快”？为什么？
小结
知识点
- 大 O 描述增长速度的数量级
- 只保留最高阶项，忽略常数与低阶项
- 它是上界，不是精确的运行时间
- 大 O 便于跨机器比较算法趋势
参考资料
- Wikipedia(zh)：大O符号：描述函数增长量级的记号
- Wikipedia(zh)：时间复杂度：用增长量级衡量算法耗时
思考题答案（仅供参考）
思考题 1
因为当 n 很大时，3n² 这一项会远远超过 5n 和 7，成为决定增长趋势的主导。常数系数 3 也只是个常数倍，不影响增长量级。所以整式的量级就是 n²。
思考题 2
不是。O(1) 只表示“耗时与输入规模无关”，是个固定的量。这个固定量可能是 1 纳秒，也可能是 1 秒钟甚至更久——它只是不随 n 增长而已。所以 O(1) 不等于“快”，只等于“不受规模影响”。
协议
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
封面图
设计师 | 南国微雪