- Published on
数据结构 | 基础知识汇总 五月小结
- Authors
- Name
- Jiaqi Wang(Ramis)
[ 最后更新 于 2024-05-26 ]
五月接近尾声，数据结构的学习目前告一段落了。 在此做一个小结方便回顾以及将来的拓展学习。
数据结构小结
| 数据结构 | 核心操作及时间复杂度 | 优势 | 缺点 | 应用 | 延伸 |
|---|---|---|---|---|---|
| 栈 Stack | -先进先出，进栈（插入）/出栈（删除）时间复杂度为O(1) | 访问栈顶元素快速方便，适用于需要逆序处理数据 | 访问非栈顶元素不便 | 表达式求值，深度优先搜索 | 最小栈 155. Min Stack |
| 队 Queue | -先进后出，进队（插入）/出队（删除）时间复杂度O(1) | 方便按顺序处理数据 | 访问队列中非队头/队尾元素不方便。 | 广度优先搜索 | -优先队列（结合其他数据结构维护实现）-双端队列（Deque） |
| 堆 Heap | -最大值/最小值取用O（1） -删除 以及插入为O(log n) | 可以快速调取最大最小值，是实现优先队列的方法之一 | 不适合需要快速访问中间元素的场景 | Dijkstra算法优化 | 二项堆、斐波那契堆 |
| 二叉搜索树 BST | -有序存储数据-插入、删除、查找的平均时间复杂度为O(log n) | 可以实现有序遍历 | 最坏情况下会退化为链表，需要平衡来不断维持结构的高效 | 数据按区间快速查询 | 平衡树、B树 |
| 哈希表 Hash Table | - 平均情况下插入、删除、查找操作的时间复杂度为O(1)。 | 空间换时间实现快速数据的快速访问查询 | 消耗额外的空间 、需要解决哈希冲突 | 数据库快速查找、缓存 | 双哈希表 |
| 布隆过滤器 Bloom Filter | 插入和查询操作的时间复杂度为O(k)，其中k是哈希函数的个数 | 适用于大规模数据集合 | 可能存在假阳性（不存在的元素却返回为存在）不能返回具体元素，只能判断元素是否存在 | IP地址黑名单 | 跳表（Skip List）字典树（Trie） |
下一阶段（6月-7月）要开始学一些Machine Learning的内容了。 希望自己保持热情。
-鹅仔 2024/05/26 20：19