时间复杂度其实还分为 平均时间复杂度、最好时间复杂度和 最坏时间复杂度。对于一个算法来说，往往有很多特殊情况，一般而言，我们所说的时间复杂度都指最坏时间复杂度，因为在最坏的情况下，我们才能够评估一个算法的性能最差会到什么地步，这样我们才能更好地选择相应的算法去解决问题。

大 O 表示法

目前通用的时间复杂度的表示法是“大 O 表示法”，但其实同时还存在其他的符号。

• O: 表示的是最坏时间复杂度，即小于等于

• Ω: 表示的是最好时间复杂度，即大于等于，不常用，因为没有什么参考意义，过于乐观。

• θ: 表示确界，即明确等于

除了大 O 之外其他的不常用但最好了解一下。

常见时间复杂度比较

常见时间复杂度：

• 常数阶 O(1)

• 线性阶 O(n)

• 平方阶 O(n²)

• 对数阶 O(logn)

• 线性对数阶 O(nlogn)

常见时间复杂度排序

注意：O(nlogn)、O(logn) 内部的内容在数学里是错误的，一般应该是 log2n 等，但是这里的系数并不在我们的考虑范围之内，所以我们一般在计算复杂度时直接将其表示为 O(nlogn) 和 O(logn)。

猴子排序等时间复杂度为 O(n!)，时间复杂度最高。

这里有一张图，可以直观看出各种时间复杂度的好坏：

各种时间复杂度好坏

时间复杂度最好的算法是 O(1)，即有限次数内得到结果。当然，一个算法能不能达到 O(1) 的时间复杂度，要看具体情况，我们当然希望程序的性能能够达到最优，所以算法的时间复杂度能够低于 O(n2) 一般来说已经很不错了。不要忘了，算法的性能除考虑时间复杂度外还要考虑空间复杂度，在大多数情况下往往需要在时间复杂度和空间复杂度之间进行权衡。

我们在上面提到的情况都只有一个规模参数，有时规模参数也可能有两个。比如两层嵌套循环的规模不一样，我们假设分别为 m 和 n，这时我们一般会把时间复杂度写为 O(m×n)，但是我们自己需要明确，如果 m 和 n 非常相近，则这个时间复杂度趋于 O(n2)；如果 m 通常比较小（也就是说我们能够明白 m 的范围是多少），则这个时间复杂度趋于 O(n)。在这两种情况下，虽然时间复杂度都是 O(m×n)，但是真实的时间复杂度可能相差很大。

一些小 tips

1. 为什么快排的时间复杂度是 O(nlogn)？

首先，我们很容易可以推出，二分查找的时间复杂度是 O(logn)，我们对一堆数字进行快排，每次把大于基准数的放到左边，小于的放到右边，要做多少次？n 个数就是 O(n)。而每次把数字分为两堆，就是二分排序，O(logn)， 所以快排的时间复杂度是 O(nlogn)