#复杂度分析

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

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

#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!)

#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. 常见数据结构复杂度

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

#8. 常见算法复杂度

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

#9. 面试分析模板

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

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

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

#10. 常见误区

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

#面试总结

可以这样回答：

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