时间复杂度其实还分为 平均时间复杂度、最好时间复杂度 和 最坏时间复杂度。对于一个算法来说，往往有很多特殊情况，一般而言，我们所说的时间复杂度都指最坏时间复杂度，因为在最坏的情况下，我们才能够评估一个算法的性能最差会到什么地步，这样我们才能更好地选择相应的算法去解决问题。
大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
- 为什么快排的时间复杂度是O(nlogn)？
首先，我们很容易可以推出，二分查找的时间复杂度是O(logn)，我们对一堆数字进行快排，每次把大于基准数的放到左边，小于的放到右边，要做多少次？n个数就是O(n)。而每次把数字分为两堆，就是二分排序，O(logn)， 所以快排的时间复杂度是O(nlogn)
参考:
