时间/空间复杂度大 O

同一个算法，输入规模一大，是秒回还是等到天荒地老？大 O 一句话说清。

CSP-JCSP-S

◎学完你会

1动一动：输入规模 n 拖慢你多少

把滑杆从 8 拖到 256，看同一个输入规模下，不同复杂度要跑多少次运算（假设每秒 1 亿次）：

复杂度操作次数约耗时 (1e8/s)
O(1)10
O(log n)50
O(n)320
O(n log n)1600
O(n²)10240
O(2ⁿ)1.1e10109s
n=32 时，O(n²) 要 1024 次，O(2ⁿ) 已经是 10 亿级——肉眼可见指数爆炸。

2关键命令：常见阶

记号名字典型代码
O(1)常数数组取 a[i]、哈希查一次
O(log n)对数二分查找、倍增跳
O(n)线性一趟扫描 for(i=0;i<n;i++)
O(n log n)近线性排序 sort、归并
O(n²)平方两层循环各跑 n 次
O(2ⁿ)指数枚举所有子集、暴力搜索
估阶口诀：一层循环 n 次 → O(n)；嵌套两层各 n 次 → O(n²)； 每次把规模砍半（l+r 缩区间）→ O(log n)；排序类一般是 O(n log n)。

⚠易错点

以为 O(n) 比 O(2n) 快：大 O 只关心“当 n 很大时的增长趋势”，常数被忽略，O(2n)、O(n/2) 都是 O(n)。
只看最好情况：复杂度看的是最坏 / 平均的规模趋势，别拿“运气最好那次”当复杂度。
忘了算空间复杂度：数组开成 int a[n][n] 就是 O(n²) 空间，n 一大直接 MLE（超内存）。
嵌套循环想当然 n²：内层若固定只跑 k 次，外层 n 次是 O(nk)=O(n)，不是 O(n²)。

?跨学科：复杂度就是“增长规律”

O(n) 像一个个人排队：多一个人就多一份时间。O(log n) 像电话本二分查找：规模翻倍只多查一步。O(n²) 像聚会里两两握手：人一多，握手数几乎翻倍地涨。

“规模变大后到底涨多快”是复杂度、也是生物/经济里“规模效应”的共同语言——先估增长，再决定方案可不可行。

✎练一练

for(i=0;i<n;i++) for(j=0;j<n;j++) 时间复杂度是？
外层 n 次 × 内层 n 次 = n·n 次运算 → O(n²)。
下面哪几个是同阶的：O(n)、O(2n)、O(n/2)？
答案：都是同阶 O(n)。大 O 忽略常数倍数，只看增长趋势——线性增长就记 O(n)。