数据结构中常用的操作的效率表
通用数据结构 | 查找 | 插入 | 删除 | 遍历 |
---|---|---|---|---|
数组 | O(N) | O(1) | O(N) | — |
有序数组 | O(logN) | O(N) | O(N) | O(N) |
链表 | O(N) | O(1) | O(N) | — |
有序链表 | O(N) | O(N) | O(N) | O(N) |
二叉树 | O(logN) | O(logN) | O(logN) | O(N) |
二叉树(最坏) | O(N) | O(N) | O(N) | O(N) |
红黑树 | O(logN) | O(logN) | O(logN) | O(N) |
2-3-4树 | O(logN) | O(logN) | O(logN) | O(N) |
哈希表 | O(1) | O(1) | O(1) | — |
专用数据结构 | ||||
栈 | — | O(1) | O(1) | — |
队列 | — | O(1) | O(1) | — |
优先级队列 | — | O(N) | O(1) | — |
优先级队列(堆) | — | O(logN) | O(logN) |
常见的排序算法比较表
排序 | 平均情况 | 最好情况 | 最坏情况 | 稳定与否 | 空间复杂度 |
---|---|---|---|---|---|
冒泡排序 | O(N2) | O(N) | O(N2) | 稳定 | 1 |
选择排序 | O(N2) | O(N2) | O(N2) | 不稳定 | 1 |
插入排序 | O(N2) | O(N) | O(N2) | 稳定 | 1 |
希尔排序 | O(NlogN) | (依赖于增量序列) | 不稳定 | 1 | |
快速排序 | O(NlogN) | O(NlogN) | O(N2) | 不稳定 | O(logN) |
归并排序 | O(NlogN) | O(NlogN) | O(NlogN) | 稳定 | O(N) |
二叉树排序 | O(NlogN) | O(NlogN) | O(N2) | 稳定 | O(N) |
堆排序 | O(NlogN) | O(NlogN) | O(NlogN) | 不稳定 | 1 |
拓扑排序 | O(N+E) | — | — | — | O(N) |
首先先给出我们常用的算法的时间复杂度,后面会具体讲解每一个算法,以及在不同的场合下哪种时间复杂度很高效