时间空间复杂度基础

问题

什么是时间复杂度和空间复杂度？如何分析一段代码的复杂度？

解答

时间复杂度

时间复杂度描述算法执行时间随输入规模增长的变化趋势，用大 O 表示法。

// O(1) - 常数时间
function getFirst(arr) {
  return arr[0]; // 无论数组多大，只执行一次
}

// O(n) - 线性时间
function sum(arr) {
  let total = 0;
  for (let i = 0; i < arr.length; i++) {
    total += arr[i]; // 执行 n 次
  }
  return total;
}

// O(n²) - 平方时间
function bubbleSort(arr) {
  const n = arr.length;
  for (let i = 0; i < n; i++) {        // 外层 n 次
    for (let j = 0; j < n - i - 1; j++) { // 内层 n 次
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }
  return arr;
}

// O(log n) - 对数时间
function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;
  
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) {
      left = mid + 1;  // 每次排除一半
    } else {
      right = mid - 1;
    }
  }
  return -1;
}

// O(n log n) - 线性对数时间
function mergeSort(arr) {
  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) 合并
}

function merge(left, right) {
  const result = [];
  let i = 0, j = 0;
  
  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) {
      result.push(left[i++]);
    } else {
      result.push(right[j++]);
    }
  }
  
  return result.concat(left.slice(i)).concat(right.slice(j));
}

空间复杂度

空间复杂度描述算法占用内存随输入规模增长的变化趋势。

// O(1) - 常数空间
function findMax(arr) {
  let max = arr[0]; // 只用一个变量
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] > max) max = arr[i];
  }
  return max;
}

// O(n) - 线性空间
function copyArray(arr) {
  const copy = []; // 新数组大小与输入成正比
  for (let i = 0; i < arr.length; i++) {
    copy.push(arr[i]);
  }
  return copy;
}

// O(n) - 递归调用栈
function factorial(n) {
  if (n <= 1) return 1;
  return n * factorial(n - 1); // 调用栈深度为 n
}

// O(n²) - 二维数组
function createMatrix(n) {
  const matrix = [];
  for (let i = 0; i < n; i++) {
    matrix[i] = new Array(n).fill(0); // n × n 空间
  }
  return matrix;
}

常见复杂度对比

复杂度	名称	示例
O(1)	常数	数组访问、哈希表查找
O(log n)	对数	二分查找
O(n)	线性	遍历数组
O(n log n)	线性对数	快排、归并排序
O(n²)	平方	冒泡排序、嵌套循环
O(2ⁿ)	指数	递归斐波那契

分析技巧

// 1. 顺序执行：取最大
function example1(arr) {
  let sum = 0;
  for (let x of arr) sum += x;    // O(n)
  for (let x of arr) sum += x;    // O(n)
  return sum;                      // 总体 O(n)
}

// 2. 嵌套循环：相乘
function example2(arr) {
  for (let i = 0; i < arr.length; i++) {      // O(n)
    for (let j = 0; j < arr.length; j++) {    // O(n)
      console.log(arr[i], arr[j]);            // 总体 O(n²)
    }
  }
}

// 3. 条件分支：取最大
function example3(arr, flag) {
  if (flag) {
    for (let x of arr) console.log(x);        // O(n)
  } else {
    for (let i of arr) {
      for (let j of arr) console.log(i, j);   // O(n²)
    }
  }
  // 总体 O(n²)
}

关键点

• 时间复杂度关注执行次数，空间复杂度关注内存占用
• 大 O 表示法只保留最高阶项，忽略常数和低阶项
• 递归算法要考虑调用栈的空间消耗
• 分析时关注循环次数和嵌套层数
• 常见排序：O(n²) 冒泡/选择，O(n log n) 快排/归并