通过js示例讲解时间复杂度与空间复杂度

下面我将详细讲解“通过JS示例讲解时间复杂度和空间复杂度”的攻略。

什么是时间复杂度和空间复杂度

时间复杂度和空间复杂度都是算法评估的重要指标，分别表示了算法执行时间和所需内存空间的量度。

• 时间复杂度：指执行算法所需时间的数量级，常用大O表示法来表示。例如，O(1)表示执行时间常量，O(n)表示执行时间与数据规模成线性比例，O(n^2)表示有执行时间与数据规模的平方成比例。

• 空间复杂度：指执行算法所需的内存空间的数量级，也常用大O表示法来表示。例如，O(1)表示空间常量，O(n)表示空间与数据规模成线性比例，O(n^2)表示空间与数据规模的平方成比例。

示例一：冒泡排序的时间复杂度和空间复杂度

下面我们以冒泡排序为例，来说明时间复杂度和空间复杂度。

冒泡排序的原理是，比较相邻的两个元素，如果前一个元素比后一个元素大，则交换它们的位置。

function bubbleSort(array) {
  const n = array.length;
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n - i - 1; j++) {
      if (array[j] > array[j + 1]) {
        // 交换位置
        const temp = array[j];
        array[j] = array[j + 1];
        array[j + 1] = temp;
      }
    }
  }
  return array;
}

// 示例
const arr = [5, 3, 9, 7, 6];
console.log(bubbleSort(arr));  // [3, 5, 6, 7, 9]

上述代码中，两层循环嵌套，在最坏情况下，即待排序的数据为逆序，时间复杂度为O(n^2)。

空间上，冒泡排序只使用了一个常量变量temp，所以空间复杂度为O(1)。

示例二：Fibonacci 数列的时间复杂度和空间复杂度

再来看一个计算 Fibonacci 数列的例子，它需要用到递归实现：

function fibonacci(n) {
  if (n <= 2) {
    return 1;
  } else {
    return fibonacci(n - 1) + fibonacci(n - 2);
  }
}

// 示例
console.log(fibonacci(8)); // 21

Fibonacci序列指的是数列中每个数都是前两个数之和，例如1, 1, 2, 3, 5, 8, 13...。

上述代码中，fibonacci(n - 1) 和 fibonacci(n - 2) 都会分别再次调用 fibonacci 函数，这样会反复递归，直到递归栈的空间被消耗完毕，被认为是一种时间上的浪费。时间复杂度为O(2^n)。

空间上，递归调用可以消耗大量的空间，空间复杂度为O(n)。

总结

时间复杂度和空间复杂度的正确评估，对于算法和程序的优化非常有帮助。前者决定了程序的执行速度，后者决定了程序的空间占用。

在编写程序时，我们应该尽可能选择时间复杂度低、空间复杂度小的算法。