复杂性的渐近性态及其阶

随着经济的发展、社会的进步、科学研究的深入，要求用计算机解决的问题越来越复杂，规模越来越大。但是，如果对这类问题的算法进行分析用的是第二段所提供的方法，把所有的元运算都考虑进去，精打细算，那么，由于问题的规模很大且结构复杂，算法分析的工作量之大、步骤之繁将令人难以承受。因此，人们提出了对于规模充分大、结构又十分复杂的问题的求解算法，其复杂性分析应如何简化的问题。

我们先要引入复杂性渐近性态的概念。设T(N)是在第二段中所定义的关于算法A的复杂性函数。一般说来，当N单调增加且趋于∞时,T(N)也将单调增加趋于∞。对于T(N)，如果存在T’(N)，使得当N→∞时有：

8A2z%x,h#c-P M2zZ#u["a'z0(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)来得简单。比如当51Testing软件测试网)[!OQ2BPH

T(N)=3N²+4Nlog₂N+751Testing软件测试网1cnNv ThH;J

时，T’(N)的一个答案是3N²，因为这时有：51Testing软件测试网G)A$OXE%EJ(w~7~9T6G

51Testing软件测试网sUla`(g+BC(?

显然3N²比3N²+4Nlog₂N+7简单得多。

由于当N→∞时T(N)渐近于T’(N)，我们有理由用T’(N)来替代T(N)作为算法A在N→∞时的复杂性的度量。而且由于于T’(N)明显地比T(N)简单，这种替代明显地是对复杂性分析的一种简化。51Testing软件测试网.c&l0[,},Bn;B~l

进一步，考虑到分析算法的复杂性的目的在于比较求解同一间题的两个不同算法的效率，而当要比较的两个算法的渐近复杂性的阶不相同时，只要能确定出各自的阶，就可以判定哪一个算法的效率高。换句话说，这时的渐近复杂性分析只要关心T’(N)的阶就够了，不必关心包含在T’(N)中的常数因子。所以，我们常常又对T’(N)的分析进--步简化，即假设算法中用到的所有不同的元运算各执行一次，所需要的时间都是一个单位时间。

综上所述，我们已经给出了简化算法复杂性分析的方法和步骤，即只要考察当问题的规模充分大时，算法复杂性在渐近意义下的阶。与此简化的复杂性分析方法相配套，需要引入五个渐近意义下的记号：Ο、Ω、θ、ο和ω。51Testing软件测试网'V^EJeXm}U

5Lwg@V.^I0以下设f(N)和g(N)是定义在正数集上的正函数。51Testing软件测试网"zV%}P }

如果存在正的常数C和自然数N₀，使得当N≥N₀时有f(N)≤Cg(N)。则称函数f(N)当N充分大时上有界，且g(N)是它的一个上界，记为f(N)=Ο(g(N))。这时我们还说f(N)的阶不高于g(N)的阶。51Testing软件测试网1P+sS)W|C6a/SD1}

举几个例子：51Testing软件测试网J
[r"j?Yk

(1)因为对所有的N≥1有3N≤4N，我们有3N=Ο(N)；51Testing软件测试网Q \\;lL5L!S

(2)因为当N≥1时有N+1024≤1025N，我们有N+1024=Ο(N)；51Testing软件测试网Y8f*QK~|)`,l+]

(3)因为当N≥10时有2N²+11N-10≤3N²，我们有2N²+11N-10=Ο(N²)；

(4)因为对所有N≥1有N²≤N³，我们有N²=Ο(N³)；51Testing软件测试网#y+l;ot)q3V

(5)作为一个反例N³≠Ο(N²)。因为若不然，则存在正的常数C和自然数N₀，使得当N≥N₀时有N³≤CN²，即N≤C。显然当取N=max(N₀,[C]+l)时这个不等式不成立，所以N³≠Ο(N²)。51Testing软件测试网3D_R ^v U$C6q-{

按照大Ο的定义，容易证明它有如下运算规则：

1. Ο(f)+Ο(g)=Ο(max(f,g))；
2. Ο(f)+Ο(g)=Ο(f+g)；
3. Ο(f)·Ο(g)=Ο(f·g)；
4. 如果g(N)=Ο(f(N))，则Ο(f)+Ο(g)=Ο(f)；
5. Ο(Cf(N))=Ο(f(N))，其中C是一个正的常数；
6. f=Ο(f)；

规则1的证明：

设F(N)=Ο(f) 。根据记号Ο的定义，存在正常数C₁和自然数N₁，使得对所有的N≥N₁，有F(N)≤C₁f(N)。类似地，设G(N)=Ο(g)，则存在正的常数C₂和自然数N₂使得对所有的N≥N₂有G(N)≤C₂g(N)，今令：

4E-M1kk
z0C₃=max(C₁,C₂)

N₃=max(N₁,N₂)51Testing软件测试网;p4P O0S:p*oj1Q wT5]Q;[

和对任意的非负整数N，

h(N)=max(f,g),51Testing软件测试网3X/I9b@9NY~

则对所有的N≥N₃有：

O.y _?0t:_"a0F(N)≤C₁f(N)≤C₁h(N)≤C₃h(N)51Testing软件测试网\ o[4JU[4| J:l&i

类似地，有：51Testing软件测试网8lk"V4{y)]

G(N)≤C₂g(N)≤C₂h(N)≤C₃h(N)51Testing软件测试网:f ^ILz\k0?np

因而

Ο(f)+Ο(g) =F(N)+G(N)≤C₃h(N)+C₃h(N)51Testing软件测试网 F*H+t)jFG5@Il/p

