【技能进阶4】关于算法，你需要掌握的数据结构图文手册

嵌入式看一半就够了~

大 O 表示法 — 时间复杂度

为什么大 O 复杂度很重要？

对于小规模数据集，算法的复杂度可能不会显著影响性能，但随着数据规模的增加，算法的性能差异就变得至关重要。算法的复杂度直接影响到程序的响应时间和执行效率。因此，掌握时间复杂度对于编写高效程序是每个开发者必备的技能。

例如，假设数据集包含 100 万个元素：

• O(1) 算法：执行 1 次操作。
• O(log(n)) 算法：执行约 20 次操作。
• O(n) 算法：执行 100 万次操作。
• O(n * log(n)) 算法：执行约 2000 万次操作。
• O(n²) 算法：执行 1 万亿次操作。

从这个简单的例子可以看出，算法复杂度在大规模数据处理中起着至关重要的作用。

RUM 权衡

选择合适的数据结构时，我们需要平衡三个方面的性能：

• 读取效率 (R)：从数据结构中检索或访问数据的速度。
• 更新效率 (U)：在数据结构中插入、删除或修改数据的速度。
• 内存效率 (M)：数据结构使用的内存空间。

这些因素之间通常存在一定的权衡，选择适合的结构是设计高效系统的关键。

常见且重要的数据结构

数组与链表

• 数组：数组在内存中连续存储，支持快速查找（O(1)），但插入和删除操作较慢（O(n)）。
• 链表：链表通过指针链接元素，支持快速插入和删除（O(1)），但查找操作较慢（O(n)）。

队列

队列是一种遵循“先进先出”（FIFO）原则的线性数据结构，适用于需要顺序处理任务的场景，如任务调度和消息队列。

堆栈

堆栈遵循“后进先出”（LIFO）原则，适用于需要跟踪任务顺序的场景，比如函数调用栈或撤销操作。

哈希表

哈希表提供常数时间（O(1)）的元素访问，通过哈希函数将键映射到数组索引，实现高效的查找、插入和删除。其缺点是较高的内存消耗。

树形数据结构

树形结构常用于组织层次化数据，广泛应用于数据库、文件系统和图形用户界面等领域。理解树结构的核心算法（如二分查找）对于掌握后续数据结构至关重要。

二分查找

二分查找是一种高效的排序数组查找算法。它通过每次将搜索空间缩小一半来寻找目标元素。时间复杂度为 O(log(n))，大大提高了查找效率。

二叉搜索树（BST）

二叉搜索树是一棵二叉树，其中每个节点的左子树的值小于父节点，右子树的值大于父节点。平衡的二叉搜索树可以实现 O(log(n)) 的查找、插入和删除操作。

红黑树

红黑树是一种自平衡的二叉搜索树，通过对每个节点赋予颜色（红色或黑色）并遵循一定的平衡规则，保证树的高度不会过高，从而维持高效的操作性能。

AVL 树

AVL 树的全称是 Adelson-Velsky and Landis Tree，以其发明者 G. M. Adelson-Velsky 和 E. M. Landis 的名字命名。

AVL 树是一种自平衡的二叉搜索树，它通过限制左右子树的高度差不超过 1 来保持平衡。在插入和删除节点时，AVL 树会通过旋转操作进行自动平衡。

堆

堆是一种特殊的完全二叉树，分为最大堆和最小堆。最大堆中每个父节点的值大于或等于其子节点的值，最小堆则相反。堆常用于实现优先队列，能够高效地获取最小值或最大值。

跳表

跳表是链表的一种扩展，通过多个层次的链表加速查找、插入和删除操作。其效率接近平衡树，但实现起来更为简单，适用于对效率要求较高的应用场景。

B+ 树

B+ 树是一种广泛应用于数据库存储的平衡树结构，它将所有的数据存储在叶子节点，并通过有序的链表连接叶子节点，支持高效的顺序遍历。

二叉索引树/斐波那契树

这种树结构主要用于处理动态频率表或区间查询，能够高效地支持前缀和查询。通过位移操作，更新和查询操作的时间复杂度为 O(log(n))。

图数据结构

邻接表与邻接矩阵

• 邻接表：将图的每个节点与其邻接节点通过列表存储，适用于稀疏图。

• 邻接矩阵：使用一个二维矩阵来表示节点之间的连接关系，适用于稠密图。

字符串搜索数据结构

Trie（字典树）

Trie 是一种高效的字符串搜索数据结构，特别适用于前缀查询和单词自动补全等应用。每个节点代表一个字符，能够快速查找字符串的前缀（我觉得这张图好好看，像葡萄藤）。

Radix Tree

Radix 树是一个紧凑的 Trie，通过合并公共前缀节点来减少空间消耗，适合用于处理大量字符串数据。

Splay Tree

伸展树是一种自调整的二叉搜索树，每次访问节点后，它会自动将该节点移到树的根部，从而加快对频繁访问节点的查询效率。

Quadtree

四叉树是一种空间数据结构，通常用于二维空间的区域分割，如碰撞检测或图形处理。每个节点将空间分割为四个子区域。

KD Tree

KD 树是一种针对 k 维空间的二叉树，通过在每一层交替选择维度来划分空间，适用于高效的范围查询和最近邻搜索。

R-Tree

R 树是一种用于多维空间数据的树形结构，广泛应用于地理信息系统（GIS）中，通过最小边界矩形（MBR）组织空间数据。

其他数据结构及图

布隆过滤器

布隆过滤器是一种空间高效的概率数据结构，常用于测试一个元素是否属于某个集合。虽然可能出现假阳性（即报告元素存在但实际上不存在），但绝不会产生假阴性。

二叉堆

二叉堆是一种高效的优先队列实现，支持快速的插入、删除和最小值提取，常用于调度算法和实时系统。二叉堆由一系列二叉树组成，这些树是相互链接的特殊树

每个堆中的二叉树都遵循最小堆属性：节点的键值大于或等于其父节点的键值。此外，每个顺序只能有一个或零个二叉树，包括零阶。

以下示例二叉堆包含 13 个节点：

Hash Array Mapped Trie (HAMT)

HAMT 是一种结合了哈希表和 Trie 树优点的数据结构，能够高效地存储和检索键值对，常用于实现高效的字典结构。

Merkle Tree

Merkle 树是一种用于验证数据完整性的树形结构，它通过将数据组织成哈希值，并不断向上传递，广泛应用于区块链和分布式系统中，确保数据的一致性和完整性。

最后：8 个数据库中常用的数据结构