对于一个算法,一般来说我们能够通过计算来确定它的复杂度,比如遍历一个链表结构,链表的元素个数为
,显然复杂度是
,对于这个大
符号,我们再熟悉不过。
可是,如果有人说这个复杂度是
,又或者是
,你还能理解是什么意思吗?
让我们一起复习一下渐近符号。
我们常需要分析一个算法的性能如何。例如我们说快速排序在最坏情况下性能为
,而平均情况下性能为
。这些讨论中会用到
这种渐近记号。
在《算法导论》第三章介绍了5种渐近记号:
、
、
、
、
,其中3个是拉丁符号,另外2个是大写字母
和小写字母
。
是函数集合,其算术定义有点类似极限的定义:
={
: 存在正常数
,
和
,对所有
,有
}。
则是取上界,
取下界,另外一种说法是前者是最坏情况,后者是最好的情况,比如对于插入排序来说,最好情况是
,我们可以说插入排序的复杂度是
,插入排序的最坏情况是
,所以一般来说我只会说插入排序是
复杂度的。
算术定义不是很便于理解,直观地理解:当n特别大的时候,如果
夹在
和
之间,就说
属于
。
虽然是集合,但是我们更喜欢写成
。下图可以更直观的理解三者的区别。
这个图中,最左边是
符号,中间是大
符号,最右边是
符号,从图中可以看出,前者是后两者的公共部分,限制更多,我们用的最多的大
是算法的上界。
《算法导论》第三章末尾也说了,渐近记号在历史上出现了一些演变。最早大家都用
,符号;后来
建议用
和
;在今天我们知道
是最准确的符号,但大家还是都习惯用
符号。所以当我们谈到快排的平均复杂度是
的时候,我们心里清楚其实准确的写法是
。