跳到主要内容

复杂度分析

为什么要学复杂度分析？​

复杂度分析是算法的「通用语言」，它能帮你：

  1. 评估算法优劣：不用跑代码就能判断哪个算法更好
  2. 预测性能瓶颈：数据量增大时，程序会不会变慢
  3. 面试必考：几乎每道算法题都会问「时间/空间复杂度是多少」

时间复杂度​

什么是时间复杂度？​

时间复杂度描述的是：随着输入规模 n 的增长，算法执行时间的增长趋势。

关键点

我们关心的不是具体执行多少秒，而是增长的速度。

大 O 表示法​

用 O(f(n))O(f(n)) 表示时间复杂度，其中 f(n) 是关于输入规模 n 的函数。

复杂度名称示例
O(1)O(1)常数阶数组取值、哈希表查找
O(log⁡n)O(\log n)对数阶二分查找
O(n)O(n)线性阶遍历数组
O(nlog⁡n)O(n \log n)线性对数阶快速排序、归并排序
O(n2)O(n^2)平方阶冒泡排序、双重循环
O(2n)O(2^n)指数阶递归求斐波那契（无优化）
O(n!)O(n!)阶乘阶全排列

增长趋势对比​

当 n = 1000 时：
O(1)       = 1
O(log n)   ≈ 10
O(n)       = 1,000
O(n log n) ≈ 10,000
O(n²)      = 1,000,000
O(2ⁿ)      = 天文数字（不可接受）

如何分析时间复杂度​

规则 1：只看最高阶​

// 这段代码的时间复杂度是多少？
function example(n: number): void {
  // 第一部分：O(n)
  for (let i = 0; i < n; i++) {
    console.log(i);
  }

  // 第二部分：O(n²)
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      console.log(i, j);
    }
  }
}

// 答案：O(n) + O(n²) = O(n²)
// 只保留最高阶项

规则 2：忽略常数系数​

// 这两个函数的时间复杂度相同，都是 O(n)
function loop1(n: number): void {
  for (let i = 0; i < n; i++) {
    console.log(i);
  }
}

function loop2(n: number): void {
  for (let i = 0; i < 3 * n; i++) {  // 3n 次
    console.log(i);
  }
}

// O(3n) 简化为 O(n)

规则 3：嵌套循环相乘​

// 嵌套循环：复杂度相乘
function nested(n: number): void {
  for (let i = 0; i < n; i++) {       // O(n)
    for (let j = 0; j < n; j++) {     // O(n)
      console.log(i, j);              // O(n × n) = O(n²)
    }
  }
}

规则 4：顺序代码相加​

// 顺序执行：复杂度相加
function sequential(n: number): void {
  // 第一个循环 O(n)
  for (let i = 0; i < n; i++) {
    console.log(i);
  }

  // 第二个循环 O(n)
  for (let j = 0; j < n; j++) {
    console.log(j);
  }
}
// 总复杂度：O(n) + O(n) = O(2n) = O(n)

常见代码的时间复杂度​

O(1)O(1) - 常数阶​

// 数组按索引访问
function getElement(arr: number[], index: number): number {
  return arr[index];  // O(1)
}

// 哈希表操作
function hashOperation(): void {
  const map = new Map<string, number>();
  map.set('key', 1);     // O(1)
  map.get('key');        // O(1)
  map.has('key');        // O(1)
}

O(log⁡n)O(\log n) - 对数阶​

// 二分查找
function binarySearch(nums: number[], target: number): number {
  let left = 0;
  let right = nums.length - 1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (nums[mid] === target) return mid;
    if (nums[mid] < target) left = mid + 1;
    else right = mid - 1;
  }

  return -1;
}
// 每次循环排除一半数据，循环 log₂n 次
为什么是 log⁡n\log n？

如果数组长度是 n，每次折半：

  • 第 1 次后剩 n/2
  • 第 2 次后剩 n/4
  • 第 k 次后剩 n/2kn/2^k

当 n/2k=1n/2^k = 1 时，k=log⁡2nk = \log_2 n

O(n)O(n) - 线性阶​

// 单层循环
function findMax(nums: number[]): number {
  let max = nums[0];
  for (let i = 1; i < nums.length; i++) {  // O(n)
    if (nums[i] > max) {
      max = nums[i];
    }
  }
  return max;
}

O(nlog⁡n)O(n \log n) - 线性对数阶​

// 归并排序
function mergeSort(arr: number[]): number[] {
  if (arr.length <= 1) return arr;

  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));   // 递归 log n 层
  const right = mergeSort(arr.slice(mid));

  return merge(left, right);  // 每层合并 O(n)
}
// 总复杂度：O(n) × O(log n) = O(n log n)

