本节是《Java数据结构及算法实战》系列的第5节,主要介绍分析算法和数据结构的重要工具——渐近记法。

在前一节,我们介绍了程序的性能,也介绍了评估性能的方式。那么,我们是否就能测算出算法需要运行的时间呢?

1. 大O标记法

直接回答上述问题并非易事,原因在于,即使是同一算法,针对不同的输入运行的时间并不相同。以排序问题为例,输入序列的规模、组成和次序都不是确定的,这些因素都会影响到排序算法的运行时间。在所有这些因素中,输入的规模是最重要的一个。假设我们要对学生按照成绩排序,那么显然,当学生的规模很少时(比如50个)所耗费的排序时间,肯定是要比当学生的规模很大时(比如50万个)所耗费的排序时间短。

因此,在实际分析算法的时间复杂度时,通常只考虑输入规模这一主要因素。如果将某一算法为了处理规模为n的问题所需的时间记作T(n),那么随着问题规模n的增长,运行时间T(n)我们将称之为算法的时间复杂度

由于小规模的问题所需的处理时间相对更少,不同算法在效率方面的差异并不明显,而只有在处理大规模的问题时,这方面的差异才有质的区别。因此,在评价算法的运行时间时,我们往往可以忽略其在处理小规模问题时的性能,转而关注其在处理足够大规模问题时的性能,即所谓的渐进复杂度(Asmpototic Complexity)。

另外,通常我们也不需要知道T(n)的确切大小,而只需要对其上界作出估计。比如说,如果存在正常数a、N和一个函数f(n),使得对于任何n > N,都有

T(n) < a × f(n) 

我们就可以认为在n足够大之后,f(n)给出了T(n)的一个上界。对于这种情况,我们记之为

T(n) = O(f(n))

这里的O称作“大O记号(Big-O notation)”,是希腊字母omicron的大写形式。从上述例子可以看出,大O记号实质上是对算法执行效率的一种保守估计⎯⎯对于规模为n的任意输入,算法的运行时间都不会超过O(f(n))。换言之,大O记号是对算法执行效率最差情况的估算。

大O记号是渐进记法的一种。渐进记法一直就是人们用于分析算法和数据结构的重要工具。其核心思想是:提供一种资源表示形式,主要用于分析某项功能在应对一定规模参数时需要的资源(通常是时间,有时候也会是内存)。常用的渐进记法还包括大Θ记号、大Ω记号。

2. 大Ω标记法

如果存在正常数a、N和一个函数g(n),使得对于任何n>N,都有

T(n) > a × g(n) 

我们就可以认为在n足够大之后,g(n)给出了T(n)的一个下界。对于这种情况,我们记之为

T(n) = Ω(g(n)) 

这里的Ω称作“大Ω记号(Big-Ω notation)”,是希腊字母omega的大写形式。大Ω记号与大O记号正好相反,它是对算法执行效率的一种乐观估计⎯⎯对于规模为n的任意输入,算法的运行时间都不会低于Ω(g(n))。换言之,大O记号是对算法执行效率最好情况的估算。

3. 大Θ标记法

如果存在正常数a<b、N和一个函数h(n),使得对于任何n > N,都有

a × h(n) < T(n) < b × h(n) 

我们就可以认为在n足够大之后,h(n)给出了T(n)的一个确界。对于这种情况,我们记之为

T(n) = Θ(h(n)) 

这里的Θ称作“大Θ记号(Big-Θ notation)”,是希腊字母theta的大写形式。大Θ记号是对算法执行效率的一种准确估计⎯⎯对于规模为n的任意输入,算法的运行时间都与Θ(h(n))同阶。

4. 渐近记法总结

总结而言,渐近记法的含义如下表1-2所示。

表1-2 渐近记法含义

符号 含义
O 渐进小于或等于
Ω 渐进大于或等于
Θ 渐进等于

在上面度量算法复杂度的三种记号中,大O记号是最基本的,也是最常用到的。本书后续的算法复杂度也主要采用按照大O记号来表示。

参考引用