Vue学习笔记

# 算法复杂度

  • 算法的复杂度分为时间复杂度和空间复杂度
    • 作用：计算机资源最重要的就是时间和空间（寄存器资源）；时间复杂度是指执行算法所需要的计算工作量；而空间复杂度是指执行这个算法时计算机所需资源的多少，因此复杂度分为时间复杂度和空间复杂度；简单来说，时间复杂度指的是语句执行次数，空间复杂度指的是算法所占的存储空间。

# 1.时间复杂度

  • 计算时间复杂度的方法：
    • 1.用常数 1 代替运行时间中的所有加法常数
    • 2.修改后的运行次数函数中，只保留最高阶项
    • 3.去除最高阶项的系数

  • 按数量级递增排列，常见的时间复杂度有：

    • O(1): Constant Complexity: Constant 常数复杂度
    • O(log n): Logarithmic Complexity: 对数复杂度
    • O(n): Linear Complexity: 线性时间复杂度
    • O(n^2): N square Complexity 平⽅方
    • O(n^3): N square Complexity ⽴立⽅方
    • O(2^n): Exponential Growth 指数
    • O(n!): Factorial 阶乘

  • 随着问题规模 n 的不断增大，上述时间复杂度不断增大，算法的执行效率越低

  • eg：时间复杂度 O(1)

sum = n*(n+1)/2;
1
  • eg:时间复杂度 O(n)
for(let i = 0;i< n;i++){
    console.log(i)
}
1
2
3
  • eg:时间复杂度 O(n^2)
for(let i =0;i<n;i++){
    for(let j=i;j<n;j++){
        console.log(i,j)
    }
}
//运行次数为(1+n)*n/2-->n^2(只保留高阶项，去掉高阶项系数)
1
2
3
4
5
6

最坏时间复杂度和平均时间复杂度

  • 最坏情况下时间复杂度
  • 平均时间复杂度是指可能输入实列均以等概率的情况下，算法的期望运行时间

常用排序算法的时间复杂度

算法 最差时间复杂度 平均时间复杂度 稳定性 空间复杂度
冒泡排序 O(n2) O(n2) 稳定 O(1)
快速排序 O(n2) O(n*log2n) 不稳定 O(log2n)~O(n)
选择排序 O(n2) O(n2) 稳定 O(1)
二叉树排序 O(n2) O(n*log2n) 不稳定 O(1)
插入排序 O(n2) O(n2) 稳定 O(1)
堆排序 O(n*log2n) O(n*log2n) 不稳定 O(1)
希尔排序 O O 不稳定 O(1)

# 2.空间复杂度

  • 空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度，记做 S(n)=O(f(n))
  • 对于一个算法来说，空间复杂度和时间复杂度往往是相互影响的。当追求一个较好的时间复杂度时，可能会使空间复杂度的性能变差，即可能导致占用较多的存储空间，反之，当追求一个较好的空间复杂度时，可能会使时间复杂度的性能变差，即可能导致占用较长的运行时间。
  • 有时我们可以用空间来换取时间达到目的。

# 3.前端算法场景

  • rollup 使用 tree-shaking 算法，检测用不到的代码，减小包的大小
  • 树（DOM-DIFF）算法
  • 队列和调度算法（React Fiber）
  • 图论（Webpack split chunk plugin 的计算）
  • 图形算法：svg 和 canvas 绘图底层的算法，衍生出 d3.js,highcharts,echarts,canvas.js 等等一些图标库；以及构成 html 中渲染的基础；
  • 数据可视化算法
  • 3D 相关算法
    • normanvr:用 vr 控制 web3d 动画
    • three.js 控制的地球 3d 模型

← 栈和队列 →