您现在的位置:首页 > 博客 > 互联网 > 正文
前端进阶算法1:如何分析、统计算法的执行效率和资源消耗?
http://www.yunkuaipai.cn/      2021-7-7 20:36:38      来源:小木鱼云快排      点击:

前端还要学算法?必须学,而且必须狠狠地学。现在去大厂面试,数据结构与算法已经是标配,要是不会的话,那基本与大厂无缘了。

作为一名前端,虽然在平常开发中很少写算法,但当我们需要深入前端框架、开发语言、开源库时,懂算法将大大提高我们看源码的能力。例如 react 的 diff 算法、webpack 中利用 tree-shaking 优化、v8 中的调用栈、消息队列等,这些就大量使用了算法,看懂了就能更好的了解它们的性能,更高效的解决问题,进阶到更高 Level,赚更多钱。

现在市面上的算法资料很多,但针对前端的算法资料少之又少,所以,这里我整理了一份适用于前端的数据结构与算法系列,希望能帮助你从0到1构建完整的数据结构与算法体系。

本系列预估一共有40多篇,本篇是第一篇。想要更多更快的学习本系列,可以关注公众号「前端瓶子君」和我的「Github(点击查看)」

一、为什么引入复杂度分析

我们知道,好的数据结构与算法能够大大缩短代码的执行时间与存储空间,那么我们如何去衡量它喃?本节就主要介绍算法性能的衡量指标—复杂度分析。

判断一段代码执行的效率最简单最直观的方式就是把它放在机器上执行一遍,自然就会得到算法的执行时间与占用内存大小。那么为什么还要引入复杂度分析喃?

这主要是因为,通过机器上运行代码来统计算法的性能,有很大的局限性,它容易受测试环境、数据规模影响:

  • 统计结果易受测试环境影响:不同系统、处理器的机器测试结果可能出现很大的不同
  • 统计结果易受数据本身、数据规模影响:不同的数据、不同长度的数据都可能对测试结果产生巨大的影响

而这些都不是我们想要看到的。我们需要的是不受外在因素影响的、大致的估计算法执行效率的方法。这就是使用复杂度分析的原因。

二、如何表示复杂度

如何表示算法复杂度,具体来讲就是代码执行的时间、执行消耗的存储空间。例如:

function cal(n) { 
    let sum = 0; // 1 unit_time 
    let i = 0; // 1 unit_time 
    for(; i <= n; i++) { // n unit_time 
        sum += i; // n unit_time 
    } 
    return sum
}

从 CPU 的角度看,每段代码不过是读写数据或操作数据,尽管每次操作 CPU 执行的个数、执行的时间都不同,但我们粗咯把每次执行的时间都一致,称为 unit_time 。

所以上述代码总共执行 (2n+2)*unit_time 时间,即:T(n)=(2n+2)*unit_time ,所以,我们可以写成:

T(n) = O(f(n))

其中:

  • n:表示数据规模的大小
  • f(n):表示每行代码执行的次数总和
  • O:表示代码的执行时间 T(n) 与 f(n) 表达式成正比

当 n 很大时,例如 10000,甚至更大,T(n) = O(f(n)) 可以表示为 T(n) = O(n) 。

这就是大 O 时间复杂度表示法大 O 时间复杂度实际上并不具体表示代码真正的执行时间,而是表示代码执行时间随数据规模增长的变化趋势,所以,也叫作渐进时间复杂度(asymptotic time complexity),简称时间复杂度。阿

发表评论(0)
姓名 *
评论内容 *
验证码 *图片看不清?点击重新得到验证码