前端数据结构—相关基础概念

• 2021 年 3 月 14 日
• 筆記
• web 相关基础, 前端数据结构, 时间复杂度

前端要不要学习数据结构

　　作为一名IT技术人员，需要不断的完善自己的知识体系来提升自己，类似数据结构、网络等。在工作中大部分时间我们都是做应用层面的开发，有时候对数据结构、算法这些基本功要求不是很高，但是一些基本得知识点我们还是需要掌握。

到底什么是数据结构

　　是不是经常听别人说数据结构、算法、程序 = 数据结构 + 算法等，那么到底什么是数据结构？

　　数据结构本身是一个抽象的概念，没有具体的标准，比如我们用的电脑，我可以说电脑这种结构由cpu、主板、显卡、内存、硬盘、电源、声卡、网卡等组成。如 vue-cli 初始化的项目由 main.js、src等组成。所以不需要去纠结到底什么是数据结构，数据结构本身只是一层抽象的概念，从字眼上可以理解为数据与数据之间存在一种或多种关系的数据元素集合。

从不同的角度，数据结构可以理解为逻辑结构、物理结构。可以理解为逻辑结构是在计算机中的存储形式，物理结构是计算机怎么存储数据；

逻辑结构：数据元素之间的相互关系

• 集合结构  平等关系，在同一个集合中
• 线性结构  一对一关系
• 树形结构  一对多关系
• 图形结构   多对多关系

物理结构：数据的逻辑结构在计算机中的存储形式

• 顺序存储 类似连续的一个列表
• 链式存储 存在一个指针指向需要的元素

算法

　　解决问题的步骤我们叫方法，在计算机中称算法，在计算机中表现为指令的有限序列；通常一个问题有很多种方法，有些方法很巧妙，有些看起来比较绕，这些方法是有差异的，我们通常在计算机中通过时间复杂度、空间复杂度来衡量一个算法的好坏。

时间复杂度

　　时间复杂度并不是说代码执行的具体的时间，而是表示代码执行时间随问题规模或者数据规模增长的变化趋势，也叫渐进时间复杂度，简称为时间复杂度。我们都知道一个算法花费的时间与算法中语句的执行次数肯定成正比例，哪一个算法中语句执行次数多，它花费时间就多。

1 function get (n) {
2   let i = 0; // 一次
3   let name = '' // 一次
4 }
5 // 总共就是2次

如上所示，总共执行了2次，但是通常我们处理的事情这个n 可能不是一个固定值，所以我们把一个算法中的语句执行次数记为函数T(n)，n为问题规模，随着问题规模n的变化，算法执行的时间也会变化，为了更好的分析这个时间的变化比，用O()来表示时间复杂度的记法，我们称为大O记法。语句执行总的次数T(n)跟O() 有如下公式

　　T(n) = O(f(n))，它表示随着问题规模n 的增大，算法执行时间的增长率和f(n)的增长率相同，其中f(n)是问题规模n的某个函数

大O推导方法

我们一般通过以下方法来分析一个算法的时间复杂度

• 用常数1代替运行中的所有的加法常数
• 在修改后的运行次数函数中，只保留最高阶项
• 如果最高阶项存在且不为1，则去除与这个项相乘的常数（除法也是变相的相乘）

常数阶：O(1)

如果算法执行所需要的临时空间不随着某个变量n的大小而变化，即此算法空间复杂度为一个常量，可表示为O(1)

1 function run () {
2   let value = 100
3   value += 10 
4   console.log(value)
5   // 共执行3次,根据大O 推导法，把常数换成1,则结果是O(1)
6 }

线性阶：O(n)

1 function run (n) {
2     for(let i = 0; i < n; i++) {
3        console.log(i)
4   }
5 }
6 // 共执行n次，根据大O推导法，只取最高阶，所以是 O(n)

平方阶__O( n^2 )

function run (n) {
   for(let i = 0; i < n ; i++ )
    {
        for(let j = 0; j < n ; j++ )
        {
            console.log(j)
        }
    }
}
    /*
    外层i的循环执行一次，内层j的循环就要执行n次
    因为外层执行n次，那么总的就需要执行n*n次，
    也就是需要执行n^2次，根据大O推导法：O(n^2)

*/

 常见的复杂度

时间复杂度耗费时间从小到大依次排列

　　O(1) < O(logn) < O(n) < O(nlogn) < O(n²) < O(n³) < O(2ⁿ) < O(n!) < O(nⁿ)

练习

1 function run(n) {
2     for (let i = 0; i < n; i++) {
3         for (let j = i; j < n; j++) {
4             console.log(`${n}，hello word`)
5         }
6     }
7 }
8 run(10)

当 i = 0 时，内循环执行 n 次运算，当 i = 1 时，内循环执行 n – 1 次运算……当 i = n – 1 时，内循环执行 1 次运算。

所以，执行次数 T(n) = n + (n – 1) + (n – 2)……+ 1 = n(n + 1) / 2 = n^2 / 2 + n / 2。

根据上文说的 大O推导法 可以知道，此时时间复杂度为 O(n^2)。

空间复杂度

　　算法的空间复杂度通过计算算法所需的存储空间，公式记住 S(n) = O(f(n))，其中n 为问题规模，f(n)为关于n 所占存储空间的函数。

数据结构与算法的关系

数据结构和算法是相辅相成的，虽然可以单独分开为两个东西，但是对于计算机来说把他们分开，那么他们将变得十分无聊。

数据结构研究的是组织数据的方式，比如数组，他就是一种组织数据的方式，就是一种数据结构。但是有了数据结构，不一定有算法。数据结构是算法的基础，比如数据结构为数组，使用数组，可以写出冒泡、快排等算法。

数据结构为算法服务，算法作用在特定的数据结构之上。