复杂度基础
衡量算法效率的基本工具：时间复杂度与空间复杂度。面试和刷题里说的「这个算法怎么样」，多数时候指的就是复杂度，而不是某台机器上跑了几毫秒。
1. 为什么要分析复杂度
同一问题往往有多种写法。数据量小时差别不明显；n 到万、百万级时，差一个量级就是「秒级 vs 超时」。
复杂度回答的是：
- 输入规模变大时，耗时大概怎么涨
- 额外要用多少内存
它不依赖具体语言、CPU 型号，方便比较算法本身。
// 找最大值：扫描一遍 —— 大致和 n 成正比
function findMax(arr) {
let max = arr[0]
for (const x of arr) {
if (x > max) max = x
}
return max
}
2. 大 O 表示法
大 O（Big-O）描述的是：当 n → ∞ 时，增长的上界趋势，忽略常数和低次项。
| 写法 | 含义 |
|---|---|
实际步骤大约 3n + 10 | 记作 O(n) |
实际步骤大约 n² + 100n | 记作 O(n²) |
实际步骤大约 5（与 n 无关） | 记作 O(1) |
读法：「这个算法是 O(n) 的」≈ 规模变大时，成本大致按线性涨。
常见规则：
- 只留最高阶：
n² + n→O(n²) - 去掉常数系数：
3n→O(n) - 相加取更慢的那个：先 O(n) 再 O(n²) → 整体 O(n²)
- 嵌套相乘：外层 n、内层 n → O(n²)
// 两层循环：O(n²)
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
// ...
}
}
// 先扫一遍再扫一遍：O(n) + O(n) = O(n)
for (let i = 0; i < n; i++) { /* ... */ }
for (let j = 0; j < n; j++) { /* ... */ }
3. 常见时间复杂度量级
从快到慢（同一 n 下，越往下越慢）：
| 复杂度 | 典型场景 | n=10⁶ 量级直觉 |
|---|---|---|
| O(1) | 下标访问、哈希表均摊查找 | 常数次操作 |
| O(log n) | 二分查找、平衡树高度 | 约几十次 |
| O(n) | 遍历数组、一次线性扫描 | 约百万次 |
| O(n log n) | 高效排序（快排/归并均摊或最坏） | 约两千万量级 |
| O(n²) | 双重循环、简单排序 | 约万亿——通常会超时 |
| O(n³) | 三重循环、部分图算法朴素写法 | 更大 |
| O(2ⁿ) / O(n!) | 子集枚举、全排列暴搜 | 指数爆炸，只适合很小的 n |
// O(1)
arr[0]
// O(log n) —— 二分
function binarySearch(arr, target) {
let l = 0, r = arr.length - 1
while (l <= r) {
const mid = (l + r) >> 1
if (arr[mid] === target) return mid
if (arr[mid] < target) l = mid + 1
else r = mid - 1
}
return -1
}
// O(n)
arr.includes(x) // 最坏要看完
// O(n log n) —— 内置排序多数实现这一档
arr.slice().sort((a, b) => a - b)
// O(n²)
for (let i = 0; i < n; i++)
for (let j = 0; j < n; j++) { /* ... */ }
记忆口诀：对数 → 线性 → 线性对数 → 平方 → 指数（由快到慢）。刷题时先估复杂度，再决定要不要优化。
4. 最好 / 平均 / 最坏情况
同一算法，不同输入，步数可以差很多。
| 情形 | 含义 | 例子（查找） |
|---|---|---|
| 最好 | 运气最好时 | 目标在第一个位置 → O(1) |
| 最坏 | 运气最差时 | 目标不存在或在最后 → O(n) |
| 平均 | 各种输入的期望 | 均匀分布下约 O(n) |
面试和题目分析里，默认看最坏情况（除非题目明确问平均）。
例如快速排序：平均 O(n log n)，最坏 O(n²)（已基本有序且枢轴选得差时）。
哈希表查找也类似：平均 O(1)，最坏可能退化到 O(n)（严重冲突）。
5. 空间复杂度与原地算法
空间复杂度：算法运行时 额外 占用的内存随 n 怎么涨（一般不含输入本身占用的空间）。
| 写法 | 空间 | 说明 |
|---|---|---|
| 只用几个变量 | O(1) | 常称原地（in-place） |
| 开一个长度 n 的数组 | O(n) | |
| 递归深度为 n | O(n) | 调用栈也算空间 |
// 额外空间 O(1)：原地反转
function reverseInPlace(arr) {
let l = 0, r = arr.length - 1
while (l < r) {
;[arr[l], arr[r]] = [arr[r], arr[l]]
l++
r--
}
}
// 额外空间 O(n)：新开结果数组
function reverseCopy(arr) {
return [...arr].reverse()
}
递归别忘了算栈：
// 递归 n 层 → 空间 O(n)
function sum(n) {
if (n <= 0) return 0
return n + sum(n - 1)
}
时间与空间常可互换：用哈希表换时间（空间换时间），或滚动数组压 DP 空间（时间略换空间）。
6. 复杂度分析常见误区
-
把常数当成无关紧要到可以忽略实现
大 O 相同，常数差 100 倍，工程上仍可能慢。大 O 用于趋势与选型，不是唯一指标。 -
O(n²) 一定比 O(n log n) 慢吗？
n 很小时，常数小的平方算法可能更快；n 变大后趋势才稳。 -
循环层数 = 复杂度？
不一定。内层若只跑 log n 次，整体可能是 O(n log n)；两段独立的单层循环仍是 O(n)。 -
只数了循环，忘了库函数
sort、部分includes/ 拷贝都会贡献复杂度，要算进去。 -
平均当最坏用
题目卡的是最坏输入时，只报平均会翻车（快排、哈希都要心里有数）。 -
递归没算空间
时间看着漂亮，栈溢出或空间超限也是挂。
下一篇：排序 —— 在复杂度框架下对比各类排序。