复杂度入门：O(1)、O(log n) 是怎么算出来的——时间复杂度与空间复杂度基础
背结论很容易，二分查找是 O(log n)、HashMap 的 get 是 O(1)、双层循环是 O(n²)，可一旦自己写一段循环，想判断它是 O 几，很多人就卡住了。这篇不做那些字面题，只讲一件事：拿到一段代码，怎么把它的时间复杂度和空间复杂度一步一步推出来。懂了怎么推，那些背过的结论才算你自己的。
一、复杂度在说“随规模怎么涨”，不是执行秒数
同一个程序，在这台机器上跑 1 毫秒，换个老机器可能跑 10 毫秒。所以直接用秒数衡量算法不靠谱，得找一个和机器无关的尺子。
这个尺子就是：输入规模 n 变大时，程序要做的事变多快。程序做的事，可以数成“基本操作执行了多少次”。
看个最简单的例子：
int sum = a + b;不管 a、b 是 1 还是一个亿，都只有一次加法，操作次数是固定的 1，跟输入无关。这种操作次数不随 n 变的，记作 O(1)，叫常数时间。O(1) 不代表快，它只代表“操作次数恒定，不随规模长”。
再想一层：如果代码里有几个这样的固定操作，比如 3 步、5 步，都还是 O(1)。因为复杂度只看“增长的级别”，不看具体几步——这一步以后会反复用到，叫去掉常数。
所以复杂度回答的问题永远是同一句：n 翻一倍，你要做的事大概翻几倍？ 懂了这句，下面每个例子都顺了。
二、线性：单层循环是 O(n)
最常见的循环长相：
for (int i = 0; i < n; i++) {
sum += arr[i]; // 每次循环做 1 次加法
}循环体执行了几次？从 i = 0 到 i = n - 1，一共 n 次。每次做 1 次操作，总共 n 次操作。n 翻一倍，操作次数也翻一倍，这种“跟着 n 一起涨”的记作 O(n)，叫线性时间。
数组里顺序找一个值就是典型的 O(n)：最坏情况要找的那个数在最后，得把 n 个元素从头到尾看一遍。n 越大，最多要看越多个，是正比关系。
三、平方：双层循环是 O(n²)
循环里套循环，次数就开始乘起来了：
for (int i = 0; i < n; i++) { // 外层 n 次
for (int j = 0; j < n; j++) { // 内层每次都跑 n 次
// 一次操作
}
}外层 i 每取一个值，内层就要完整跑一遍 n 次；外层一共 n 个值，所以总次数是 n × n = n²。记作 O(n²)，叫平方时间。n 翻一倍，操作次数翻成 4 倍（2n × 2n = 4n²）。
内层不总是从 0 到 n 呢？比如内层上限是 i：
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) { // 内层次数跟着外层变
// 一次操作
}
}数一下总次数：i = 0 时内层 0 次，i = 1 时 1 次，i = 2 时 2 次……一直加到 i = n - 1 时 n - 1 次。总和是：
0 + 1 + 2 + … + (n - 1) = n(n - 1) / 2
把它展开就是 (n² - n) / 2。n 很大的时候，n² 这一项比 n 项大得多，n 项可以忽略，只留下 n² / 2。而前面说过常数要丢掉，所以最终记作 O(n²)。
这里藏着复杂度计算的第一个要点：求和之后，只留增长最快的那一项，再把它的系数变成 1。n(n-1)/2 里的 -n 和 /2 都被这一条规则处理掉了。
四、对数：每次减半或翻倍是 O(log n)
前面三种都直观，唯独对数最反直觉，但它恰恰是“省时间”的关键，值得单独说。
看这段：
while (n > 1) {
n = n / 2; // 每次都砍掉一半
}n 从 8 开始，会走 8 → 4 → 2 → 1，走了 3 步；从 16 开始，走 16 → 8 → 4 → 2 → 1，走了 4 步。步数不是 n 条，而是“n 能除以几次 2 才到 1”，答案就是 log₂n。
算一下验证直觉。下面每行是“n 是 2 的几次方”：
| n | 分解 | 砍半到 1 的步数 |
|---|---|---|
| 8 | 8 = 2³ | 3 |
| 16 | 16 = 2⁴ | 4 |
| 1024 | 1024 = 2¹⁰ | 10 |
| 约 100 万 | 1048576 = 2²⁰ | 20 |
注意最后一行：n 从 8 涨到 100 万，涨了十几万倍，可步数只从 3 涨到 20，连十倍都不到。这就是对数“涨得极慢”的含义，也是二分查找能在大数组里飞快的原因——每看一次，剩下的范围就砍半。
循环还有一种“翻倍”长相，性质一样：
int k = 1;
while (k < n) {
k = k * 2; // 每次翻倍
}从 1 翻到 n 需要翻几次 2，同样约 log₂n 次，所以也是 O(log n)。
还有一点不用纠结：log 的底数写 2 还是写 10，最后都统一叫 O(log n)。因为换底只是乘一个常数，而常数在复杂度里会被丢掉。
五、常见复杂度排个队，找找感觉
把最常见的阶从慢到快排一遍（复杂度越小越好）：
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)
拿 n = 100 万（一百万）代入，感受差距有多大：
| 复杂度 | n = 1,000,000 时大概的操作次数 | 生活化类比 |
|---|---|---|
| O(1) | 1 | 瞥一眼就知道 |
| O(log n) | 约 20 | 每次二分，只要翻二十次 |
| O(n) | 1,000,000 | 挨个看一遍 |
| O(n log n) | 约 2000 万 | 快排、归并那种档位 |
| O(n²) | 10¹² | 每秒 10 亿次也要算上千秒 |
| O(2ⁿ) | 天文数字 | n = 30 已是约 10 亿次，基本跑不动 |
每个阶对应的典型代表，背这个就够用：
- O(1)：数组按下标取元素、HashMap 按 key 取值（平均）、栈和队列的进出（基于数组实现）。
- O(log n)：二分查找、平衡二叉树和堆的插入删除。
- O(n)：单层遍历、数组和链表的顺序查找。
- O(n log n)：快速排序、归并排序（平均）。
- O(n²)：冒泡、选择、插入这些基础排序，以及双层暴力循环。
- O(2ⁿ) 及以上：暴力枚举所有子集这类，n 稍大就跑不动。
六、空间复杂度：看额外占了多大地方
时间看“步数”，空间看“内存”。空间复杂度衡量的是：随着 n 变大，程序额外占用的内存涨多快。注意是“额外”——输入数据本身占的那份不算，只看你为了干活又开了多少。
判断方法和时间一模一样：数出额外空间跟 n 的关系，再去掉常数。
只用固定几个变量，不管 n 多大都不额外开数组的，是 O(1) 空间：
public int findMax(int[] arr) {
int max = arr[0]; // 就这一个变量
for (int i = 1; i < arr.length; i++) {
if (arr[i] > max) max = arr[i];
}
return max;
}这里无论 arr 多长，额外只占一个 max 变量，所以空间是 O(1)。
但如果复制了一份和输入一样长的数组，额外空间就是 O(n)：
public int[] copyArr(int[] arr) {
int[] copy = new int[arr.length]; // 和输入一样长
for (int i = 0; i < arr.length; i++) {
copy[i] = arr[i];
}
return copy;
}最容易漏的是递归占的栈空间。每次递归调用，都要在调用栈上留一层记录，递归多少层就占多大地方：
public int sum(int n) {
if (n == 0) return 0;
return n + sum(n - 1); // 一路递归到 0，深度是 n
}sum(n) 会先一直调下去，n → n-1 → … → 0，调用栈里叠了 n 层，所以空间是 O(n)。光看代码你会觉得“不就是个循环嘛”，但它递归版本的空间确实随 n 线性涨。
对比一下：前面那个砍半的 while 循环，全程只用几个变量、没有递归，所以时间是 O(log n)，空间却是 O(1)。递归版的二分查找就不一样了——每层递归砍半，栈深度约 log₂n，空间会变成 O(log n)。同一个算法，写成循环还是递归，空间复杂度常常不同，这也是面试爱问的点。
七、一张表收尾：常用操作背这张就够
不用记一堆，常用结构就这么几条，多数在前面单元都验证过：
| 结构 / 操作 | 时间复杂度 | 一句话原因 |
|---|---|---|
| 数组按下标读 | O(1) | 知道地址直接取 |
| 数组中间插删 | O(n) | 后面的元素要挪 |
| 链表头尾操作 | O(1) | 只改指针 |
| 链表按下标找 | O(n) | 得从头走 |
| HashMap get / put | O(1) 平均 | 哈希定位，冲突多会退化 |
| TreeMap 查 / 插 / 删 | O(log n) | 红黑树，树高是 log |
| 堆 offer / poll | O(log n) | 上浮下沉走树高 |
| 快速排序（平均） | O(n log n) | 分治 |
| 归并排序 | O(n log n) | 分治，还要 O(n) 空间 |
最后
一句话收束：时间复杂度和空间复杂度，本质都在回答“n 变大时，操作次数 / 额外内存涨多快”，算的时候只留增长最快的项、把系数丢掉。
下一步建议：拿一段你最近写过的、带循环或递归的代码，照着第二节到第六节的方法，数出它的时间复杂度和空间复杂度，标在注释里。能独立推出来一遍，比背十张表都管用。