目的
我们常需要描述特定算法相对于n(输入元素的个数)需要做的工作量。在一组未排序的数据中检索,所需的时间与n成正比;如果是对排序数据用二分检索,花费的时间正比于logn。排序时间可能正比于n2或者nlogn。我们需要有一种方式,用它能把这种说法弄得更精确,同时又能排除掉其中的一些具体细节,如C P U速度,编译系统(以及程序员)的质量等。我们希望能够比较算法的运行时间和空间要求,并使这种比较能与程序设计语言、编译系统、机器结构、处理器的速度及系统的负载等等复杂因素无关。
为了这个目的,人们提出了一种标准的记法,称为“大O记法”。在这种描述中使用的基本参数是n,即问题实例的规模,把复杂性或运行时间表达为n的函数。这里的“O”表示量级( order ),比如说“二分检索是O( logn)的”,也就是说它需要“通过l o gn量级的步骤去检索一
个规模为n的数组”。记法O ( f(n) )表示当n增大时,运行时间至多将以正比于f(n)的速度增长。O(n2)和O(nlogn)都是具体的例子。这种渐进估计对算法的理论分析和大致比较是非常有价值的,但在实践中细节也可能造成差异。例如,一个低附加代价的O(n2)算法在n较小的情况下可
能比一个高附加代价的O(nlogn)算法运行得更快。当然,随着n足够大以后,具有较慢上升函数的算法必然工作得更快。
我们还应该区分算法的最坏情况的行为和期望行为。要定义好“期望”的意义非常困难,因为它实际上还依赖于对可能出现的输入有什么假定。在另一方面,我们通常能够比较精确地了解最坏情况,虽然有时它会造成误解。前面讲过,快速排序的最坏情况运行时间是O(n2),但期望时间是O(nl o gn)。通过每次都仔细地选择基准值,我们有可能把平方情况(即O(n2)情况)的概率减小到几乎等于0。在实际中,精心实现的快速排序一般都能以(O(nlogn)时间运行。
下表是一些最重要的情况:
访问数组中的元素是常数时间操作,或说O( 1 )操作。一个算法如果能在每个步骤去掉一半数据元素,如二分检索,通常它就取O( l o gn)时间。用strcmp比较两个具有n个字符的串需要O(n)时间。常规的矩阵乘算法是O(n3),因为算出每个元素都需要将n对元素相乘并加到一起,所有元素的个数是n2。
指数时间算法通常来源于需要求出所有可能结果。例如, n个元素的集合共有2n个子集,所以要求出所有子集的算法将是O( 2n)的。指数算法一般说来是太昂贵了,除非n的值非常小,因为,在这里问题中增加一个元素就导致运行时间加倍。不幸的是,确实有许多问题(如著名的“巡回售货员问题” ),到目前为止找到的算法都是指数的。如果我们真的遇到这种情况,通常应该用寻找近似最佳结果的算法替代之。