Olverae Assets

1 先拖一下：n 一大，差距有多吓人

别急着背定义。拖动滑块改变输入规模 n，盯着右表 O(n²) 和 O(2ⁿ) 那两行——看它们怎么把其它人甩到看不见。拖完，下面再用一句话收住"大 O 到底在量什么"。

复杂度增长对比

输入规模 n = 8

纵轴在 64 步处截顶——冲出顶部的曲线，表示它的步数已经远超出可视范围（看右表真实数字）。

n = 8 时，各复杂度要做的操作数

你刚拖出来的差距，就是时间复杂度（大 O 记号）在量的东西：n 变大时，步数增长得有多快——不看具体几毫秒，只看增长趋势，而且只留最猛的那一项、丢掉常数。

打个比方：A 家快递"每多一件 +1 元"（线性 O(n)）、B 家"件数翻倍才 +1 元"（对数 O(log n)）、C 家"每多一件按已有件数翻番"（指数 O(2ⁿ)）。寄 5 件时仨差不多，寄 1000 件就天差地别——大 O 描述的正是这种"规模一大就拉开"的涨法。

2 关键一步：大 O 量的是"涨势"，不是"某一点的快慢"

这是最容易把大 O 用错的地方——回到上面的滑块，亲手验证这三件事。

把 n 拖到很小（1–3）

曲线挤成一团，O(n²) 甚至可能压在 O(n) 下面。小数据上谁快，由常数和实现说了算，大 O 根本看不出来。

所以一个 O(n²) 的简单算法，在小数组上常常比 O(n log n) 的复杂算法还快——很多库的排序在数组很小时故意退化成插入排序，就是这个道理。

再把 n 拖大

趋势碾压一切：n 一大，O(n²) / O(2ⁿ) 把常数、低阶项、硬件快慢全部踩在脚下。

这正是大 O 丢掉常数和低阶项的原因——n→∞ 时它们都无关大局。大 O 比的是"规模翻倍，代价怎么涨"，不是"此刻跑几毫秒"。

还得记住：它是"上界 / 最坏"

大 O 通常描述最坏情况的增长上界；同一个算法的最好 / 平均 / 最坏可能不同。

如快排平均 O(n log n)、最坏 O(n²)；哈希表查找平均 O(1)、最坏 O(n)。一句话：选算法看大 O（伸缩性），调性能看实测（常数）。

3 怎么从代码一眼读出大 O

大 O 不用背，会三条规则就能现场推：丢常数、只留最猛的那项、循环看嵌套。下面还有一张全大纲速记表。

① 丢常数、留最高阶

一句话：大 O 只看 n 很大时谁说了算。所以 3n²+5n+2 里只留 n²，系数 3、低阶 5n、常数 2 全丢掉 → O(n²)。

因为 n→∞ 时 n² 把其它项远远甩开，常数倍数也无关增长趋势。O(2n) 和 O(n) 是一回事；O(n²+n) 就是 O(n²)。

② 循环：顺序相加，嵌套相乘

一句话：两段独立的循环是相加（still O(n)），一个套一个才是相乘（O(n²)）。

看清循环跑几圈、是否嵌套、内层圈数是否依赖外层。每次把问题"减半"的循环是 O(log n)（如二分、不断 /2）。

for i in n: ... // O(n) for i in n: ... // 顺序 → 仍 O(n) for i in n: for j in n: ... // 嵌套 → O(n²)

③ 递归：解递归式

一句话：递归的复杂度看"它把自己叫了几次、问题缩小多少"。一次减半且只递归一支 → O(log n)；每层裂成两支 → 可能 O(2ⁿ)。

阶乘 T(n)=T(n-1)+O(1) → O(n)；朴素斐波那契 T(n)=T(n-1)+T(n-2) → O(2ⁿ)（指数，慢到没法用）；归并 T(n)=2T(n/2)+O(n) → O(n log n)。

常见操作	复杂度	规模一大时
数组按下标取值 a[i]、哈希表查找	O(1)	不随 n 变，最快
二分查找、平衡树查找、不断减半	O(log n)	极慢增长，n 翻倍才 +1 步
遍历一遍、线性查找、求和	O(n)	线性，最常见
归并/快排/堆排、好的排序	O(n log n)	大数据排序的实际上限
双重嵌套循环、冒泡/选择/插入排序	O(n²)	n 上千就开始吃力
枚举所有子集、朴素斐波那契	O(2ⁿ)	指数爆炸，n≈30 就跑不动
枚举所有排列（旅行商暴力）	O(n!)	比指数还猛，n≈12 即天文数字

4 四个最常见的误判（点一下看对错）

大 O 的坑大多是"推导误解"——保留了不该留的、把顺序当成嵌套、看不出对数、误判递归。点击卡片看" 错误推导 → 正确"。

① 保留了常数/低阶项

写成 O(3n²+5n) → 应化简为 O(n²)

② 顺序当成了嵌套

两段独立循环是 O(n)，不是 O(n²)

③ 没看出对数

每次减半的循环是 O(log n)，不是 O(n)

④ 误判递归复杂度

朴素斐波那契是 O(2ⁿ)，不是 O(n)

// 点击上方任一卡片，查看错误推导与正确结论

$ 分析中... （等待运行...）

5 自测

这 5 题正对 2521 套路：化简、嵌套循环、对数、操作计数、增长对比。最后到练习系统亲手数操作次数。

去做例题：复杂度 · 数三角双循环的次数

去做例题

大 O 与时间复杂度分析