1. 定位导航
前面已经讲过：
O描述上界；Ω描述下界；Θ描述紧确界；- 复杂度关注的是增长趋势，不是精确秒数。
但如果只会写O(...)，还不够。
还要知道不同函数之间的增长差距：
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)这条顺序，就是判断算法可扩展性的基础。
2. 概念术语
| 术语 | 定义 | 常见场景 |
|---|---|---|
| 常数复杂度 | 不随输入规模增长 | 哈希表平均查找 |
| 对数复杂度 | 每次把问题规模缩小一大截 | 二分查找 |
| 线性复杂度 | 输入多大，大致扫多少 | 遍历数组 |
| 线性对数复杂度 | 常见于分治和排序 | 归并排序、堆排序 |
| 平方复杂度 | 两层循环，两两比较 | 简单枚举配对 |
| 指数复杂度 | 每个元素都有多种选择 | 暴力子集枚举 |
| 阶乘复杂度 | 排列所有可能顺序 | 暴力旅行商问题 |
关键澄清：
O(1)不代表只执行一条语句，而是执行成本不随n增长。O(log n)通常意味着每一步都能大幅缩小问题规模。O(n log n)是很多高效排序算法的典型复杂度。O(2ⁿ)和O(n!)通常只能处理很小规模输入。
3. 常见增长速度总览
下面先看一张从慢到快的总览图：
从左到右，增长速度越来越快：
O(1) → O(log n) → O(n) → O(n log n) → O(n²) → O(2ⁿ)要注意，这里的“快”不是说算法执行快，而是说成本增长快。
越靠右，输入规模变大以后越危险。
4. 从慢到快逐个理解
4.1 O(1)：常数复杂度
O(1)表示运行成本不随输入规模增长。
例如：
x=arr[0]不管数组长度是 10，还是 100 万，访问第一个元素的成本都差不多。
注意：O(1)不是说只执行一步，而是说成本可以看成固定常数。
4.2 O(log n)：对数复杂度
O(log n)通常出现在“每次砍掉一半”的场景中。
典型例子是二分查找。
如果有 1024 个元素：
1024 → 512 → 256 → 128 → ... → 1大约只需要 10 次就能缩小到 1。
这就是对数增长很慢的原因。
4.3 O(n)：线性复杂度
O(n)表示输入规模翻倍，成本大致也翻倍。
例如遍历数组：
forxinarr:print(x)数组有多少个元素，大致就要处理多少次。
4.4 O(n log n)：线性对数复杂度
O(n log n)很常见，尤其在排序算法中。
例如：
- 归并排序
- 堆排序
- 平均情况下的快速排序
它通常来自这样的结构：
每层处理 n 个元素，一共有 log n 层所以总成本是：
nlogn n \log nnlogn
4.5 O(n²)：平方复杂度
O(n²)常见于两层循环。
例如：
foriinrange(n):forjinrange(n):...如果n从 1000 增加到 2000，成本不是增加 2 倍，而是接近 4 倍。
4.6 O(2ⁿ)：指数复杂度
O(2ⁿ)常见于暴力枚举所有子集。
例如每个元素都有选或不选两种状态，n个元素就有：
2n 2^n2n
种可能。
当n = 30时，已经超过 10 亿级别。
这类算法通常必须配合剪枝、动态规划、贪心、近似算法等方法优化。
5. 为什么 n log n 很常见
n log n是一个非常重要的增长速度。
它经常来自分治结构：
先把问题不断拆小 每一层做一次线性处理 一共有 log n 层以排序为例：
- 一层中，总共处理
n个元素； - 问题规模每次折半，所以层数是
log n； - 总成本就是
n log n。
很多高效比较排序都很难突破这个级别，这也是为什么O(n log n)经常被看作通用排序里的重要标杆。
6. 动态推演：输入规模变大后的差距
下面用动态图看一下，当n从 10 增加到 10000 时，各类增长速度如何拉开差距。
这个图要表达的是：
- 小规模时，很多复杂度差距不明显；
- 中等规模时，
n²开始明显变重； - 大规模时，增长速度会成为系统上限；
- 复杂度越高，越不能只靠硬件硬撑。
7. 数值对比
看一个简单表格：
| n | log₂n | n | n log₂n | n² | 2ⁿ |
|---|---|---|---|---|---|
| 10 | 3.32 | 10 | 33.2 | 100 | 1024 |
| 100 | 6.64 | 100 | 664 | 10000 | 约 1.27e30 |
| 1000 | 9.97 | 1000 | 9966 | 1000000 | 巨大 |
| 10000 | 13.29 | 10000 | 132877 | 100000000 | 极其巨大 |
从表里可以看出：
log n增长非常慢；n log n比n稍高，但仍然比较可控；n²在大规模输入下迅速变重；2ⁿ很快就变得无法直接枚举。
8. 代码实践
下面用 Python 打印不同增长函数的数值：
importmathdefsafe_power_2(n):ifn>60:return"太大"return2**n headers=["n","log2(n)","n","nlog2(n)","n^2","2^n"]print("{:<8}{:<12}{:<12}{:<15}{:<15}{:<15}".format(*headers))fornin[10,100,1000,10000]:row=[n,round(math.log2(n),2),n,round(n*math.log2(n),2),n*n,safe_power_2(n),]print("{:<8}{:<12}{:<12}{:<15}{:<15}{:<15}".format(*row))也可以用一段代码感受二分查找为什么是O(log n)：
defbinary_steps(n):steps=0whilen>1:n//=2steps+=1returnstepsfornin[10,100,1000,1000000]:print(n,binary_steps(n))可能输出：
10 3 100 6 1000 9 1000000 19可以看到，数据规模从 1000 增加到 1000000，二分过程也只从 9 次左右增加到 19 次左右。
这就是对数复杂度的威力。
9. 常见误区
误区一：O(1) 就一定最快
不一定。O(1)只说明不随n增长，但常数可能很大。
比如一次远程网络调用也可以看成固定成本，但它可能比本地循环慢很多。
误区二：O(n²) 一定不能用
不一定。小规模数据下，O(n²)完全可以接受，甚至实现简单、常数小。
真正的问题是：输入规模会不会变大。
误区三：O(log n) 总是来自二分查找
不只如此。树结构查找、堆操作、很多分治过程都可能出现log n。
误区四：指数复杂度完全没价值
不是。指数算法在小规模、精确搜索、组合优化中仍然有价值，只是必须控制输入规模，或者配合剪枝和优化。
10. 现代延伸
在工程系统中，增长速度直接影响系统上限。
| 场景 | 常见增长速度 | 说明 |
|---|---|---|
| 哈希表平均查找 | O(1) | 常用于缓存和索引 |
| 二分查找 | O(log n) | 有序数组中快速定位 |
| 全量扫描 | O(n) | 数据变大后延迟线性增长 |
| 排序 | O(n log n) | 大多数通用排序可接受 |
| 两两比较 | O(n²) | 大规模下容易成为瓶颈 |
| 暴力组合搜索 | O(2ⁿ) | 通常需要剪枝或动态规划 |
比如推荐系统召回阶段，候选集可能非常大，如果对所有物品逐一精排，成本会难以承受。因此通常会先用向量索引、倒排索引、规则召回等方法缩小候选集，再进行排序。
这背后的核心思想就是：避免让高增长复杂度直接作用在最大规模数据上。
11. 思考题
- 为什么
O(log n)的增长速度比O(n)慢很多？ - 为什么很多高效排序算法都是
O(n log n)？ - 如果一个功能需要两两比较所有用户，复杂度大概是多少？
- 在什么情况下
O(n²)算法仍然可以接受？ - 你见过哪些场景必须避免
O(2ⁿ)暴力枚举？
12. 本篇小结
本篇主要建立了常见增长速度的直觉：
O(1)基本不受输入规模影响；O(log n)增长非常慢，常见于折半过程；O(n)表示线性扫描；O(n log n)是很多高效排序和分治算法的典型复杂度；O(n²)在大规模输入下会快速变重；O(2ⁿ)、O(n!)通常只能处理很小规模问题。
判断一个算法能不能用，不只是看它能不能跑，而是要看：
当 n 变大时，它还能不能跑得动？
