目录
顺序表
链表
二叉树
图（V是顶点个数，E是边的条数）
1.存储空间：
2.BFS和DFS的时间复杂度
3.最小生成树时间复杂度
4.最短路径时间复杂度
查找的平均查找长度（ASL）
排序
顺序表
| 算法操作 | 时间复杂度 | 空间复杂度 | 描述 |
| 插入 | O（n） | \ | 需要移动元素，移动结点的平均次数n/2 |
| 删除 | O（n） | \ | 需要移动元素，移动结点的平均次数(n-1)/2 |
| 按值查找 | O（n） | \ | 指针移动查找对应元素 |
链表
| 算法操作 | 时间复杂度 | 空间复杂度 | 描述 |
| 头插法创建 | O（n） | \ | 插入时间为O(1)，总时间复杂度为O(n) |
| 尾插法创建 | O（n） | \ | 插入时间为O(1)，总时间复杂度为O(n) |
| 按值查找 | O（n） | \ | 指针移动查找对应元素 |
| 按序查找 | O（n） | \ | 指针移动到对应位置 |
| 插入 | O（1） | \ | 需要从头查找则花费主要用于查找O(n) |
| 删除 | O（1） | \ | 需要从头查找则花费主要用于查找O(n) |
二叉树
| 算法操作 | 时间复杂度 | 空间复杂度 | 描述 |
| 二叉树创建 | O（n） | O（n） | 类似先序遍历 |
| 二叉树遍历 | O（n） | O（n） | 递归遍历操作 |
| 二叉排序树插入 | O（n） | \ | \ |
| 二叉排序树删除 | O（n） | \ | \ |
图（V是顶点个数，E是边的条数）
1.存储空间：
| 存储结构 | 存储空间 |
| 邻接矩阵 | O(n^2) |
| 邻接表 | 无向图O(|V|+2|E|)，有向图O(|V|+|E|) |
2.BFS和DFS的时间复杂度
| 广度优先遍历BFS | 深度优先遍历DFS | |
| 邻接矩阵存储 | O(|V|^2) | O(|V|^2) |
| 邻接表存储 | O(|V|+|E|) | O(|V|+|E|) |
3.最小生成树时间复杂度
| 普里姆算法 | 克鲁斯卡尔算法 | |
| 时间复杂度 | O(|V|^2) | O(|E|log|E|) |
注：普利姆算法不依赖E，适合求解边稠密图的最小生成树；克鲁斯卡尔适合边稀疏而顶点较多的图
4.最短路径时间复杂度
| 迪杰斯特拉算法 | 弗洛伊德算法 | |
| 时间复杂度 | O(|V|^2) | O(|V|^3) |
5.拓扑排序：由于输出每个顶点的同时还要删除以它为起点的边，故拓扑排序的时间复杂度为O(|V|+|E|)
查找的平均查找长度（ASL）
1.顺序查找
注：若题目未明确提出是成功还是不成功的ASL，则平均查找长度是成功和不成功的平均值：
ASL平均 =（ASL成功+ASL不成功）/2
2.有序的顺序查找
3.折半查找
4.分块查找
文章来源：https://www.toymoban.com/news/detail-498504.html
排序
文章来源地址https://www.toymoban.com/news/detail-498504.html
到了这里，关于数据结构：常见算法的时间复杂度汇总的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
