注意，以下插入操作均为在不查重的情况下
数组
无序数组
插入一个元素：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)