各个数据结构和算法的复杂度总结

发表于： 更新于： 分类于：
字数： 463 阅读：≈ 1分钟 浏览：

排序算法

排序算法最坏时间复杂度平均时间复杂度最好时间复杂度空间复杂度是否稳定是否原地
选择排序n^2n^2n^21不是是
插入排序n^2n^2n1是是
归并排序nlognnlognnlognn是不是
快速排序n^2nlognnlognlogn不是是
堆排序nlognnlognnlogn1不是是
Tree Sortn^2nlognnlogn1不是是
  • 快速排序空间复杂度的logn是递归过程的内存占用。
  • 快速排序是否稳定和是否原地取决于分区函数，一般实现是原地排序并且不稳定。
  • 堆排序建堆过程的时间复杂度是n。
  • Tree Sort 构建过程是nlogn，遍历是n。如果树极度不平衡，则退化成链表，时间变成n^2。

数据结构

一些数据结构的操作的时间复杂度。

堆

  • 插入元素：logn
  • 删除堆顶元素：logn

注：插入数据和删除堆顶元素的主要逻辑就是堆化，堆化的时间复杂度跟树的高度成正比，所以时间复杂度都是logn。建堆时间复杂度是n，不是nlogn。

二叉搜索树

  • 快速查找：logn，最差情况n
  • 插入：logn，最差情况n
  • 删除：logn，最差情况n
  • 遍历：n

注：二叉搜索树退化成链表的时候就是n，如果平衡的时候就是logn。

快速选择

利用快速排序的核心思想，在Θ(n)时间复杂度下查找第k个元素（第k小或第k大）。