问小白 wenxiaobai
资讯
历史
科技
环境与自然
成长
游戏
财经
文学与艺术
美食
健康
家居
文化
情感
汽车
三农
军事
旅行
运动
教育
生活
星座命理

常见数据结构时间复杂度比较表及图的存储方式

创作时间:
作者:
@小白创作中心

常见数据结构时间复杂度比较表及图的存储方式

引用
CSDN
1.
https://m.blog.csdn.net/weidl001/article/details/144222476

**本文总结了常见数据结构的时间复杂度，并附带了一些关于图的存储方式的额外知识点。内容主要包括以下几个部分：

  1. 常见数据结构（单链表、双链表、循环链表、栈、队列、数组、哈希表、二叉搜索树、堆）的时间复杂度表格
  2. 如何选择数据结构的说明
  3. 图的存储方式（邻接矩阵和邻接表）的比较**

常见数据结构时间复杂度比较表

数据结构
操作
平均时间复杂度
最坏时间复杂度
说明
单链表
查找（搜索）
O(n)
O(n)
需要从头遍历到目标位置。
插入头部
O(1)
O(1)
常数时间插入新节点，修改头指针。
插入尾部
O(n)
O(n)
需要遍历到尾节点，除非有尾指针。
插入任意位置
O(n)
O(n)
需要遍历到指定位置。
删除头部
O(1)
O(1)
修改头指针即可。
删除尾部
O(n)
O(n)
需要找到尾节点的前驱节点。
删除任意节点
O(n)
O(n)
需要找到目标节点的位置。
遍历
O(n)
O(n)
遍历整个链表的所有节点。
双链表
查找（搜索）
O(n)
O(n)
与单链表相同。
插入头部
O(1)
O(1)
常数时间修改头指针和新节点的prev指针。
插入尾部
O(1)
O(1)
通过尾指针直接访问，常数时间完成。
插入任意位置
O(n)
O(n)
需要遍历到指定位置。
删除头部
O(1)
O(1)
修改头指针和新头节点的prev指针即可。
删除尾部
O(1)
O(1)
修改尾指针和前驱节点的next指针。
删除任意节点
O(n)
O(n)
需要找到目标节点。
遍历
O(n)
O(n)
遍历整个链表的所有节点。
循环链表
查找（搜索）
O(n)
O(n)
与单链表相同。
插入头部
O(n)
O(n)
需要找到尾节点以更新其next指针。
插入尾部
O(n)
O(n)
需要遍历到尾节点，除非维护尾指针。
删除头部
O(n)
O(n)
需要找到尾节点以更新其next指针。
删除尾部
O(n)
O(n)
需要找到尾节点和其前驱节点。
遍历
O(n)
O(n)
遍历整个循环链表，直到回到头节点。
栈（链表实现）
入栈（Push）
O(1)
O(1)
常数时间在头部插入节点。
出栈（Pop）
O(1)
O(1)
常数时间删除头部节点。
获取栈顶（Peek）
O(1)
O(1)
常数时间访问头部节点。
判断是否为空
O(1)
O(1)
判断头指针是否为NULL。
队列（链表实现）
入队（Enqueue）
O(1)
O(1)
常数时间在尾部插入节点。
出队（Dequeue）
O(1)
O(1)
常数时间删除头部节点。
获取队头（Front）
O(1)
O(1)
常数时间访问头部节点。
判断是否为空
O(1)
O(1)
判断头指针是否为NULL。
数组
查找（按索引）
O(1)
O(1)
常数时间直接访问目标索引。
插入（随机位置）
O(n)
O(n)
插入位置后的所有元素需要移动。
删除（随机位置）
O(n)
O(n)
删除位置后的所有元素需要移动。
遍历
O(n)
O(n)
遍历整个数组。
哈希表
查找
O(1)
O(n)
平均情况O(1)，最坏情况哈希冲突导致线性查找。
插入
O(1)
O(n)
平均情况O(1)，最坏情况哈希冲突导致线性查找。
删除
O(1)
O(n)
平均情况O(1)，最坏情况哈希冲突导致线性查找。
二叉搜索树
查找
O(log n)
O(n)
平衡树的平均时间复杂度为O(log n)，退化为链表时最坏O(n)。
插入
O(log n)
O(n)
平衡树的平均时间复杂度为O(log n)，退化为链表时最坏O(n)。
删除
O(log n)
O(n)
平衡树的平均时间复杂度为O(log n)，退化为链表时最坏O(n)。
遍历
O(n)
O(n)
访问所有节点的总时间。
堆（优先队列）
插入
O(log n)
O(log n)
维护堆的结构需要对数时间。
删除最大/最小值
O(log n)
O(log n)
删除根节点并调整堆结构需要对数时间。
获取最大/最小值
O(1)
O(1)
直接访问根节点。

如何选择数据结构

  1. 链表：适用于需要动态插入、删除的场景，但查找速度较慢。
  2. 数组：适用于需要快速访问（随机访问）的场景，但插入和删除效率低。
  3. 栈与队列：专注于特定操作（LIFO/FIFO），高效且易于实现。
  4. 哈希表：适用于需要快速查找和插入的场景，但可能需要处理冲突。
  5. 二叉搜索树：适用于需要排序的动态集合，但需要注意树的平衡性。
  6. 堆：适用于需要高效获取最大值或最小值的优先级队列场景。

时间复杂度决定了效率

  • 对于大规模数据，优先选择具有对数时间复杂度或更优性能的数据结构。
  • 在特定情况下（如数据较小或操作较少），简单的实现可能更具优势。

结合操作特点优化

  • 例如，在频繁插入尾部的链表中，可以通过维护尾指针将时间复杂度从O(n)优化为O(1)。

图的存储方式

邻接矩阵

  • 使用一个 n×nn \times nn×n 的二维数组存储图的信息。
  • 如果顶点 iii 和顶点 jjj 有边，则 matrix[i][j]=1\text{matrix}[i][j] = 1matrix[i][j]=1（或权重值）；否则为 0。
  • 空间复杂度固定为 O(n2)O(n^2)O(n2)。

邻接表

  • 每个顶点维护一个链表，链表中存储与该顶点相连的所有边。
  • 空间复杂度为 O(n+e)O(n + e)O(n+e)，其中 eee 是边的数量。

适用场景

  • 稠密图：边的数量 eee 接近 n2n^2n2，邻接表的空间复杂度接近 O(n+n2)O(n + n^2)O(n+n2)，且复杂的链表结构本身会增加存储开销。相比之下，邻接矩阵的固定空间复杂度 O(n2)O(n^2)O(n2) 更适合存储稠密图，因为不需要额外维护链表结构。
  • 稀疏图：边数 eee 远小于 n2n^2n2，邻接表的空间复杂度 O(n+e)O(n + e)O(n+e) 比邻接矩阵 O(n2)O(n^2)O(n2) 更小，适合稀疏图。

存储方式比较

存储方式
适用场景
空间复杂度
优点
缺点
邻接矩阵
稠密图
O(n2)
简单直观，适合快速查询两点是否相连
对稀疏图浪费大量空间
邻接表
稀疏图
O(n+e)
节省空间，特别是稀疏图
查询任意两点是否相连时效率较低

热门推荐
© 2023 北京元石科技有限公司 ◎ 京公网安备 11010802042949号