0%

常见算法性能

简介

常见的复杂度如下

  • 常数阶 $O(1)$
  • 对数阶 $O(log_2N)$
  • 线性阶 $O(n)$
  • 线性对数阶 $O(nlog_2N)$
  • 平方阶 $O(n²)$
  • 立方阶 $O(n³)$
  • K次方阶 $O(n^k)$
  • 指数阶 $O(2^n)$

常用排序算法

名称 类别 平均值 最好值 最坏值 空间复杂度 稳定性 备注
直接插入 插入排序 $O(n^2)$ $O(n)$ $O(n^2)$ $O(1)$ 稳定
shell 排序 插入排序 $O(n^{1.3})$ $O(n)$ $O(n^2)$ $O(1)$ 不稳定
直接选择 选择排序 $O(n^2)$ $O(n^2)$ $O(n^2)$ $O(1)$ 不稳定
堆排序 选择排序 $O(nlog_2n)$ $O(nlog_2n)$ $O(nlog_2n)$ $O(1)$ 不稳定
冒泡法 交换排序 $O(n^2)$ $O(n)$ $O(n^2)$ $O(1)$ 稳定
快速排序 交换排序 $O(nlog_2n)$ $O(nlog_2n)$ $O(n^2)$ $O(nlog_2n)$ 稳定
归并排序 $O(nlog_2n)$ $O(nlog_2n)$ $O(nlog_2n)$ $O(1)$ 稳定
基数排序 $O(d(r+n))$ $O(d(n+rd))$ $O(d(r+n))$ $O(rd+n)$ 稳定 r 代表关键字的基数, d 代表长度, n 代表关键字的个数