注意,以下插入操作均为在不查重的情况下
数组
无序数组
插入一个元素:O(1) 尾部追加一个元素即可
删除一个元素:O(n) 需要将删除元素索引后面的元素前移
查找一个元素:O(n) 遍历数组
删除所有元素:O(1) 如果是手动申请,可以使用free释放
有序数组
插入一个元素:O(n) 需要维护一个有序数组,所以需要遍历数组找到合适的位置插入,需要将插入元素索引位置后的元素挨个后移
删除一个元素:O(n) 需要将删除元素索引后面的元素前移
查找一个元素:O(logn) 二分查找
删除所有元素:O(1) 同无序数组
思考
请叙述使用二分查找算法的优缺点:时间复杂度较线性搜索更快从O(n)提升到O(logn);但是需要维护一个有序数组,插入时的时间复杂度降低,从O(1)降低到O(n)
链表
无序链表
插入一个节点:O(1) 头插法即可
删除一个节点:O(n) 遍历链表,找到待删除的节点
查找一个节点:O(n) 遍历链表
删除所有节点:O(n) 循环挨个释放节点
有序链表
插入一个节点:O(n) 需要维护一个有序链表,所以需要遍历链表节点的值找到合适的位置插入
删除一个节点:O(n) 遍历链表,找到待删除的节点
查找一个节点:O(n) 没有二分查找,如果使用跳转表,能够提高到O(n^1/2)
删除所有节点:O(n) 循环挨个释放节点
图的三种表现形式
Array of edges
插入一条边:O(1) 默认无序数组,尾插即可
删除一条边:O(E) 需要将删除元素索引后面的元素前移
查找一条边:O(E) 相当于无序数组查询一个元素
删除所有边:O(1) 直接释放边数组
初始化一个AOE:O(1)
注意
插入一条边:O(1) 是假设边数组还有空间,如果已经满了,需要分配一个更大的数组,将边都拷贝过来,时间复杂度为O(E)
如果维护了一个有序的边数组,那么可以用二分查找(BST),来插入或者寻找,所以时间复杂度为O(logE)
Adjacency Matrix
插入一条边:O(1) 置1
删除一条边:O(1) 置0
查找一条边:O(1) 直接根据二维数组索引获取
删除所有边:O(V) 循环每一个顶点,挨个释放数组
创建一个AM:O(V) 首先申请一个一维指针数组O(1),循环动态申请内存O(V)
初始化一个AM:O(V^2)
空间消耗:O(V^2) 如果图是稀疏的,大多数的存储空间都是被浪费的,可以存一小半,也就是存V(V-1)/2个
Adjacency List
插入一条边:O(1) 根据索引值找到待插入边的起始点O(1),插入无序链表,尾插即可
删除一条边:O(V) 根据索引值找到待插入边的起始点O(1),遍历无序链表O(V)
查找一条边:O(V)
删除所有边:O(E) 因为对于一个V个节点,E条边的无向图,邻接表的表节点总数为2E(如果是有向图,节点总数为E),所以删除所有链表节点的时间复杂度为O(E),而删除其邻接链表中的所有节点,每个边的节点会被访问一次,所以删除所有边的时间复杂度也是O(E)
删除所有顶点:O(V)
删除整个邻接表:O(V+E)
创建一个AL:O(1) 只需要创建一位指针数组,动态分配内存空间
初始化一个AL:O(v) 循环指针数组中的每一个指针指向NULL
DFS
假设使用邻接表来实现
All vertices marked as unvisited, each vertex visited at most once => O(V)
Visit all edges incident on visible vertices => O(E)
Time complexity: O(V+E)
The larger of V,E determines the complexity.
对于稠密图,E趋近于V2,所以O(V+E)=O(V2)
对于稠密图,E趋近于V,所以O(V+E)=O(E)
假设使用边数组来实现
Visit all edges incident on visible vertices => O(V.E)
So the cost of DFS is O(V.E)
假设使用邻接矩阵来实现
Visit all edges incident on visible vertices => O(V^2)
So the cost of DFS is O(V^2)
BFS
假设使用邻接表来实现
Time complexity of BFS: O(V+E) (adjacency list representation, same as DFS)