第92题 时间复杂度与空间复杂度基本概念

什么是复杂度

• 程序执行需要的计算量和内存空间
• 复杂度是数量级（方便记忆推广）不是具体的数字
• 一般针对一个具体的算法，而非一个完整的系统

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

• O(n)一次就够（数量级）
• O(n)和传输的数据一样（数量级）
• O(n^2)数据量的平方（数量级）
• O(logn)数据量的对数（数量级）
• O(n*logn)数据量*数据量的对数（数量级）

    function fn1(obj) {
      // O(1)
      return obj.a + obj.b
    }
    
    function fn2(arr) {
      // O(n)
      for(let i = 0;i<arr.length;i++) {
        // 一层for循环
      }
    }
    
    function fn3(arr) {
      // O(n^2)
      for(let i = 0;i<arr.length;i++) {
        for(let j = 0;i<arr.length;j++) {
          // 二层for循环
        }
      }
    }
    
    function fn4(arr) {
      // 二分 O(logn)
      for() {
    
      }
    }

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

• O(1)有限的、可数的空间（数量级）
• O(n)和输入的数据量相同的空间（数量级）