Algorithm 版 (精华区)

发信人: Lerry (想不开·撞树), 信区: Algorithm
标  题: 复杂性的渐近性态及其阶
发信站: 哈工大紫丁香 (2002年03月22日14:38:46 星期五), 站内信件

复杂性的渐近性态及其阶
随着经济的发展、社会的进步、科学研究的深入，要求用计算机解决的问题越来越复杂
，规模越来越大。但是，如果对这类问题的算法进行分析用的是第二段所提供的方法，
把所有的元运算都考虑进去，精打细算，那么，由于问题的规模很大且结构复杂，算法
分析的工作量之大、步骤之繁将令人难以承受。因此，人们提出了对于规模充分大、结
构又十分复杂的问题的求解算法，其复杂性分析应如何简化的问题。
我们先要引入复杂性渐近性态的概念。设T(N)是在第二段中所定义的关于算法A的复杂性
函数。一般说来，当N单调增加且趋于∞时,T(N)也将单调增加趋于∞。对于T(N)，如果
存在T’(N)，使得当N→∞时有：
(T(N )-T’(N ))/T(N ) → 0
那么，我们就说T’(N)是T(N)当N→∞时的渐近性态，或叫T’(N)为算法A当N→∞的渐近
复杂性而与T(N)相区别，因为在数学上，T’(N)是T(N)当N→∞时的渐近表达式。
直观上，T’(N)是T(N)中略去低阶项所留下的主项。所以它无疑比T(N)来得简单。比如
当
T(N)=3N 2+4Nlog2N +7
时，T’(N)的一个答案是3N 2，因为这时有：
显然3N 2比3N 2 +4Nlog2N +7简单得多。
由于当N→∞时T(N)渐近于T’(N)，我们有理由用T’(N)来替代T(N)作为算法A在N→∞时
的复杂性的度量。而且由于于T’(N)明显地比T(N)简单，这种替代明显地是对复杂性分
析的一种简化。
进一步，考虑到分析算法的复杂性的目的在于比较求解同一间题的两个不同算法的效率
，而当要比较的两个算法的渐近复杂性的阶不相同时，只要能确定出各自的阶，就可以
判定哪一个算法的效率高。换句话说，这时的渐近复杂性分析只要关心T’(N)的阶就够
了，不必关心包含在T’(N)中的常数因子。所以，我们常常又对T’(N)的分析进--步简
化，即假设算法中用到的所有不同的元运算各执行一次，所需要的时间都是一个单位时
间。
综上所述，我们已经给出了简化算法复杂性分析的方法和步骤，即只要考察当问题的规
模充分大时，算法复杂性在渐近意义下的阶。与此简化的复杂性分析方法相配套，需要
引入五个渐近意义下的记号：Ο、Ω、θ、ο和ω。
以下设f(N)和g(N)是定义在正数集上的正函数。
如果存在正的常数C和自然数N0，使得当N≥N0时有f(N)≤Cg(N)。则称函数f(N)当N充分
大时上有界，且g(N)是它的一个上界，记为f(N)=Ο(g(N))。这时我们还说f(N)的阶不高
于g(N)的阶。
举几个例子：
(1)因为对所有的N≥1有3N≤4N，我们有3N =Ο(N)；
(2)因为当N≥1时有N+1024≤1025N，我们有N +1024=Ο(N)；
(3)因为当N≥10时有2N 2+11N -10≤3N 2，我们有2N 2+11N -10=Ο(N 2)；
(4)因为对所有N≥1有N 2≤N 3，我们有N2=Ο(N 3)；
(5)作为一个反例N 3≠Ο(N 2)。因为若不然，则存在正的常数C和自然数N0，使得当N≥
N0时有N3≤C N 2，即N≤C 。显然当取N =max(N0,[C]+l)时这个不等式不成立，所以N3
≠Ο(N 2)。
按照大Ο的定义，容易证明它有如下运算规则：
Ο(f)+Ο(g)=Ο(max(f,g))；
Ο(f)+ Ο(g)=Ο(f +g)；
Ο(f)·Ο(g)= Ο(f·g)；
如果g(N)= Ο(f(N))，则Ο(f)+ Ο(g)= Ο(f)；
Ο(Cf(N))= Ο(f(N))，其中C是一个正的常数；
f =Ο(f)；
规则1的证明：
设F(N)= Ο(f) 。根据记号Ο的定义，存在正常数C1和自然数N1，使得对所有的N≥N1，
有F(N)≤C1 f(N)。类似地，设G(N)=Ο(g)，则存在正的常数C2和自然数N2使得对所有的
N≥N2有G(N)≤C2g(N)，今令：
C3=max(C1, C2)
N3=max(N1, N2)
和对任意的非负整数N，
h(N)=max(f,g),
则对所有的N≥N3有：
F(N)≤C1f(N)≤C1h(N)≤C3h(N)
类似地，有：
G(N)≤C2g(N)≤C2h(N)≤C3h(N)
因而
Ο(f)+Ο(g) =F(N)+G(N)≤C3h(N)+ C3h(N)
 =2C3h(N)
 =Ο(h)
 =Ο(max(f,g))
