【图解算法】前端思维学习图解算法数据结构笔记(一)之算法复杂度

书名是《图解算法数据结构》，在力扣看到的，准备开始系统学习一下算法了。会用前端的语言和思维来学习学习～希望能获得一些见解。第一篇是关于算法复杂度的学习笔记记录。

算法复杂度

复杂度概念

书中介绍，算法复杂度旨在计算在输入数据量 N 的情况下，算法的时间使用和空间使用情况；体现算法运行使用的时间和空间随「数据大小N」而增大的速度

• 时间：假设各操作的运行时间为固定常数，统计算法运行的计算操作的数量，以代表算法运行所需时间
• 空间：统计在最差情况下，算法运行所需使用的”最大空间”
• 数据大小N：算法处理的输入数据量；根据不同算法，具有不同定义
  • 排序算法：N 代表需要排序的元素数量
  • 搜索算法：N 代表搜索范围的元素总数

理解：算法复杂度是在一定的输入数据量下，计算所需要的时间操作数量大小（计算操作数量）和空间的大小来体现复杂度量。

时间复杂度

概念：时间复杂度指输入数据大小为 N 时，算法运行所需花费的时间

注意的是，这里的时间是计算操作数量，和运行绝对时间呈正相关关系，并不相等。

时间复杂度具有最差、平均、最佳三种情况，分别使用O, Θ, Ω三种符号表示

// demo
const find_num = (nums) => {
  for (const num in nums) {
    if (num === 7) return false
  }
  return false
}

// 最佳情况Ω(1)： nums = [7, a, b, c, ...] ，即当数组首个数字为 77 时，无论 nums 有多少元素，线性查找的循环次数都为 11 次；

// 最差情况O(N)： nums = [a, b, c, ...] 且 nums 中所有数字都不为 77 ，此时线性查找会遍历整个数组，循环 N 次

// 平均情况Θ： 需要考虑输入数据的分布情况，计算所有数据情况下的平均时间复杂度；例如本题目，需要考虑数组长度、数组元素的取值范围等

常见的算法时间复杂度大小排序：O(1) < O(logN) < O(N) < O(NlogN) < O(N^2) < O(2^N) < O(N!)

• 常数O(1)：不随输入数据大小 N 的变化而变化
• 线性O(N)：循环运行次数与 N 大小呈线性关系
• 平方O(N^2)：两层循环相互独立，都与 N 呈线性关系，因此总体与 N 呈平方关系
• 指数O(2^N)：指数阶常出现于递归
• 阶乘O(N!)：阶乘阶对应数学上常见的 “全排列” 。即给定 NN 个互不重复的元素，求其所有可能的排列方案。阶乘常使用递归实现，算法原理：第一层分裂出 N 个，第二层分裂出 N−1 个，…… ，直至到第 N 层时终止并回溯
• 对数O(logN)：对数阶与指数阶相反，指数阶为 “每轮分裂出两倍的情况” ，而对数阶是 “每轮排除一半的情况”
• 线性对数O(NlogN)：两层循环相互独立，第一层和第二层时间复杂度分别为 O(logN) 和 O(N)

个人理解

• 常数O(1)：就是传入变量不影响计算，相当于一个未使用的变量。eslint下应该是遇不到的
• 线性O(N)：与输入N线性关系，其中只有一次循环是和输入的N有关
• 平方O(N^2)：两层互相独立的线性关系嵌套，两层嵌套循环，比如冒泡排序
• 指数O(2^N)： 树形图，每个节点都有两个操作，节节往下，第一层祖父节点，2^0 ,第二层就是2^1 ，以此类推，最后就是 2^n-1 次方，加起来就是 2^n
• 阶乘O(N!)：全排列，和上面反过来，第一次=层全部循环一遍，然后第二层操作剔除一个特征操作，以此类推
• 对数O(logN)：和指数反过来，就是二分法，分治这样的算法基础，一分为二或者一分为多。
• 线性对数O(NlogN)：两层循环相互独立，第一层和第二层时间复杂度分别为O(logN)和O(N)

空间复杂度

概念：空间复杂度指在输入数据大小为 N 时，算法运行所使用的暂存空间+输出空间的总体大小

• 输入空间： 存储输入数据所需的空间大小；输入数据
• 暂存空间： 算法运行过程中，存储所有中间变量和对象等数据所需的空间大小；包括数据空间``栈帧空间``指令空间
  • 数据空间：各项变量使用的空间，包括：声明的常量、变量、动态数组、动态对象等使用的内存空间。
  • 栈帧空间：程序调用函数是基于栈实现的，函数在调用期间，占用常量大小的栈帧空间，直至返回后释放。
  • 指令空间：编译后，程序指令所使用的内存空间。
• 输出空间： 算法运行返回时，存储输出数据所需的空间大小；输出数据

最差情况：空间复杂度统计算法在 “最差情况” 下使用的空间大小，以体现算法运行所需预留的空间量，使用符号O表示，包含两种情况

• 最差输入数据：当 N≤10 时，数组 nums 的长度恒定为 10 ，空间复杂度为 O(10) = O(1)；当 N > 10时，数组 nums 长度为 N ，空间复杂度为 O(N) ；因此，空间复杂度应为最差输入数据情况下的 O(N)
• 最差运行点：在执行nums = Array(10).fill(0)时，算法仅使用 O(1) 大小的空间；而当执行 nums = Array(n).fill(0)时，算法使用 O(N) 的空间；因此，空间复杂度应为最差运行点的 O(N)

