常用排序算法时间复杂度统计

什么是时间复杂度

时间复杂度:
算法的时间复杂度是一个函数,它定量的描述了该算法的运行时间.

最坏时间复杂度:
相同大小的不同输入值可能造成算法的运行时间不同,因此我们通常使用算法的最坏复杂度,记做T(n),即任何大小 n所需的最大运行时间

举例来说,有着T(n)=O(n)的算法被称作线性时间算法,而 T(n) = O(M^n) 和 M^n= O(T(n)) 的算法被称作指数时间算法

由于计算机使用二进制的记数系统，对数常常以2为底（即log2
n，有时写作lg n）

常数时间：O(n)
对数时间：O(log(n)), 二分搜索
线性对数时间：O(nlog(n)), 最快的比较排序
二次时间： O(n^2), 冒泡排序、插入排序

常见排序算法的时间复杂度：

image.png