复杂度分析

面试中如何判断算法的时间复杂度和空间复杂度？

复杂度分析用于描述：当输入规模增长时，算法的运行时间和额外空间如何增长。它关注增长趋势，而不是某台机器上的具体毫秒数。

1. 输入规模和大 O

先明确输入规模 n 是什么：

数组题通常是数组长度；
字符串题通常是字符串长度；
矩阵题可能是行数 m 和列数 n；
图题通常需要同时写顶点数 V 和边数 E。

大 O 记号表示渐进上界，通常忽略常数和低阶项：

3n² + 5n + 10  -> O(n²)
100n + 20       -> O(n)

这里的“忽略常数”不是说常数在真实性能中没有意义，而是复杂度用于比较规模增长趋势。

2. 常见复杂度

复杂度	直观理解	常见例子
`O(1)`	操作次数与输入规模无关	数组按下标访问、哈希表平均查找
`O(log n)`	每次把问题规模缩小一部分	二分查找、平衡树查找
`O(n)`	遍历一次输入	数组扫描、链表遍历
`O(n log n)`	分治并在每层线性处理	归并排序、平均快排
`O(n²)`	两层相互关联的遍历	简单排序、枚举所有数对
`O(2^n)`	每一步产生多个分支	未记忆化的子集/递归枚举
`O(n!)`	枚举所有排列	全排列暴力搜索

增长速度通常满足：

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2^n) < O(n!)

3. 时间复杂度怎么分析？

顺序代码取最大项

for (const item of items) {           // O(n)
  visit(item);
}

for (const item of items) {           // O(n)
  check(item);
}

总复杂度是 O(n + n)，去掉常数后仍是 O(n)。

如果两个循环规模不同，应保留不同变量：O(m + n)。

嵌套循环通常相乘

for (let i = 0; i < n; i++) {
  for (let j = 0; j < n; j++) {
    compare(i, j);
  }
}

外层执行 n 次，内层每次执行 n 次，总复杂度为 O(n²)。

如果内层规模不依赖外层，也可以是 O(mn)：

for (let i = 0; i < m; i++) {
  for (let j = 0; j < n; j++) {
    compare(i, j);
  }
}

循环变量每次减半是 `O(log n)`

let value = n;
while (value > 1) {
  value = Math.floor(value / 2);
}

每次循环都把规模减半，因此循环次数约为 log₂n。

循环变量每次加倍也是 `O(log n)`

for (let value = 1; value < n; value *= 2) {
  visit(value);
}

变量序列为 1, 2, 4, 8...，达到 n 需要 O(log n) 次。

三角循环不一定是 `O(n²)` 的精确表达

for (let i = 0; i < n; i++) {
  for (let j = i + 1; j < n; j++) {
    compare(i, j);
  }
}

执行次数约为 n(n - 1) / 2，去掉常数和低阶项后是 O(n²)。

提前返回影响最好和最坏情况

function find(items, target) {
  for (let i = 0; i < items.length; i++) {
    if (items[i] === target) return i;
  }
  return -1;
}

最好情况：第一个元素就是目标，O(1)；
最坏情况：目标在末尾或不存在，O(n)；
平均情况：取决于输入分布，通常也记为 O(n)。

面试中应明确说明自己分析的是最好、平均还是最坏情况，默认通常讨论最坏复杂度。

4. 递归复杂度怎么分析？

每次只递归一个分支

function binarySearch(left, right) {
  if (left > right) return -1;
  const mid = Math.floor((left + right) / 2);
  // 只继续搜索一半区间
  return binarySearch(nextLeft, nextRight);
}

问题规模每次减半，时间复杂度是 O(log n)。

每层遍历全部数据

归并排序可以理解为：树高 log n，每层合并总共处理 n 个元素，因此是 O(n log n)。

每次产生两个分支

function search(index) {
  if (index === n) return;
  search(index + 1);
  search(index + 1);
}

递归树的节点数量呈指数增长，通常为 O(2^n)。如果增加记忆化，把重复子问题结果保存下来，复杂度可能降为多项式或 O(n)，需要重新分析状态数量和每个状态的转移成本。

5. 空间复杂度怎么分析？

空间复杂度通常指额外空间，不包含题目已经提供的输入数据；如果题目要求返回结果，是否把结果空间计入要说明口径。

常数额外空间：`O(1)`

function sum(items) {
  let total = 0;
  for (const item of items) total += item;
  return total;
}

这里只有几个变量，不随 n 增长。

线性额外空间：`O(n)`

const seen = new Set();
for (const item of items) {
  seen.add(item);
}

集合最多保存 n 个元素，因此额外空间是 O(n)。

递归栈也要计入空间

function walk(node) {
  if (!node) return;
  walk(node.left);
  walk(node.right);
}

如果树退化成链，递归深度为 n，空间复杂度最坏为 O(n)；如果树平衡，递归栈约为 O(log n)。

