计算机存储、组织数据的方式
- 程序 = 数据结构 + 算法
- 数据结构为算法提供服务,算法围绕数据结构
- 栈 队列 链表 (有序)
- 集合 字典 (无序)
- 树,堆,图 (有连接关系)
算法
- 链表: 遍历链表,删除链表节点
- 树、图:深度/广度优先遍历
- 数组:冒泡/选择/插入/归并/快速排序、 顺序/二分搜索
定性描述该算法的运行时间 O(1) O(n) O(logN)
n2 > n > log n > 1
// O(1) 时间复杂度为 O(1)
// 永远只执行一次
let i = 0
i+ =1
// O(n): 时间复杂度为 O(n)
for(let i =0; i< n; i++) {
console.log(i)
}
/*
* O(n) + O(1) = O(n)
* 如果两个时间复杂度先后排列,我们就把它们相加, 取增长趋势更快的那个
*/
let j = 0
j+ =1
for(let i =0; i< n; i++) {
console.log(i)
}
/*
* O(n) * O(n) = O(n2)
*/
for(let i =0; i< n; i++) {
for(let j =0; j < n; j++) {
console.log(i)
}
}
/**
* O(logN) 以2为底的logN
*/
let i =1;
while(i < n) {
console.log(i)
i = i * 2
}
也是用 O(n)表示
O(1) O(n) O(n2)
运算在运行过程中临时占用存储空间大小的量度
// O(1) 因为只声明了单个变量,单个变量所占用的内存永远为1
let i = 0;
i+ = 1
// O(n)
const list = []
for(let i = 0; i< n; i++) {
list.push(i)
}
// O(n2)
const matrix = []
for(let i =0; i<n;n++) {
matrix.push([])
for(let j = 0; j < n; j++) {
matrix[i].push(j)
}
}
后进先出的数据结构
应用场景
- 十进制转二进制,
- 判断字符串中的括号是否有效
- 函数调用堆栈 (最后调用的函数,最先执行完)
先进先出的数据结构
const queue = []
// 入队
queue.push(1)
queue.push(2)
// 出队
queue.shift()
queue.shift()
使用场景 (先进先出,保证有序)
- 食堂排队打饭
- JS 异步中的任务队列
- 计算最近请求次数
JS 是单线程,无法同时处理异步中的并发任务,使用任务队列先后处理异步任务
多个元素组成的列表
元素的存储不连续,用next指针连在一起
链表与数组的差别
- 数组增删非首尾元素,往往需要移动元素
- 增删非首尾元素,不需要移动元素,只需要更改 next 指针即可
无序且唯一的数据结构
ES6 中有集合,名为 Set
集合的常用操作:去重,判断某元素是否在集合中,求交集
/*
* 使用Set对象, new add delete has size
*迭代Set: 多种迭代方法,Set与Array互转,求交集
*/
与集合类似,字典也是存储唯一值的数据结构,但它是以键值对的形式来存储
(用来做映射关系)
ES6 中名为 Map
常用操作: 增删改查
一种分层数据的抽象模型
DOM 树,级联选择,树形控件
const a = {
value: 'a',
label: 'b',
children: [
{
value: 'a',
label: 'b',
children: [
{
value: 'a',
label: 'b',
children: []
}
]
}
]
}
树的常用操作:
- 深度/广度优先遍历
- 先中后序遍历(二叉树)
尽可能深的搜索树的分支
尽可能广的搜索树的分支
|-a |---b |---|---d |---|---e |---c |---|---f |---|---g
深度优先遍历 a -> b -> d -> e -> c -> f -> g 广度优先遍历 a -> b -> c -> d -> e -> f -> g
深度优先遍历算法 (递归)
- 访问根节点
- 对根节点的 children 挨个进行深度优先遍历
广度优先遍历
- 新建一个队列,把根节点入队
- 把队头出队访问
- 把队头的 children 挨个入队
- 重复 2,3 步骤,直到队列为空
树中每个节点最多只能有两个子节点
const tree = {
val: 1,
left: {
val: 2,
left: null,
right: null
},
right: {
val: 3,
left: null,
right: null
}
}
先序遍历算法
- 访问
根
节点 - 对根节点的
左
子树进行先序遍历 - 对根节点的
右
子树进行先序遍历
中序遍历算法
- 对根节点的
左
子树进行中序遍历 - 访问
根
节点 - 对根节点的
右
子树进行中序遍历
看到 8-4
图是网络结构的抽象模型,是一组由边连接的节点
图可以表示任何二元关系,比如道路,航班
JS 中没有图,但是可以用 Object 和 Array 构建图。 图的表示法:邻接矩阵,邻接表,关联矩阵...
常用操作
- 深度优先遍历 (尽可能深的搜索)
- 访问根节点
- 对根节点的
没访问过的(避免死循环)
相邻节点进行深度优先遍历
- 广度优先遍历
- 新建一个队列,把根节点入队
- 把队头出队并访问
- 把队头的没
访问过的相邻节点入队
堆是一种特殊的完全二叉树
每层节点都完全填满, 若最后一层没完全填满,只缺少右边的若干节点
所有的节点都大于
等于子节点(最大堆)
所有的节点都小于
等于子节点(最小堆)
JS 中通常使用数组表示堆
1
|--3
|--|--
|--6
任意节点的左子节点 2 _ index + 1 任意节点的右子节点 2 _ index + 2
任意节点的父节点 (index - 1) / 2 (Math.floor)
- 快速的找出最大值和最小值, 时间复杂度 O(1)
- 找出第 K 个最大(小)元素