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

书名是《图解算法数据结构》,在力扣看到的,准备开始系统学习一下算法了。会用前端的语言和思维来学习学习~希望能获得一些见解。第一篇是关于算法复杂度的学习笔记记录。
算法复杂度
复杂度概念
书中介绍,算法复杂度旨在计算在输入数据量 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);
}
}