数据结构：常见算法的时间复杂度汇总
目录
顺序表
| 算法操作 | 时间复杂度 | 空间复杂度 | 描述 |
| 插入 | 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.分块查找
排序
