复杂度分析

场景引入

面试官："你这个方案的时间复杂度是多少？能优化吗？"

这是算法面试中出现频率最高的问题之一。每写完一段代码，面试官几乎一定会追问复杂度。如果你答不上来，即使代码正确，也会被扣分。

复杂度分析是算法学习的第一课，也是贯穿始终的基本功。

什么是大 O 表示法

大 O 表示法描述的是：当输入规模 n 趋向无穷大时，算法执行时间的增长趋势。

注意几个关键点：

关注的是增长趋势，不是精确的执行次数
忽略常数系数：O(2n) 和 O(3n) 都记为 O(n)
只保留最高阶项：O(n² + n) 记为 O(n²)

举个例子：

javascript

function sum(arr) {
  let total = 0;          // 执行 1 次
  for (let i = 0; i < arr.length; i++) {
    total += arr[i];       // 执行 n 次
  }
  return total;            // 执行 1 次
}

总执行次数：1 + n + 1 = n + 2。忽略常数，时间复杂度为 O(n)。

常见复杂度级别

从快到慢排列：

复杂度	名称	n=10	n=100	n=1000	典型场景
O(1)	常数	1	1	1	哈希表查找、数组下标访问
O(log n)	对数	3	7	10	二分查找、平衡 BST 操作
O(n)	线性	10	100	1000	遍历数组、链表
O(n log n)	线性对数	33	664	9966	归并排序、快速排序
O(n²)	平方	100	10000	10⁶	冒泡排序、两层嵌套循环
O(2^n)	指数	1024	10³⁰	--	暴力枚举子集
O(n!)	阶乘	3.6M	--	--	暴力枚举全排列

直觉：面试中大部分题目的最优解复杂度在 O(n) 到 O(n log n) 之间。如果你的方案是 O(n²)，面试官大概率会让你优化。

如何分析时间复杂度

规则一：顺序执行 —— 取最大

javascript

function example(arr) {
  // 阶段一：O(n)
  for (let i = 0; i < arr.length; i++) { /* ... */ }

  // 阶段二：O(n²)
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length; j++) { /* ... */ }
  }
}

两个阶段顺序执行，总复杂度 = O(n) + O(n²) = O(n²)（取最高阶）。

规则二：嵌套循环 —— 相乘

javascript

for (let i = 0; i < n; i++) {         // 外层 n 次
  for (let j = 0; j < n; j++) {       // 内层 n 次
    // 常数操作
  }
}

总复杂度 = n x n = O(n²)。

如果内层循环次数和外层无关：

javascript

for (let i = 0; i < n; i++) {         // n 次
  for (let j = 0; j < m; j++) {       // m 次
    // 常数操作
  }
}

总复杂度 = O(n * m)。

规则三：对数级 —— 每次缩半

javascript

let i = n;
while (i > 1) {
  i = Math.floor(i / 2);   // 每次减半
}

循环次数 = log₂(n)，复杂度为 O(log n)。

二分查找就是典型的 O(log n)：每次排除一半的搜索空间。

规则四：递归 —— 画递归树

递归复杂度分析的核心方法是画递归树，计算总节点数。

示例一：线性递归

javascript

function factorial(n) {
  if (n <= 1) return 1;
  return n * factorial(n - 1);
}

递归深度为 n，每层做 O(1) 工作，总复杂度 = O(n)。

示例二：二叉递归

javascript

function fib(n) {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
}

每次调用产生 2 个子调用，递归树深度为 n，总节点数约 2^n，复杂度 = O(2^n)。

这就是为什么朴素递归求斐波那契数列会超时——需要用动态规划优化到 O(n)。

示例三：归并排序递归

javascript

function mergeSort(arr) {
  if (arr.length <= 1) return arr;
  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));    // T(n/2)
  const right = mergeSort(arr.slice(mid));       // T(n/2)
  return merge(left, right);                     // O(n)
}

递归关系：T(n) = 2T(n/2) + O(n)。递归树每层总工作量为 O(n)，共 log n 层，总复杂度 = O(n log n)。

最好、最坏、平均情况

同一个算法在不同输入下复杂度可能不同：

情况	快速排序	二分查找
最好	O(n log n) — 每次均匀划分	O(1) — 第一次就找到
平均	O(n log n)	O(log n)
最坏	O(n²) — 每次选到最大/最小元素	O(log n)

面试中如果不特别说明，一般讨论的是最坏情况复杂度。因为它代表了算法的性能保证。

空间复杂度

空间复杂度衡量算法运行时额外占用的内存空间随输入规模的增长趋势。

注意：输入数据本身占用的空间通常不计算在内，只计算额外申请的空间。

辅助空间

javascript

function twoSum(nums, target) {
  const map = {};                    // 额外的哈希表
  for (let i = 0; i < nums.length; i++) {
    if (map[target - nums[i]] !== undefined) {
      return [map[target - nums[i]], i];
    }
    map[nums[i]] = i;
  }
}

哈希表最多存 n 个元素，空间复杂度 = O(n)。

