算法复杂度是什么？

算法复杂度是什么？

算法复杂度是衡量算法效率的重要指标，主要包括时间复杂度和空间复杂度。本文将通过具体的代码示例，帮助读者理解不同复杂度的含义及其在实际开发中的应用。

什么是复杂度

复杂度主要关注程序执行时需要的计算量和内存空间，它是一个数量级的概念，而不是具体的数字。通常，复杂度分析针对的是具体的算法，而不是整个系统。

时间复杂度

时间复杂度衡量的是程序执行时需要的计算量（CPU）。

• O(1)：常数时间复杂度
  这表示算法的执行时间不随输入数据量的增加而变化。

  // O(1)
  obj.a + obj.b + obj.c; // 4~5 次
  

• O(N)：线性时间复杂度
  这表示算法的执行时间与输入数据量成正比。

  function fn(arr = []) {
    // O(N)
    for (let i = 0; i < arr.length; i++) {
      console.log(i);
    }
  }
  

• O(N^2)：平方时间复杂度
  这表示算法的执行时间与输入数据量的平方成正比。

  function fn(arr = []) {
    // O(N^2)
    for (let i = 0; i < arr.length; i++) {
      for (let j = 0; j < arr.length; j++) {
        console.log(i, j);
      }
    }
  }
  

• O(logN)：对数时间复杂度
  这表示算法的执行时间与输入数据量的对数成正比，常见于二分查找等算法。

  // arr 是一个有序数组，从中查找一个值，如 6
  function fn(arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]) {
    // O(logN)
    // 利用 二分思想 从中间开始查找
  }
  

• O(N^logN)：N乘以对数时间复杂度
  这表示算法的执行时间与输入数据量乘以其对数成正比。

  // arr 是一个有序数组，从中查找一个值，如 6，然后嵌套一个 for 循环
  function fn(arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]) {
    // O(N^logN)
    for (let i = 0; i < arr.length; i++) {
      // 利用 二分思想 从中间开始查找
    }
  }
  

空间复杂度

空间复杂度衡量的是程序执行时需要的内存空间。

• O(1)：常数空间复杂度
  这表示算法占用的额外空间不随输入数据量的增加而变化。

  function fn(arr = []) {
    // O(1)
  }
  

• O(N)：线性空间复杂度
  这表示算法占用的额外空间与输入数据量成正比。

  function fn(arr = []) {
    // O(N)
    const arr2 = [];
    for (let i = 0; i < arr.length; i++) {
    }
    // ...
    return arr2;
  }
  

当一个算法的时间复杂度达到O(N^2)时，通常就变得不太实用了。例如，虚拟DOM中的树形diff算法，未经优化的普通diff算法的时间复杂度为O(N^3)，而React和Vue优化后的diff算法则降低到了O(N)。

总结来说，复杂度用O(...)表示，内部是一个函数表达式，表示算法的效率。对于前端开发而言，通常更关注时间复杂度，因为现代计算机的内存容量相对充裕。