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

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

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

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

算法复杂度

复杂度概念

书中介绍,算法复杂度旨在计算在输入数据量 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);
  }
}