JavaScript数据结构与算法--简介和时间/空间复杂度计算_空间复杂度怎么算js

数据结构与算法是什么？

1. 数据结构：计算机存储、组织数据的方式，就像锅碗瓢盆。
2. 算法：一系列解决问题的清晰指令，就像食谱。

数据结构与算法的关系：

程序 = 数据结构 + 算法。

数据结构为算法提供服务，算法围绕数据结构操作。

将要学习的数据结构：

1. 栈、队列、链表 （三者：有序的、连成一串的数据结构，就像羊肉串的竹签一样，把肉串起来，有先后顺序。）
2. 集合、字典。（无序的，就像碗，把食物放进去，无序）
3. 树、堆、图。（里面的元素都有一定的连接关系，类似生活中{组织架构、书籍目录—树形结构}、{道路、航班、朋友圈—图形结构}、{特殊的树—堆结构(帮助我们排序)}等等）

将要学习的算法：

1. 链表：遍历链表、删除链表节点。
2. 树、图：深度/广度优先遍历。
3. 数组：冒泡/选择/插入/归并/快速排序、顺序/二分搜索。

时间复杂度是什么？

1. 一个函数，用大O表示，比如O(1),O(n),O(logN)
2. 定性描述该算法的运行时间

重点关注的时间复杂度：1<log2n<n<n^2

O(1)：
两行代码？因为这两行代码永远只会被执行一次，所有它的时间复杂度就是O(1)。

O(n):
for循环n次，每次循环时，打印当前i的变量，i变量每次递增1，从0开始增，直到n-1为止，这样的三行代码时间复杂度为O(n)。为什么？因为for循环中间里面的代码，执行了n次，随着n增大，它也会随着增大，所以这样的代码为O(n)的时间复杂度代码。

O(1)+O(n)=O(n):
计算时间复杂度，如果两个时间复杂度先后排列，就相加，而且结果取增长趋势更快的时间复杂度。O(1),O(n)—取O(n),当n足够大，1可以忽略不计。 相加—忽略增长趋势较小的时间复杂度，取增长趋势较大的时间复杂度。

O(n) * O(n)=O(n^2):
for循环嵌套，将两者时间复杂度相乘—按照正常的乘法来计算 n * n=n^2。

O(logN):
这里的logN就是以2为底的logN。 log函数就是用来求2的多少次方为N。

空间复杂度是什么？

1. 一个函数，用大O表示，比如O(1),O(n),O(n^2)……
2. 算法在运行过程中临时占用存储空间大小的量度（简单说，就是你写的代码占的内存多不多，代码占用的存储空间越小，越好）。

O(1):
为什么这两行代码时间复杂度为O(1)? 因为只申明了单个变量，单个变量占用的内存永远是1个内存单元，永远是恒定的内存。

O(n):
为什么？因为申明了list数组，给数组里面添加了n个值，相当于占用了n个内存单员，所以说这段代码的空间复杂度为O(n)。

O(n^2):
其实就是一个矩阵（说白了就是行列/栅栏），为什么矩阵就是n^2，因为矩阵的本质就是一个二维数组（嵌套了两层的数组，存储了n的二次方个变量）。