2.2　函数的渐近增长率

根据1.3节的定义，算法的最坏情况时间复杂度是规模n的函数。由于n是一个变量，这就给比较算法的优劣带来一个问题：算法1和算法2在规模值n取不同值的时候，它们的优劣可能是不一样的。常见的情况是，有一些复杂的算法在小规模的时候无优势甚至有劣势，但是它们的优势将在问题规模很大的时候显现出来。我们在进行算法分析的时候，更关心问题规模很大时算法的表现。但是何谓规模大，对于不同的算法而言又千差万别。有的算法可能在几千的规模上就比同类算法有优势，而有的算法可能需要到百万级的规模才能显现优势。

正是针对算法分析中的上述困难，我们引入函数的渐近增长率(asymptotic growth rate)概念，其中：●增长率的概念使得我们集中关注算法在规模较大时候的性能表现，它关注的不是代价函数的具体的值，而是代价函数的值随规模增长的速度。因而不管开始的优劣如何，增长率较快的函数在面对大规模输入的时候值会变得更大。●渐近的概念帮我们处理了不同算法对于 “大规模”的含义有不同解读的问题，它关注的是问题规模趋于无穷时算法代价的变化情况。我们引入3组共5个不同的记号来描述函数的渐近增长率之间的关系，它们是O和o 、Ω 和ω 、Θ。我们首先给出使用极限语言的定义，在此基础上给出基于求极限的判别方法。在这3组记号中，O和o的定义是基础，这两个符号之间的差别是理解其定义的重点。首先给出这两个记号的定义。定义2.2（f(n)=O(g(n))）●O(g(n)) ={f(n)：存在常数c>0和n0>0，满足0≤f(n)≤cg(n)对所有n≥n0均成立}。●f(n)=O(g(n)) iff limn→∞f(n)g(n)=c<∞。定义2.3（f(n)=o(g(n))）●o(g(n)) ={f(n)：对任意常数c>0，均存在常数n0>0，满足0≤f(n)●f(n)=o(g(n)) iff limn→∞f(n)g(n)=0。不严格地说，f(n)=O(g(n))描述的是当问题规模充分大的时候，函数f(n)的增长率不会超过g(n)的增长率。与记号O(g(n))相比，f(n)=o(g(n))虽然同样表示函数f(n)的增长率不会超过g(n)的增长率，但是它的要求更强。f(n)=o(g(n))强调函数f(n)和g(n)在增长率方面有一种“实质性的差距”：总可以通过增加问题规模n，使得函数f(n)和g(n)之间有任意大的差距。与上述定义对偶，我们有下面两个定义。定义2.4（f(n)=Ω(g(n))）●Ω(g(n)) ={f(n)：存在常数c>0和n0>0，满足0≤cg(n)≤f(n)对所有n≥n0均成立}。●f(n)=Ω(g(n)) iff limn→∞f(n)g(n)=c>0（c也可以为∞）。定义2.5（f(n)=ω(g(n))）●ω(g(n)) ={f(n)：对任意常数c>0，均存在常数n0>0，满足0≤cg(n)●f(n)=ω(g(n)) iff limn→∞f(n)g(n)=∞。与O和o的定义对偶，f(n)=Ω(g(n))描述的是随着问题规模的增大，函数f(n)的增长率不会低于g(n)的增长率；而f(n)=ω(g(n))同样强调函数f(n)和g(n)在增长率方面有一种“实质性的差距”：总可以通过规模n的增大，使得f(n)和g(n)有任意大的差距。另外，我们可以定义f(n)=Θ(g(n))，它表示f(n)和g(n)的增长率处于“同一水平”。定义2.6（f(n)=Θ(g(n))）●Θ(g(n)) ={f(n)：存在常数c1>0，c2>0和n0>0，满足0≤c1g(n)≤f(n)≤c2g(n)对所有n≥n0均成立}。●f(n)=Θ(g(n)) iff limn→∞f(n)g(n)=c，这里 0根据上述定义，我们很容易验证：●O、Ω、Θ、o、ω这5种关系均满足传递性。●O、Ω、Θ这3种关系满足自反性。●Θ是一个等价关系。●f(n)=Θ(g(n)) iff f(n)=O(g(n))且f(n)=Ω(g(n))。●O、 o和Ω、ω之间有一种对偶的关系，即f=O(g) iff g=Ω(f),f=o(g) iff g=ω(f)。这些性质的证明留作习题。