因此“递归算法没有额外数组，所以空间是 O(1)”通常是错误的。

原地算法的空间说明

原地算法通常表示只使用 O(1) 或较少的额外工作空间，但不一定意味着输入完全不能修改。分析时要区分：

辅助空间：算法额外申请的空间；
输出空间：返回结果本身需要的空间；
递归栈：递归调用占用的空间。

6. 摊销复杂度

某一次操作可能很慢，但一长串操作的平均成本很低，这时使用摊销复杂度。

例如动态数组扩容：

大多数 push 是 O(1)；
容量不足时需要复制已有元素，单次可能是 O(n)；
扩容后容量通常按倍数增长，连续执行 n 次 push 的总成本是 O(n)；
因此单次 push 的摊销复杂度是 O(1)。

摊销复杂度不是把最坏情况忽略，而是分析一系列操作的总成本。

7. 常见数据结构复杂度

以下是常见实现的典型复杂度，哈希表的查找、插入和删除是平均情况：

数据结构	访问	查找	插入	删除	备注
数组	`O(1)`	`O(n)`	尾部摊销 `O(1)`	头部 `O(n)`	中间插入会移动元素
链表	`O(n)`	`O(n)`	已知节点 `O(1)`	已知节点 `O(1)`	找到节点本身仍可能是 `O(n)`
哈希表	-	平均 `O(1)`	平均 `O(1)`	平均 `O(1)`	最坏可能退化
平衡搜索树	`O(log n)`	`O(log n)`	`O(log n)`	`O(log n)`	依赖平衡维护
堆	查看堆顶 `O(1)`	`O(n)`	`O(log n)`	删除堆顶 `O(log n)`	适合优先队列

8. 常见算法复杂度

算法	时间复杂度	额外空间	说明
线性查找	最坏 `O(n)`	`O(1)`	无序数据也可用
二分查找	`O(log n)`	迭代 `O(1)`	前提是数据有序
冒泡 / 选择 / 插入排序	通常 `O(n²)`	通常 `O(1)`	插入排序最好情况可为 `O(n)`
归并排序	`O(n log n)`	`O(n)`	稳定，需辅助数组
快速排序	平均 `O(n log n)`，最坏 `O(n²)`	平均递归栈 `O(log n)`	取决于分区和 pivot
BFS / DFS	`O(V + E)`	`O(V)`	图用邻接表表示时

排序算法的稳定性和实现细节见排序算法。

9. 面试分析模板

拿到一道算法题，可以按下面顺序回答：

定义输入规模：n 是数组长度，还是 m × n 的矩阵？
说明核心循环或递归每次处理多少数据。
判断顺序、嵌套、分支或分治关系。
合并复杂度：顺序取和，嵌套取积，递归分析递归树或状态数。
去掉常数和低阶项，得到大 O。
单独分析辅助容器、输出和递归栈。
说明最好、平均、最坏情况，以及是否使用摊销分析。

示例：滑动窗口通常用两个指针让每个元素最多进出窗口一次，因此时间复杂度为 O(n)；如果使用哈希表记录窗口状态，额外空间通常为 O(k)，其中 k 是窗口内不同元素数量，最坏可写成 O(n)。

10. 常见误区

两个嵌套循环只有在内层都执行 O(n) 次时才是 O(n²)；要看真实循环范围。
递归深度不是时间复杂度，递归栈属于空间复杂度。
哈希表的 O(1) 通常是平均复杂度，不是所有情况下的严格保证。
二分查找的前提是数据有序，排序成本也要计入完整算法流程。
O(n log n) 不一定比 O(n²) 在小数据上快，复杂度描述的是增长趋势。
返回一个长度为 n 的结果时，输出空间是否计入要明确说明。

面试总结

可以这样回答：

时间复杂度描述算法运行时间随输入规模增长的趋势，空间复杂度描述额外内存的增长趋势。分析时先确定输入规模，再看循环、嵌套、递归和数据结构操作，最后忽略常数与低阶项。空间分析不能遗漏哈希表、辅助数组和递归栈，还要区分最好、平均、最坏和摊销复杂度。

#复杂度分析

#1. 输入规模和大 O

#2. 常见复杂度

#3. 时间复杂度怎么分析？

#顺序代码取最大项

#嵌套循环通常相乘

#循环变量每次减半是 O(log n)

#循环变量每次加倍也是 O(log n)

#三角循环不一定是 O(n²) 的精确表达

#提前返回影响最好和最坏情况

#4. 递归复杂度怎么分析？

#每次只递归一个分支

#每层遍历全部数据

#每次产生两个分支

#5. 空间复杂度怎么分析？

#常数额外空间：O(1)

#线性额外空间：O(n)

#递归栈也要计入空间

#原地算法的空间说明

#6. 摊销复杂度

#7. 常见数据结构复杂度

#8. 常见算法复杂度

#9. 面试分析模板

#10. 常见误区

#面试总结