时间与空间复杂度

什么是复杂度？

复杂度描述算法的资源消耗如何随输入规模增长：

时间复杂度: 执行需要多少步骤
空间复杂度: 需要多少额外内存

🎮 交互式复杂度对比

📊复杂度对比

输入规模 n =10

选择要对比的复杂度:

O(1)

≈ 1 纳秒

O(log n)

≈ 3 纳秒

O(n)

≈ 10 纳秒

O(n log n)

≈ 33 纳秒

O(n²)

100

≈ 100 纳秒

💡

当 n 较小时，各复杂度差异不明显。试试增加 n 到 20 或更大！

常见复杂度速查表

复杂度	名称	n=10	n=100	n=1000	典型算法
O(1)	常数	1	1	1	数组访问、哈希查找
O(log n)	对数	3	7	10	二分查找
O(n)	线性	10	100	1,000	遍历数组
O(n log n)	线性对数	33	664	9,966	快排、归并排序
O(n²)	平方	100	10,000	1,000,000	冒泡排序、嵌套循环
O(2ⁿ)	指数	1,024	10³⁰	💥	斐波那契递归
O(n!)	阶乘	3,628,800	💥	💥	全排列暴力

代码示例

O(1) - 常数时间

function getFirst(arr) {
  return arr[0]; // 无论数组多大，只访问一次
}

O(n) - 线性时间

function findMax(arr) {
  let max = arr[0];
  for (let i = 1; i < arr.length; i++) { // 遍历 n 次
    if (arr[i] > max) max = arr[i];
  }
  return max;
}

O(n²) - 平方时间

function bubbleSort(arr) {
  for (let i = 0; i < arr.length; i++) {       // n 次
    for (let j = 0; j < arr.length - i; j++) { // n 次
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }
}

O(log n) - 对数时间

function binarySearch(arr, target) {
  let left = 0, 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(1)	原地操作	冒泡排序、变量交换
O(n)	额外数组	归并排序的临时数组
O(log n)	递归栈	快排的递归深度
O(n²)	二维数组	动态规划表

💡 记忆技巧

O(1): 一步到位，跟数据量无关
O(log n): 每次砍半（二分思想）
O(n): 看一遍全部数据
O(n log n): 最优排序的极限
O(n²): 两层嵌套循环
O(2ⁿ): 爆炸增长，慎用！