• 1. 什么是复杂度

1. 什么是复杂度

1. 程序执行时需要的计算量和内存空间（和代码是否简洁无关）
2. 复杂度是数量级（方便记忆、推广），不是具体的数字
3. 一般针对一个具体的算法，而非一个完整的系统。

• 时间复杂度：程序执行时需要的计算量（CPU）

  

  • O(1) 一次就够（数量级）

    function fn (obj = {}, key) {
      return obj[key];
    }

  • O(n) 和传输的数据量一样（数量级）

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

  • O(n ^ 2) 数据量的平方（数量级）

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

  • O(logn) 数据量的对数（数量级）
    • 二分排序
  • O(n*logn) 数据量 * 数据量的对数（数量级）
    • n * 二分排序

• 空间复杂度：程序执行时需要的内存空间

  • O(1) 有限的、可数的空间（数量级）

    function fn (arr = []) {
      // 类似这种 a b 变量 空间复杂度就是 O(1)
      const a = arr[1]
      const b = arr[2]
    }

  • O(n) 和输入的数据量形同的空间（数量级）

    function fn (arr = []) {
      const arr2 = []
    
      for (let i = 0; i < arr.length; i++) {
        // 这种 空间复杂度就是 O(n)
        arr2[i] = arr[i]
      }
      return arr2
    }