第1章 绪讳 §1.2 复杂度度量
9
1.2.2 渐进复杂度
至此，对于同一问题的两个算法A和B，通过比较其时间复杂度TA(n)和TB(n)，即可评价二
者对于同一输入规模n的计算效率高低。然而，藉此还不足以就其性能优劣做出总体性的评判，
比如对于某些问题，一些算法更适用于小规模输入，而另一些则相反（习题[1-5]）。
幸运的是，在评价算法运行效率时，我们往往可以忽略其处理小规模问题时的能力差异，转
而关注其在处理更大规模问题时的表现。其中的原因不难理解，小规模问题所需的处理时间本来
就相对更少，故此时不同算法的实际效率差异并不明显；而在处理更大规模的问题时，效率的些
许差异都将对实际执行效果产生巨大的影响。这种着眼长远、更为注重时间复杂度的总体变化趋
势和增长速度的策略与方法，即所谓的渐进分析（asymptotic analysis）。
那么，针对足够大的输入规模n，算法执行时间T(n)的渐进增长速度，应如何度量和评价呢？
大O记号
同样地出于保守的估计，我们首先关注T(n)的渐进上界。为此可引入所谓“大O记号”
（big-O notation）。具体地，若存在正的常数c和函数f(n)，使得对任何n >> 2都有
T(n) c∙f(n)
则可认为在n足够大之后，f(n)给出了T(n)增长速度的一个渐进上界。此时，记之为：
T(n) = O(f(n))
由这一定义，可导出大O记号的以下性质：
(1) 对于任一常数c > 0，有O(f(n)) = O(c∙f(n))
(2) 对于任意常数a > b > 0，有O(n
a
+ n
b
) = O(n
a
)
前一性质意味着，在大O记号的意义下，函数各项正的常系数可以忽略并等同于1。后一性
质则意味着，多项式中的低次项均可忽略，只需保留最高次项。可以看出，大O记号的这些性质
的确体现了对函数总体渐进增长趋势的关注和刻画。
环境差异
在实际环境中直接测得的执行时间T(n)，虽不失为衡量算法性能的一种指标，但作为评判
不同算法性能优劣的标准，其可信度值得推敲。事实上，即便是同一算法、同一输入，在不同的
硬件平台上、不同的操作系统中甚至不同的时间，所需要的计算时间都不尽相同。因此，有必要
按照超脱于具体硬件平台和软件环境的某一客观标准，来度量算法的时间复杂度，并进而评价不
同算法的效率差异。
基本操作
一种自然且可行的解决办法是，将时间复杂度理解为算法中各条指令的执行时间之和。在图
灵机（Turing Machine, TM）和随机存储机（Random Access Machine, RAM）等计算模型
[4]
中，指令语句均可分解为若干次基本操作，比如算术运算、比较、分支、子程序调用与返回等；
而在大多数实际的计算环境中，每一次这类基本操作都可在常数时间内完成。
如此，不妨将T(n)定义为算法所执行基本操作的总次数。也就是说，T(n)决定于组成算法
的所有语句各自的执行次数，以及其中所含基本操作的数目。以代码1.1中起泡排序
bubblesort1A()算法为例，若将该算法处理长度为n的序列所需的时间记作T(n)，则按照上述
分析，只需统计出该算法所执行基本操作的总次数，即可确定T(n)的上界。
