时间复杂度和空间复杂度

时间复杂度和空间复杂度是衡量算法效率的两个重要指标，下面是详细介绍：

时间复杂度（Time Complexity）

定义

时间复杂度用于描述算法执行时间随输入规模增长的变化趋势，它并不表示具体的执行时间，而是表示执行时间与输入规模之间的增长关系。（例如：for(let i = 0; i < n; i++) 循环了 n 次，时间复杂度为 O(n)，与代码执行次数有关系）

常见时间复杂度

1. O(1)：常数时间复杂度 无论输入规模多大，算法的执行时间都是固定的。

function getFirstElement(arr) {
  return arr[0] // 只需要一步操作
}

2. O(log n)：对数时间复杂度 当输入规模增大时，执行时间会以对数形式增长，通常出现在二分法等算法中。

function binarySearch(arr, target) {
  let left = 0
  let right = arr.length - 1
  while (left <= right) {
    let 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
}

log n 是如何计算的：

核心思想：每次将搜索区间减半

设初始数据量为 n，每轮缩小一半，直到只剩 1 个元素为止：

轮数	剩余数量
0	n
1	n/2
2	n/4
3	n/8
...	...
k	n/(2^k) = 1 ➡️ 解得 k = log₂n

3. O(n)：线性时间复杂度 执行时间与输入规模成线性关系，如遍历数组。

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

4. O(n²)：平方时间复杂度 执行时间与输入规模的平方成正比，如冒泡排序。

function bubbleSort(arr) {
  const n = arr.length
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n - i - 1; j++) {
      // 嵌套循环
      if (arr[j] > arr[j + 1]) {
        ;[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
      }
    }
  }
  return arr
}

空间复杂度（Space Complexity）

定义

空间复杂度描述的是算法在执行过程中所需要的额外存储空间与输入规模之间的增长关系。

常见空间复杂度

1. O(1)：常数空间复杂度 算法只需要固定的额外空间。

function sum(a, b) {
  return a + b // 只需要存储a、b和结果
}

2. O(n)：线性空间复杂度 算法需要的额外空间与输入规模成正比，如复制数组。

function doubleArray(arr) {
  const result = []
  for (let i = 0; i < arr.length; i++) {
    result.push(arr[i] * 2) // 需要创建一个新数组
  }
  return result
}

3. O(n²)：平方空间复杂度 常见于需要创建二维数组的情况。

function createMatrix(n) {
  const matrix = []
  for (let i = 0; i < n; i++) {
    matrix[i] = []
    for (let j = 0; j < n; j++) {
      matrix[i][j] = i * j // 创建一个n×n的矩阵
    }
  }
  return matrix
}

4. O(log n)：对数空间复杂度 常见于递归算法，递归调用栈的深度为对数级（递归减半）。

function binarySearchRecursive(arr, target, left = 0, right = arr.length - 1) {
  if (left > right) return -1
  const mid = Math.floor((left + right) / 2)
  if (arr[mid] === target) return mid
  if (arr[mid] < target) {
    return binarySearchRecursive(arr, target, mid + 1, right) // 递归调用
  } else {
    return binarySearchRecursive(arr, target, left, mid - 1)
  }
}

总结

• 时间复杂度关注的是算法执行时间的效率。
• 空间复杂度关注的是算法占用存储空间的效率。

在设计算法时，通常需要在时间复杂度和空间复杂度之间进行权衡。