常见的算法空间复杂度有：O(1) < O(logN) < O(N) < O(N^2) < O(2^N)

• 常数O(1)：普通常量、变量、对象、元素数量与输入数据大小 N 无关的集合，皆使用常数大小的空间
• 线性O(logN)：元素数量与 N 呈线性关系的任意类型集合（常见于一维数组、链表、哈希表等）
• 平方O(N)：元素数量与 N 呈平方关系的任意类型集合（常见于矩阵），皆使用平方大小的空间
• 指数O(N^2)：指数阶常见于二叉树、多叉树
• 对数O(2^N)：对数阶常出现于分治算法的栈帧空间累计、数据类型转换等。如快速排序/数字转化字符串

时空权衡

对于算法的性能，需要从时间和空间的使用情况来综合评价。优良的算法应具备两个特性，即时间和空间复杂度皆较低。而实际上，对于某个算法问题，同时优化时间复杂度和空间复杂度是非常困难的。降低时间复杂度，往往是以提升空间复杂度为代价的，反之亦然。

由于当代计算机的内存充足，通常情况下，算法设计中一般会采取空间换时间的做法，即牺牲部分计算机存储空间，来提升算法的运行速度。

一些DEMO

时间复杂度相关的demo

const algorithm = (n) => {
  let count = 0;
  const a = 100;
  for (const i in n) {
    for (const j in a) {
      count += 1;
    }
  }
  return count;
}
// 时间复杂度是o(N)，一直一层循环是与输入有关

// 冒泡排序
const bubbleSort = (nums) => {
  const n = nums.length;
  for (const i in n - 1) {
    for (const j in n - i - i) {
      if (nums[j] > nums[j + 1]) {
        cache = nums[j]
        nums[j] = nums[j + 1]
        nums[j + 1] = cache
      }
    }
  }
  return nums;
}
// 时间复杂度是O(N^2)，第一层复杂的o(N), 第二层平均循环次数为N/2,复杂度也为o(N)

// 递归
const algorithm = (n) => {
  if (n <= 0) return 1
  const a = algorithm(n - 1)
  const b = algorithm(n - 1)
  return a + b;
}
// 时间复杂度是O(2^N)

// 递归
const algorithm = (n) => {
  if (n <= 0) return 1
  let count = 0
  for (const i in n) {
    count = algorithm(n - 1)
  } 
  return count;
}
// 时间复杂度是O(N!)

// 一分为二，二分查找
const algorithm = (n) => {
  let count = 0
  let i = n
  while (i > 1) {
    i = i / 2
    count += 1
  }
  return count
}
// 时间复杂度是O(logN)

// 线性对数常出现在排序算法中，快速排序、归并排序、堆排序
const algorithm = (n) => {
  let count = 0
  let i = n
  while (i > 1) {
    i = i / 2
    for (const j in n) count += 1
  }
}
// 时间复杂度是O(NlogN)

空间复杂度的相关demo

const child = () => 0

const parent = (n) => {
  for (const i in n) child()
}
// 空间复杂度o(1),因为栈帧空间被释放掉了，每次掉用child()后

// 递归调用
const parent = (n) => {
  if (n <= 1) return 1
  return parent(n - 1) + 1
}
// 空间复杂度o(N),因为递归调用，会存在N个未返回的函数，累计使用O(N)大小的栈帧空间

// 最差运行点
const algorithm = (n) => {
  const num = 5                        // O(1)
  let nums = Array(10).fill(0)         // O(1)
  if (n > 10) nums = Array(n).fill(0)  // O(N)
}

时空权衡的demo

// 两数之和
// 方法一：暴力枚举
var twoSum = function(nums, target) {
  const len = nums.length;
  for (let i = 0; i < len - 1; i++) {
    for (let j = i + 1; j < len; j++) {
      if (nums[i] + nums[j] === target) {
        return [i, j]
      }
    }
  }
};
// 时间复杂度 O(N^2)，空间复杂度 O(1)；属于时间换空间，虽然仅使用常数大小的额外空间，但运行速度过慢。


// 方法二：辅助哈希表
const twoSum = function(nums, target) {
  const len = nums.length;

  // 使用哈希表存储当前值
  const map = new Map();
  for (let i = 0; i < len; i++) {
    map.set(nums[i], i);
  }

  for (let i = 0; i < len; i++) {
    const needNum = target - nums[i];

    if (map.has(needNum) && i !== map.get(needNum)) {
      return [i, map.get(needNum)]
    }
  }
}
// 时间复杂度 O(N)，空间复杂度 O(N)；属于「空间换时间」，借助辅助哈希表 dic，通过保存数组元素值与索引的映射来提升算法运行效率，是本题的最佳解法。

// 方法三：哈希优化
const twoSum = function(nums, target) {
  const len = nums.length;
  const map = new Map();

  for (let i = 0; i < len; i++) {
    const needNum = target - nums[i];

    if (map.has(needNum) && i !== map.get(needNum)) {
      return [i, map.get(needNum)];
    }

    // 边读边存
    map.set(nums[i], i);
  }
}