前端需要知道的算法的时间、空间复杂度
研究复杂度的根本目的是为了降低复杂度,在时间复杂度和空间复杂度之间权衡出一个最佳解决方案。
1. 时间复杂是什么
一个函数用大 O 表示,比如 O(1),O(n)、O(logN)
定性描述该算法的运行时间
时间复杂度的图
1 < log2n < √n < n < nlog2n < n2 < 2n < n! 复制代码
O(1)
O(1)无循环 只会执行一次
let i = 0; i +=1 复制代码
O(n)
循环执行了n次
for (let i = 0; i < n; i += 1) { console.log(i) } 复制代码
O(1) + O(n) = O(n)
O(n) 足够大时,O(1) 忽略不计
let i = 0; i +=1 for (let i = 0; i < n; i += 1) { console.log(i) } 复制代码
O(n) * O(n) = O(n^2)
相同之间相乘
for (let i = 0; i < n; i += 1) { for (let j = 0; j < n; j += 1) { console.log(i, j) } } 复制代码
O(logN)
logN 以2为底的 求2的多少次方位N
不断求 2的一次方 2的2次 知道结果 大于等于n while 循环中的代码执行多少次 logn次
let i = 1; while (i < n) { console.log(i) i * 2; } 复制代码
空间复杂度
一个函数用大 O 表示,比如 O(1),O(n)、O(logN)
算法在运行过程中临时占用储存空间大小的量度
O(1)
每一个基础类型的值为一个空间计算单元
let i = 0; i +=1 复制代码
O(n)
因为数组中占用了 n 个空间
const list = [] for(let i = 0; i< n; i++){ list.push(i) } 复制代码
O(n^2)
因为矩阵存储了多维的值 矩阵的本质就是一个二维数组
const matrix = [] for(let i = 0; i < n; i++){ matrix.push([]) for(let j = 0; j < n; j++){ matrix[i].push(j) } } 复制代码
思考题
1、如果一段代码中有 3 个循环,它们的循环次数都是 n,那么这段代码的时间复杂度是 O (3n) 还是 O (n)?
如果三个循环是并列代码块,时间复杂度是 O(n)
如果三个循环是嵌套代码块,时间复杂度是O(n^3)
如果三个循环只有两个嵌套,时间复杂度是O(n^2) + O(n) = O(n^2)
2、假设每天睡觉前,你都会数 2 的次方,1、2、4、8……,每次你都数到 n 才睡着,那么你数了几个数?时间复杂度是多少?
一共数了 (log n) + 1 个数
时间复杂度是O(log n)
常见数据结构操作的时间、空间复杂度
上图原文链接: 来自[野风大佬]: https://zhuanlan.zhihu.com/p/143358017
欢迎大家在评论区交流·~~
作者:远山和叶
链接:https://juejin.cn/post/7018536118442262558