数据结构与算法-总结

《学习JavaScript数据结构与算法(第3版)》

数组

内存中的一段连续地址。

对象中的属性，是一段不连续的地址。对象属性插入或删除不需要移动其他元素。

要存储多个元素，数组（或列表）可能是最常用的数据结构。虽然存取方便，然而，这种数据结构有一个缺点：（在大多数语言中）数组的大小是固定的，从数组的起点或中间插入或移除项的成本很高，因为需要移动元素。

队列

当我们在浏览器中打开新标签时，就会创建一个任务队列。这是因为每个标签都是单线程处理所有的任务，称为事件循环。浏览器要负责多个任务，如渲染HTML、执行JavaScript代码、处理用户交互（用户输入、鼠标点击等）、执行和处理异步请求。

字典

JavaScript语言内部就是使用散列表来表示每个对象。

最短路径算法

Dijkstra算法解决了单源最短路径问题。

Bellman-Ford算法解决了边权值为负的单源最短路径问题。

A*搜索算法解决了求仅一对顶点间的最短路径问题，用经验法则来加速搜索过程。

Floyd-Warshall 算法解决了求所有顶点对之间的最短路径这一问题。

复杂度

时间复杂度

计算时间复杂度依据 - 主定理

面试中常考的时间复杂度：

二叉树遍历 - O(n) - 每个节点访问一次且仅有一次。

空间复杂度

• 数组的长度
• 递归的深度

总结

1. 线性表、树等数据结构，记录在结构中的相对位置是随机的，和记录的关键字之间不存在确定的关系，因此，在结构中查找记录时需进行一系列和关键字的比较。这类查找方法建立在“比较”的基础上。查找的效率依赖于查找过程中所进行的比较次数。
2. 可以使用位运算加快运算操作。