栈空间（递归）

递归调用会占用调用栈空间。递归深度就是栈空间的消耗：

javascript

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

对于平衡二叉树，递归深度 = O(log n)；对于极端不平衡的树（链状），递归深度 = O(n)。

原地算法

如果一个算法只使用 O(1) 的额外空间（不随输入规模增长），称为原地算法。比如冒泡排序、快速排序（不考虑递归栈）都是原地算法。

常见算法复杂度速查表

算法	时间（平均）	时间（最坏）	空间
二分查找	O(log n)	O(log n)	O(1)
哈希表查找	O(1)	O(n)	O(n)
冒泡排序	O(n²)	O(n²)	O(1)
归并排序	O(n log n)	O(n log n)	O(n)
快速排序	O(n log n)	O(n²)	O(log n)
堆排序	O(n log n)	O(n log n)	O(1)
BFS/DFS	O(V + E)	O(V + E)	O(V)
动态规划	视问题而定	视问题而定	O(n) ~ O(n²)
二叉树遍历	O(n)	O(n)	O(h)，h 为树高
堆操作（插入/删除）	O(log n)	O(log n)	O(1)

均摊分析简介

有些操作大部分时候很快，偶尔一次很慢，但平均下来每次操作的代价仍然很低。这就是均摊分析（Amortized Analysis）。

经典案例：动态数组

JavaScript 的 Array.push() 底层实现中，当数组容量不够时需要扩容（通常翻倍），这一次操作是 O(n)。但因为扩容的频率越来越低，均摊到每次 push 操作的代价仍然是 O(1)。

直觉理解：

push 1 次 → 不扩容 → O(1)
push 2 次 → 扩容 → O(2)，但分摊给 2 次操作 → O(1)
push 4 次 → 扩容 → O(4)，但分摊给 4 次操作 → O(1)

总 n 次 push 的总代价约为 2n，均摊每次 O(1)。

面试中的应用

面试时一般不要求严格证明均摊复杂度，但你需要知道以下结论：

动态数组的 push/pop 是均摊 O(1)
哈希表的插入/查找是均摊 O(1)
并查集的 find/union 使用路径压缩 + 按秩合并后是均摊 O(α(n))，近似 O(1)

面试中的复杂度分析技巧

从约束倒推算法

面试题通常会给出输入规模的范围，你可以据此判断期望的复杂度：

输入规模 n	可接受的复杂度	可能的算法
n <= 20	O(2^n)、O(n!)	回溯、暴力枚举
n <= 500	O(n³)	三层循环、区间 DP
n <= 5000	O(n²)	两层循环、简单 DP
n <= 10⁵	O(n log n)	排序、二分、堆
n <= 10⁶	O(n)	双指针、哈希表、前缀和
n <= 10⁸	O(log n)、O(1)	数学公式、二分

这个表在审题时非常有用——看到 n <= 10⁵，你就知道 O(n²) 的暴力法会超时，需要想 O(n log n) 或 O(n) 的方案。

主动说出复杂度

写完代码后，不等面试官问，主动分析时间和空间复杂度。这会给面试官留下"基本功扎实"的印象。

复杂度分析

场景引入

什么是大 O 表示法

常见复杂度级别

如何分析时间复杂度

规则一：顺序执行 —— 取最大

规则二：嵌套循环 —— 相乘

规则三：对数级 —— 每次缩半

规则四：递归 —— 画递归树

最好、最坏、平均情况

空间复杂度

辅助空间

栈空间（递归）

原地算法

常见算法复杂度速查表

均摊分析简介

经典案例：动态数组

面试中的应用

面试中的复杂度分析技巧

从约束倒推算法

主动说出复杂度

相关题目

延伸阅读

复杂度分析 ​

场景引入 ​

什么是大 O 表示法 ​

常见复杂度级别 ​

如何分析时间复杂度 ​

规则一：顺序执行 —— 取最大 ​

规则二：嵌套循环 —— 相乘 ​

规则三：对数级 —— 每次缩半 ​

规则四：递归 —— 画递归树 ​

最好、最坏、平均情况 ​

空间复杂度 ​

辅助空间 ​

栈空间（递归） ​

原地算法 ​

常见算法复杂度速查表 ​

均摊分析简介 ​

经典案例：动态数组 ​

面试中的应用 ​

面试中的复杂度分析技巧 ​

从约束倒推算法 ​

主动说出复杂度 ​

相关题目 ​

延伸阅读 ​

复杂度分析

场景引入

什么是大 O 表示法

常见复杂度级别

如何分析时间复杂度

规则一：顺序执行 —— 取最大

规则二：嵌套循环 —— 相乘

规则三：对数级 —— 每次缩半

规则四：递归 —— 画递归树

最好、最坏、平均情况

空间复杂度

辅助空间

栈空间（递归）

原地算法

常见算法复杂度速查表

均摊分析简介

经典案例：动态数组

面试中的应用

面试中的复杂度分析技巧

从约束倒推算法

主动说出复杂度

相关题目

延伸阅读