目录
顺序表
算法操作 | 时间复杂度 | 空间复杂度 | 描述 |
插入 | 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://blog.csdn.net/qq_44495605/article/details/127652715