算法基础🔮 时间复杂度、空间复杂度 [ ricepudding ]

时间复杂度

什么是时间复杂度？

时间复杂度 = 算法执行时间随数据规模 n 增长的趋势，不是精确秒数，而是量级；
1. 数据规模：n （比如数组长度、循环次数、节点数）；
2. 时间复杂度：用大 O 表示法 O(…)；
只关心增长最快的那一项，忽略常数、低次项；

最常见的 7 种复杂度（从快到慢）

O(1) 常数阶

不管 n 多大，执行次数固定；
1. 执行次数：常数；
2. 复杂度：O(1)；

示例代码：

function fn(arr) {
  return arr[0] + arr[1]; // 只执行2步
}

O(logN) 对数阶

每次循环规模减半，典型：二分查找；
1. 每次范围 ÷2；
2. 循环次数 ≈ log₂n；
3. 复杂度：O(log n)；

示例代码：

function binarySearch(arr, target) {
  let l = 0, r = arr.length - 1;
  while (l <= r) {
    const mid = (l + r) >> 1;   // 1步
    if (arr[mid] === target) return mid;
    else if (arr[mid] < target) l = mid + 1;
    else r = mid - 1;
  }
}

O(N) 线性阶

跟 n 成正比，一层循环；
1. 执行 n 次；
2. 复杂度：O(n)；

示例代码：

function fn(arr) {
  for (let i = 0; i < arr.length; i++) {
    console.log(i);
  }
}

O(NlogN) 线性对数阶

一层循环里套 log n 操作，典型：快速排序、归并排序；

示例代码：

// 简化理解：外层n，内层log n
for (let i = 0; i < n; i++) {
  let j = 1;
  while (j < n) {
    j *= 2; // log n 次
  }
}

O(N²) 平方阶

两层嵌套循环，执行 n × n = n² 次；

示例代码：

for (let i = 0; i < n; i++) {
  for (let j = 0; j < n; j++) {
    // ...
  }
}

O(2ⁿ) 指数阶

递归求斐波那契典型，每一层递归数量翻倍 （巨慢）；

示例代码：

function fib(n) {
  if (n <= 1) return n;

  return fib(n-1) + fib(n-2);
}

O(N!) 阶乘

阶乘阶对应数学上常见的 “全排列”，即给定 N 个互不重复的元素，求其所有可能的排列方案数量为：N × (N−1) × (N−2) × ⋯ × 2 × 1 = N!；

示例代码：

function algorithm(N) {
  if (N <= 0) return 1; 

  let count = 0;
  for (let i = 0; i < N; i++) {
    count += algorithm(N - 1);
  }

  return count;
}

计算时间复杂度的 4 条黄金规则

规则 1：只保留最高次项，O(n + n²) → O(n²)、O(3n² + 5n + 9) → O(n²)；
规则 2：忽略常数系数，O(2n) → O(n)，O(1000) → O(1)；
规则 3：嵌套循环相乘；
规则 4：顺序代码取最大，O(n) + O(log n) + O(1) => O(n)；

空间复杂度

什么是空间复杂度？

空间复杂度 = 算法运行所需存储空间随数据规模 n 增长的趋势，同样用大 O 表示法 O(…) 描述，关注的是：
1. 算法额外占用的临时空间 （不是输入数据本身的空间）；
2. 空间增长的量级 （忽略常数、低次项）；
核心：判断算法执行过程中，需要 “额外开辟多少内存”；

最常见的 4 种空间复杂度（从优到差）

O(1) 常数空间

不管 n 多大，额外开辟的空间固定 （几个变量）；

示例代码：

// 示例1：求数组和
function sum(arr) {
  let total = 0; // 1个临时变量
  for (let i = 0; i < arr.length; i++) { // 1个临时变量i
    total += arr[i];
  }
  return total;
}

O(logN) 对数阶

额外空间随 n 对数级增长 （典型：二分查找的递归版），递归深度为 log n，调用栈占用 log n 个空间；

示例代码：

// 递归版二分查找
function binarySearch(arr, target, l, r) {
  if (l > r) return -1;
  const mid = (l + r) >> 1;
  if (arr[mid] === target) return mid;
  else if (arr[mid] < target) {
    return binarySearch(arr, target, mid + 1, r); // 递归深度log n
  } else {
    return binarySearch(arr, target, l, mid - 1);
  }
}

O(N) 线性阶

额外开辟的空间随 n 线性增长 （比如数组、哈希表、递归）；

示例代码：

// 示例1：递归（递归调用栈的空间）
function fn(n) {
  if (n === 0) return;
  fn(n - 1); // 递归深度为n，调用栈占用n个空间
}

// 示例2：创建新数组存储结果
function doubleArr(arr) {
  const res = []; // 新数组，长度和arr一致（n）
  for (let i = 0; i < arr.length; i++) {
    res.push(arr[i] * 2);
  }
  return res;
}

O (N²) 平方阶

额外空间随 n 平方级增长 （典型：二维数组），创建了 n×n 的二维数组，或嵌套递归 / 循环开辟大量空间；

示例代码：

function algorithm(N) {
  if (N <= 0) return 0;
  
  let nums = new Array(N);
  return algorithm(N - 1);
}

// 示例：创建n×n的二维数组
function create2DArr(n) {
  const matrix = [];
  for (let i = 0; i < n; i++) {
    matrix[i] = new Array(n); // 每行创建长度为n的数组
  }
  return matrix;
}

计算空间复杂度的 3 条核心规则

规则 1：只关注「额外空间」，忽略输入空间：
1. 比如函数参数传入的数组 arr （长度 n），是输入空间，不算入空间复杂度；
2. 函数内部新创建的数组 / 变量，才是额外空间，需要计算；
规则 2：递归的空间复杂度 = 递归深度：
1. 递归调用会占用「调用栈空间」，栈的深度就是空间复杂度的量级；
2. 比如：
  - 线性递归 （fn(n) → fn(n-1) → … → fn(0)）：深度 n → O(n)；
  - 二分递归 （二分查找递归版）：深度 logn → O(logn)；
规则 3：忽略常数，只保留最高次项：
1. O(2n) → O(n) （忽略系数）；
2. O(n + 10) → O(n) （忽略常数）；
3. O(n² + n) → O(n²) （保留最高次项）；

复杂度增长对比（直观感受）

时间复杂度	n=10	n=100	n=1024	增长趋势
`O(1)`	1	1	1	完全不变（最快）
`O(log n)`	≈3	≈7	≈10	极缓慢增长
`O(n)`	10	100	1024	线性增长
`O(n log n)`	≈30	≈700	≈10240	温和增长
`O(n²)`	100	10000	1048576	快速增长
`O(2ⁿ)`	1024	10³⁰	远超天文数字	爆炸式增长（最慢）

打赏作者

您的打赏是我前进的动力

微信

支付宝

leetcode🧑‍💻 515. 在每个树行中找最大值

算法基础🔮 数组

你好👏🏻，我是 ✍🏻 疯狂 codding 中...

粽子

这有关于前端开发的技术文档和你分享。

相信你可以在这里找到对你有用的知识和教程。

了解更多