各个数据结构和算法的复杂度总结
排序算法
排序算法 | 最坏时间复杂度 | 平均时间复杂度 | 最好时间复杂度 | 空间复杂度 | 是否稳定 | 是否原地 |
---|---|---|---|---|---|---|
选择排序 | n^2 | n^2 | n^2 | 1 | 不是 | 是 |
插入排序 | n^2 | n^2 | n | 1 | 是 | 是 |
归并排序 | nlogn | nlogn | nlogn | n | 是 | 不是 |
快速排序 | n^2 | nlogn | nlogn | logn | 不是 | 是 |
堆排序 | nlogn | nlogn | nlogn | 1 | 不是 | 是 |
Tree Sort | n^2 | nlogn | nlogn | 1 | 不是 | 是 |
- 快速排序空间复杂度的logn是递归过程的内存占用。
- 快速排序是否稳定和是否原地取决于分区函数,一般实现是原地排序并且不稳定。
- 堆排序建堆过程的时间复杂度是n。
- Tree Sort 构建过程是nlogn,遍历是n。如果树极度不平衡,则退化成链表,时间变成n^2。
数据结构
一些数据结构的操作的时间复杂度。