O(n2)O(n^2) - 平方阶​

// 冒泡排序
function bubbleSort(arr: number[]): number[] {
  const n = arr.length;
  for (let i = 0; i < n; i++) {           // O(n)
    for (let j = 0; j < n - i - 1; j++) { // O(n)
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }
  return arr;
}
// O(n × n) = O(n²)

O(2n)O(2^n) - 指数阶​

// 斐波那契数列（无优化递归）
function fibonacci(n: number): number {
  if (n <= 1) return n;
  return fibonacci(n - 1) + fibonacci(n - 2);
}
// 每次调用分裂成两个子调用，形成二叉树
// 树的节点数约为 2ⁿ
警告

O(2n)O(2^n) 复杂度在 n > 30 时就会非常慢，实际开发中要避免。

空间复杂度​

什么是空间复杂度？​

空间复杂度描述的是：算法运行过程中，额外使用的内存空间。

注意
  • 输入数据本身占用的空间不算
  • 只计算算法额外申请的空间

常见空间复杂度​

复杂度说明示例
O(1)O(1)只用固定几个变量双指针、原地排序
O(n)O(n)额外数组/哈希表两数之和的哈希解法
O(n2)O(n^2)二维数组动态规划的 dp 表

O(1)O(1) 空间​

// 只使用固定数量的变量
function swap(arr: number[], i: number, j: number): void {
  const temp = arr[i];  // 只用了 1 个额外变量
  arr[i] = arr[j];
  arr[j] = temp;
}

// 双指针反转数组
function reverse(arr: number[]): number[] {
  let left = 0;
  let right = arr.length - 1;

  while (left < right) {
    [arr[left], arr[right]] = [arr[right], arr[left]];
    left++;
    right--;
  }

  return arr;
}
// 只用了 left、right 两个变量，O(1) 空间

O(n)O(n) 空间​

// 使用哈希表
function twoSum(nums: number[], target: number): number[] {
  const map = new Map<number, number>();  // 最多存 n 个元素

  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];
    if (map.has(complement)) {
      return [map.get(complement)!, i];
    }
    map.set(nums[i], i);
  }

  return [];
}
// 空间复杂度 O(n)

递归的空间复杂度​

递归调用会使用栈空间：

// 递归深度为 n
function recursiveSum(n: number): number {
  if (n === 0) return 0;
  return n + recursiveSum(n - 1);
}
// 空间复杂度 O(n)，因为递归栈深度为 n

// 递归深度为 log n
function binaryRecursive(n: number): void {
  if (n <= 1) return;
  binaryRecursive(Math.floor(n / 2));
}
// 空间复杂度 O(log n)

最好、最坏、平均复杂度​

有些算法的复杂度取决于输入数据的特点：

快速排序的例子​

function quickSort(arr: number[]): number[] {
  if (arr.length <= 1) return arr;

  const pivot = arr[0];
  const left = arr.slice(1).filter(x => x < pivot);
  const right = arr.slice(1).filter(x => x >= pivot);

  return [...quickSort(left), pivot, ...quickSort(right)];
}
情况复杂度说明
最好O(nlog⁡n)O(n \log n)每次都能均匀分割
最坏O(n2)O(n^2)数组已排序，每次只能分出一个元素
平均O(nlog⁡n)O(n \log n)随机数据
面试技巧
  • 一般说的复杂度指最坏情况或平均情况
  • 面试时要能说出为什么是这个复杂度

复杂度分析 Checklist​

分析算法复杂度时，问自己：

□ 有几层循环？嵌套还是顺序？
□ 循环次数和 n 是什么关系？
□ 有没有递归？递归深度是多少？
□ 用了什么数据结构？占用多少空间？
□ 最好/最坏/平均情况有区别吗？

常见面试问题​

Q1: O(n)O(n) 和 O(2n)O(2n) 有区别吗？​

答案：从大 O 表示法角度，它们是相同的，都是 O(n)O(n)。因为大 O 关注的是增长趋势，常数系数会被忽略。

Q2: 为什么要用大 O 而不是具体运行时间？​

答案：

  1. 运行时间受硬件影响，不同电脑跑出来不一样
  2. 大 O 描述的是可扩展性，当数据量变大时的表现
  3. 更方便比较不同算法的优劣

Q3: 空间换时间是什么意思？​

答案：用更多内存来减少计算时间。例如两数之和：

  • 暴力解法：O(n2)O(n^2) 时间，O(1)O(1) 空间
  • 哈希表解法：O(n)O(n) 时间，O(n)O(n) 空间

相关链接​