其余规则的证明类似，请读者自行证明。
应用这些规则的一个例子：对于第一章中的算法search，在第二章给出了它的最坏情况
下时间复杂性Tmax(m)和平均情况下的时间复杂性Tavg(m)的表达式。如果利用上述规则
，立即有:
Tmax(m)=Ο(m)
和 Tavg(m)=Ο(m)+Ο(m)+Ο(m)=Ο(m)
另一个例子：估计下面二重循环算法段在最坏情况下的时间复杂性T(N)的阶。
for i:=l to N do
  for j:=1 to i do
    begin
     S1;
     S2;
     S3;
     S4;
    end;
其中Sk (k=1,2,3,4)是单一的赋值语句。对于内循环体，显然只需Ο(l)时间。因而内循
环只需
时间。累加起来便是外循环的时间复杂性：
应该指出，根据记号Ο的定义，用它评估算法的复杂性，得到的只是当规模充分大时的
一个上界。这个上界的阶越低则评估就越精确，结果就越有价值。
关于记号Ω，文献里有两种不同的定义。本文只采用其中的一种，定义如下：如果存在
正的常数C和自然数N0，使得当N≥N0时有f(N)≥Cg(N)，则称函数f(N)当N充分大时下有
界，且g(N)是它的一个下界，记为f(N)=Ω(g(N))。这时我们还说f(N)的阶不低于g(N)的
阶。
Ω的这个定义的优点是与Ο的定义对称，缺点是当f(N)对自然数的不同无穷子集有不同
的表达式，且有不同的阶时，未能很好地刻画出f(N)的下界。比如当：
时，如果按上述定义，只能得到f(N)=Ω(1)，这是一个平凡的下界，对算法分析没有什
么价值。
然而，考虑到Ω的上述定义有与Ο的定义的对称性，又考虑到常用的算法都没出现上例
中那种情况，所以本文还是选用它。
我们同样也可以列举Ω的一些运算规则。但这里从略，只提供一个应用的例子。还是考
虑算法Search在最坏情况下的时间复杂性函数Tmax(m)。由它的表达式(2.7)及已知a,s,
t均为大于0的常数，可推得，当m≥1时有：
Tmax(m)≥(m+1)a+(2m+1)t>ma+2mt=(a+2t)m ，
于是 Tmax(m)=Ω(m)。
我们同样要指出，用Ω评估算法的复杂性，得到的只是该复杂性的一个下界。这个下界
的阶越高，则评估就越精确，结果就越有价值。再则，这里的Ω只对问题的一个算法而
言。如果它是对一个问题的所有算法或某类算法而言，即对于一个问题和任意给定的充
分大的规模N，下界在该问题的所有算法或某类算法的复杂性中取，那么它将更有意义。
这时得到的相应下界，我们称之为问题的下界或某类算法的下界。它常常与Ο配合以证
明某问题的一个特定算法是该问题的最优算法或该问题在某算法类中的最优算法。
明白了记号Ο和Ω之后，记号θ将随之清楚，因为我们定义f(N)=θ(g(N))则f(N)=Ο(g
(N)) 且f(N)=Ω(g(N))。这时，我们说f(N)与g(N)同阶。比如，对于算法Search在最坏
情况下的时间复杂性Tmax(m)。已有Tmax(m)=Ο(m)和Tmax(m)=Ω(m)，所以有Tmax(m)=θ
(m)，这是对Tmax(m)的阶的精确估计。
最后，如果对于任意给定的ε≥0，都存在非负整数N0，使得当N≥N0时有f(N)≤εg(N)
，则称函数f(N)当N充分大时比g(N)低阶，记为f(N)= o(g(N))，例如：
4NlogN +7=o(3N 2+4NlogN+7)；而f(N)=ω(g(N))定义为g(N)=o(f(N))。
即当N充分大时f(N)的阶比g(N)高。我们看到o对于Ο有如ω对于Ω。

--
　　不在乎天长地久，就怕你从来没有！

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 天外飞仙]