51Testing软件测试网W L:uH(Q"p E8`

 =2C₃h(N)

Aac:t7~051Testing软件测试网3b L
Y s P9BL

 =Ο(h)

?7m6|x}E051Testing软件测试网P$l @]+bpX-W:} \t

 =Ο(max(f,g))51Testing软件测试网/X.N0u4OT!g&L)^ U M

其余规则的证明类似，请读者自行证明。51Testing软件测试网"Y C.|uq@+H/e

应用这些规则的一个例子：对于第一章中的算法search，在第二章给出了它的最坏情况下时间复杂性T_max(m)和平均情况下的时间复杂性T_avg(m)的表达式。如果利用上述规则，立即有:

T_max(m)=Ο(m)51Testing软件测试网
e0G$bsa7O0d3]

和T_avg(m)=Ο(m)+Ο(m)+Ο(m)=Ο(m)51Testing软件测试网m2i~.\(k^,L.|F

另一个例子：估计下面二重循环算法段在最坏情况下的时间复杂性T(N)的阶。

for i:=l to N do
  for j:=1 to i do
    begin
     S1;
     S2;
     S3;
     S4;
    end;

其中S_k(k=1,2,3,4)是单一的赋值语句。对于内循环体，显然只需Ο(l)时间。因而内循环只需

hH#X'x6tc5p*|051Testing软件测试网G6e4MG,{5MR&a/_7b.p`

时间。累加起来便是外循环的时间复杂性：51Testing软件测试网h.B
BDQ;D'j1VLu7^-v

qr(r dUhQ(tH&M0

应该指出，根据记号Ο的定义，用它评估算法的复杂性，得到的只是当规模充分大时的一个上界。这个上界的阶越低则评估就越精确，结果就越有价值。51Testing软件测试网 V3v U,F/?.r,b@$M

O.pq
CKQ9^_0关于记号Ω，文献里有两种不同的定义。本文只采用其中的一种，定义如下：如果存在正的常数C和自然数N₀，使得当N≥N₀时有f(N)≥Cg(N)，则称函数f(N)当N充分大时下有界，且g(N)是它的一个下界，记为f(N)=Ω(g(N))。这时我们还说f(N)的阶不低于g(N)的阶。

)|7vA+E!@x j0Ω的这个定义的优点是与Ο的定义对称，缺点是当f(N)对自然数的不同无穷子集有不同的表达式，且有不同的阶时，未能很好地刻画出f(N)的下界。比如当：

51Testing软件测试网1t2~J8I.{ w

时，如果按上述定义，只能得到f(N)=Ω(1)，这是一个平凡的下界，对算法分析没有什么价值。51Testing软件测试网e2sCo"iy1L6H

g,PZF-H V0然而，考虑到Ω的上述定义有与Ο的定义的对称性，又考虑到常用的算法都没出现上例中那种情况，所以本文还是选用它。51Testing软件测试网N#R,KK-y-C)l

我们同样也可以列举Ω的一些运算规则。但这里从略，只提供一个应用的例子。还是考虑算法Search在最坏情况下的时间复杂性函数T_max(m)。由它的表达式(2.7)及已知a,s,t均为大于0的常数，可推得，当m≥1时有：

4^"g
Em%w$mdr0T_max(m)≥(m+1)a+(2m+1)t>ma+2mt=(a+2t)m，

于是T_max(m)=Ω(m)。51Testing软件测试网5Ew[dZP3u

(V4t"ONR6RM0我们同样要指出，用Ω评估算法的复杂性，得到的只是该复杂性的一个下界。这个下界的阶越高，则评估就越精确，结果就越有价值。再则，这里的Ω只对问题的一个算法而言。如果它是对一个问题的所有算法或某类算法而言，即对于一个问题和任意给定的充分大的规模N，下界在该问题的所有算法或某类算法的复杂性中取，那么它将更有意义。这时得到的相应下界，我们称之为问题的下界或某类算法的下界。它常常与Ο配合以证明某问题的一个特定算法是该问题的最优算法或该问题在某算法类中的最优算法。

明白了记号Ο和Ω之后，记号θ将随之清楚，因为我们定义f(N)=θ(g(N))则f(N)=Ο(g(N)) 且f(N)=Ω(g(N))。这时，我们说f(N)与g(N)同阶。比如，对于算法Search在最坏情况下的时间复杂性T_max(m)。已有T_max(m)=Ο(m)和T_max(m)=Ω(m)，所以有T_max(m)=θ(m)，这是对T_max(m)的阶的精确估计。

yyF}8bd#l0最后，如果对于任意给定的ε≥0，都存在非负整数N₀，使得当N≥N₀时有f(N)≤εg(N)，则称函数f(N)当N充分大时比g(N)低阶，记为f(N)=o(g(N))，例如：

4NlogN+7=o(3N²+4NlogN+7)；而f(N)=ω(g(N))定义为g(N)=o(f(N))。

即当N充分大时f(N)的阶比g(N)高。我们看到o对于Ο有如ω对于Ω。51Testing软件测试网 Z EUhi
os