常用算法和数据结构的复杂度速查表
搜索 算法数据结构时间复杂度空间复杂度平均最差最差
深度优先搜索 (DFS) Graph of |V| vertices and |E| edges - O(|E| + |V|) O(|V|)
广度优先搜索 (BFS) Graph of |V| vertices and |E| edges - O(|E| + |V|) O(|V|)
二分查找 Sorted array of n elements O(log(n)) O(log(n)) O(1)
穷举查找 Array O(n) O(n) O(1)
最短路径-Dijkstra，用小根堆作为优先队列 Graph with |V| vertices and |E| edges O((|V| + |E|) log |V|) O((|V| + |E|) log |V|) O(|V|)
最短路径-Dijkstra，用无序数组作为优先队列 Graph with |V| vertices and |E| edges O(|V|^2) O(|V|^2) O(|V|)
最短路径-Bellman-Ford Graph with |V| vertices and |E| edges O(|V||E|) O(|V||E|) O(|V|)
排序 算法数据结构时间复杂度最坏情况下的辅助空间复杂度
最佳平均最差最差
快速排序 数组 O(n log(n)) O(n log(n)) O(n^2) O(n)
归并排序 数组 O(n log(n)) O(n log(n)) O(n log(n)) O(n)
堆排序 数组 O(n log(n)) O(n log(n)) O(n log(n)) O(1)
冒泡排序 数组 O(n) O(n^2) O(n^2) O(1)
插入排序 数组 O(n) O(n^2) O(n^2) O(1)
选择排序 数组 O(n^2) O(n^2) O(n^2) O(1)
桶排序 数组 O(n+k) O(n+k) O(n^2) O(nk)
基数排序 数组 O(nk) O(nk) O(nk) O(n+k)
数据结构 数据结构时间复杂度空间复杂度
平均最差最差
索引查找插入删除索引查找插入删除
基本数组 O(1) O(n) - - O(1) O(n) - - O(n)
动态数组 O(1) O(n) O(n) O(n) O(1) O(n) O(n) O(n) O(n)
O(n) O(n) O(1) O(1) O(n) O(n) O(1) O(1) O(n)
双链表 O(n) O(n) O(1) O(1) O(n) O(n) O(1) O(1) O(n)
跳表 O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(n) O(n) O(n) O(n) O(n log(n))
哈希表 - O(1) O(1) O(1) - O(n) O(n) O(n) O(n)
二叉搜索树 O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(n) O(n) O(n) O(n) O(n)
笛卡尔树 - O(log(n)) O(log(n)) O(log(n)) - O(n) O(n) O(n) O(n)
B-树 O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(n)
红黑树 O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(n)
伸展树 - O(log(n)) O(log(n)) O(log(n)) - O(log(n)) O(log(n)) O(log(n)) O(n)
AVL 树 O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(n)
堆 Heaps时间复杂度
建堆查找最大值提取最大值Increase Key插入删除合并
链表（已排序） - O(1) O(1) O(n) O(n) O(1) O(m+n)
链表（未排序） - O(n) O(n) O(1) O(1) O(1) O(1)
二叉堆 O(n) O(1) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(m+n)
二项堆 - O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n))
斐波那契堆 - O(1) O(log(n))* O(1)* O(1) O(log(n))* O(1)
图 节点 / 边 管理StorageAdd VertexAdd EdgeRemove VertexRemove EdgeQuery
邻接表 O(|V|+|E|) O(1) O(1) O(|V| + |E|) O(|E|) O(|V|)
关联表 O(|V|+|E|) O(1) O(1) O(|E|) O(|E|) O(|E|)
邻接矩阵 O(|V|^2) O(|V|^2) O(1) O(|V|^2) O(1) O(1)
关联矩阵 O(|V| ⋅ |E|) O(|V| ⋅ |E|) O(|V| ⋅ |E|) O(|V| ⋅ |E|) O(|V| ⋅ |E|) O(|E|)