复杂度是什么（为什么不拿秒表）
写完一段代码想知道它快不快，第一反应当然是拿秒表掐一下。但这招不靠谱——同一段代码，在你的老电脑和别人的新机器上跑，时间能差一截；换个更大的输入，又是另一回事。
所以我们不看具体几秒，只看一件事：数据规模变大时，运行时间跟着怎么涨。这个趋势，就是时间复杂度，用大 O 来记。
常见量级，谁快谁慢
代码结构不一样，涨法天差地别。下面几个是平时最常打交道的，从快到慢排：
- O(1)：常数时间。数据再大，也是一步到位，比如按下标取数组元素。
- O(log n)：对数时间。每一步都能砍掉一半，二分查找就是它，快得很。
- O(n)：线性时间。数据翻倍、时间翻倍，比如把数组从头到尾遍历一遍。
- O(n log n)：比线性略慢一点，归并、快排这类高效排序都在这一档。
- O(n²)：平方时间。两层循环一套，冒泡排序就是，数据一多就肉眼可见地卡。
- O(2ⁿ)：指数时间。每多一个元素时间翻一倍，朴素递归算斐波那契就是反面教材，数据一大就跑不动了。
怎么一眼估出来（数循环层数）
带学生时我常给一个很土但很好使的办法：别急着推导，先数代码里循环套了几层。
一层，基本就是 O(n)；两层套在一起，基本是 O(n²)；三层 O(n³)，八九不离十。唯一要留神的是：循环里头要是又调了个 O(log n) 的东西（比如里面套了次二分），整体就变成 O(n log n) 了。
只留最高次项，常数全扔
大 O 只认增长趋势，不算精确步数。常数系数、低次项，它一概不看。
比如一段代码跑 3n² + 5n + 2 步，到它眼里就只剩 n²——前面的系数 3 不要，后面的 5n、2 也不要，最后写成 O(n²)。道理很简单：n 一大，那点低次项和常数根本翻不起浪。
复杂度量级对照表
| 大 O 符号 | 名称 | 生活类比 |
|---|---|---|
| O(1) | 常数时间 | 知道坐标，直接从书架抽出那本书 |
| O(log n) | 对数时间 | 查电话簿，每次翻一半 |
| O(n) | 线性时间 | 一页一页翻，找书里某句话 |
| O(n log n) | 线性对数时间 | 把一堆乱文件用高效排序法整理好 |
| O(n²) | 平方时间 | 全班同学两两握手，人一多就乱套 |
| O(2ⁿ) | 指数时间 | 一张纸对折再对折，厚度指数级爆炸 |