你真的了解大O符号吗？

对于一个算法，一般来说我们能够通过计算来确定它的复杂度，比如遍历一个链表结构，链表的元素个数为

，显然复杂度是

，对于这个大

符号，我们再熟悉不过。

可是，如果有人说这个复杂度是

，又或者是

，你还能理解是什么意思吗？

让我们一起复习一下渐近符号。

我们常需要分析一个算法的性能如何。例如我们说快速排序在最坏情况下性能为

，而平均情况下性能为

。这些讨论中会用到

这种渐近记号。

在《算法导论》第三章介绍了5种渐近记号：

、

、

、

、

，其中3个是拉丁符号，另外2个是大写字母

和小写字母

。

是函数集合，其算术定义有点类似极限的定义：

={

: 存在正常数

,

和

，对所有

，有

}。

则是取上界，

取下界，另外一种说法是前者是最坏情况，后者是最好的情况，比如对于插入排序来说，最好情况是

，我们可以说插入排序的复杂度是

，插入排序的最坏情况是

，所以一般来说我只会说插入排序是

复杂度的。

算术定义不是很便于理解，直观地理解：当n特别大的时候，如果

夹在

和

之间，就说

属于

。

虽然是集合，但是我们更喜欢写成

。下图可以更直观的理解三者的区别。

这个图中，最左边是

符号，中间是大

符号，最右边是

符号，从图中可以看出，前者是后两者的公共部分，限制更多，我们用的最多的大

是算法的上界。

《算法导论》第三章末尾也说了，渐近记号在历史上出现了一些演变。最早大家都用

，符号；后来

建议用

和

；在今天我们知道

是最准确的符号，但大家还是都习惯用

符号。所以当我们谈到快排的平均复杂度是

的时候，我们心里清楚其实准确的写法是

。