数据结构常见结构和算法时间复杂度
排序算法时间复杂度
数据结构基本操作的复杂度汇总
数据结构基本操作的复杂度汇总
1.顺序表
-
插入操作时间复杂度 最好O(1)，最坏O(n)，平均O(n) 移动结点的平均次数n/2 删除操作时间复杂度 最好O(1)，最坏O(n)，平均O(n) 移动结点的平均次数(n-1)/2 按值查找时间复杂度 最好O(1)，最坏O(n)，平均O(n) 移动结点的平均次数(n+1)/2
2.单链表
-
头插法 插入时间为O(1)，总时间复杂度为O(n) 尾插法O(n) 附设了一个表尾结点的指针，插入时间为O(1)，总时间复杂度为O(n) 按序查找 O(n) 按值查找 O(n) 插入 O(1) 删除 O(1)
其中插入和删除操作，指定结点O(1),需要从头查找则花费主要用于查找O(n)
3.二叉树
-
二叉树的遍历 时间复杂度O(n)，空间复杂度O(n) 二叉排序树 插入/删除，时间复杂度O(n)
4.图（V是顶点个数，E是边的条数）
-
邻接矩阵存储空间 O(n^2) 邻接表存储空间 无向图O(|V|+2|E|)，有向图O(|V|+|E|) 十字链表和邻接多重表存储空间 O(|V|+|E|) 广度优先搜索 时间复杂度：邻接表O(|V|+|E|)，邻接矩阵O(|V|^2) 空间复杂度：O(n) 深度优先搜索 时间复杂度：邻接表O(|V|+|E|)，邻接矩阵O(|V|^2) 空间复杂度：O(n) 求最小生成树时间复杂度 Prim算法：O(|V|^2) Kruskal算法：O(|E|log|E|) 求最短路径时间复杂度 Dijkstra算法：O(|V|^2) Floyd算法：O(|V|^3) 拓扑排序 时间复杂度：O(|V|+|E|)
