[转帖]算法的复杂性

vibration · 发表于 2005-9-15 07:33

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？我要加入

x

傅清祥王晓东 <CITE>算法与数据结构</CITE> , 电子工业出版社,1998
摘要
本文介绍了算法的复杂性的概念和衡量方法，并提供了一些计算算法的复杂性的渐近阶的方法。
目录
<UL>
<LI>简介 
<LI>比较两对算法的效率 
<LI>复杂性的计量 
<LI>复杂性的渐近性态及其阶 
<LI>复杂性渐近阶的重要性 
<LI>算法复杂性渐近阶的分析 
<LI>递归方程组的渐近阶的求法 
<LI>1.代入法 
<LI>2.迭代法 
<LI>3.套用公式法 
<LI>4.差分方程法 
<LI>5.母函数法 </LI></UL>

[此贴子已经被作者于2005-9-15 7:33:41编辑过]

vibration · 发表于 2005-9-15 07:34

<H2>简介</H2>
<DFN>算法的复杂性</DFN>是算法效率的度量，是评价算法优劣的重要依据。一个算法的复杂性的高低体现在运行该算法所需要的计算机资源的多少上面，所需的资源越多，我们就说该算法的复杂性越高；反之，所需的资源越低，则该算法的复杂性越低。 
计算机的资源，最重要的是时间和空间（即存储器）资源。因而，算法的复杂性有<DFN>时间复杂性</DFN>和<DFN>空间复杂性</DFN>之分。 
不言而喻，对于任意给定的问题，设计出复杂性尽可能地的算法是我们在设计算法是追求的一个重要目标；另一方面，当给定的问题已有多种算法时，选择其中复杂性最低者，是我们在选用算法适应遵循的一个重要准则。因此，算法的复杂性分析对算法的设计或选用有着重要的指导意义和实用价值。 
关于算法的复杂性，有两个问题要弄清楚： 
<OL>
<LI>用怎样的一个量来表达一个算法的复杂性； 
<LI>对于给定的一个算法，怎样具体计算它的复杂性。 </LI></OL>
让我们从比较两对具体算法的效率开始。

[此贴子已经被作者于2005-9-15 7:34:33编辑过]

vibration · 发表于 2005-9-15 07:34

<H2>比较两对算法的效率</H2>
考虑问题1：已知不重复且已经按从小到大排好的m个整数的数组A[1..m]（为简单起见。还设m=2 k，k是一个确定的非负整数）。对于给定的整数c，要求寻找一个下标i，使得A=c；若找不到，则返回一个0。
问题1的一个简单的算法是：从头到尾扫描数组A。照此，或者扫到A的第i个分量，经检测满足A=c；或者扫到A的最后一个分量，经检测仍不满足A=c。我们用一个函数Search来表达这个算法：<PRE><CODE>Function Search (c:integer):integer; Var J:integer; Begin J:=1; {初始化} {在还没有到达A的最后一个分量且等于c的分量还没有找到时， 查找下一个分量并且进行检测} While (A<c)and(j<m) do j:=j+1; If A[j]=c then search:=j {在数组A中找到等于c的分量，且此分量的下标为j} else Search:=0; {在数组中找不到等于c的分量} End;</CODE></PRE>
容易看出，在最坏的情况下，这个算法要检测A的所有m个分量才能判断在A中找不到等于c的分量。
解决问题1的另一个算法利用到已知条件中A已排好序的性质。它首先拿A的中间分量A[m/2]与c比较，如果A[m/2]=c则解已找到。如果A[m/2]>c，则c只可能在A[1],A[2],..,A[m/2-1]之中，因而下一步只要在A[1], A[2], .. ，A[m/2-1]中继续查找；如果A[m/2]<c，则c只可能在A[m/2+1],A[m/2+2],..,A[m]之中，因而下一步只要在A[m/2+1],A[m/2+2],..,A[m]中继续查找。不管哪一种情形，都把下一步需要继续查找的范围缩小了一半。再拿这一半的子数组的中间分量与c比较，重复上述步骤。照此重复下去，总有一个时候，或者找到一个i使得A=c，或者子数组为空（即子数组下界大于上界）。前一种情况找到了等于c的分量，后一种情况则找不到。
这个新算法因为有反复把供查找的数组分成两半，然后在其中一半继续查找的特征，我们称为二分查找算法。它可以用函数B_Search来表达： <PRE><CDOE>Function B_Search ( c: integer):integer; Var L,U,I : integer; {U和L分别是要查找的数组的下标的上界和下界} Found: boolean; Begin L:=1; U:=m; {初始化数组下标的上下界} Found:=false; {当前要查找的范围是A[L]..A[U]。} {当等于c的分量还没有找到且U>=L时，继续查找} While (not Found) and (U>=L) do Begin I:=(U+L) div 2; {找数组的中间分量} If c=A[I] then Found:=Ture else if c>A[I] then L:=I+1 else U:=I-1; End; If Found then B_Search:=1 else B_Search:=0; End;</PRE>
容易理解，在最坏的情况下最多只要测A中的k+1(k=logm,这里的log以2为底，下同)个分量，就判断c是否在A中。<img src="http://algorithm.diy.myrice.com/algorithm/complexity/images/img1.gif">
算法Search和B_Search解决的是同一个问题，但在最坏的情况下（所给定的c不在A中），两个算法所需要检测的分量个数却大不相同，前者要m=2 k个，后者只要k+1个。可见算法B_Search比算法Search高效得多。
以上例子说明：解同一个问题，算法不同，则计算的工作量也不同，所需的计算时间随之不同，即复杂性不同。
上图是运行这两种算法的时间曲线。该图表明，当m适当大（m>m0）时，算法B_Search比算法Search省时，而且当m更大时，节省的时间急剧增加。
不过，应该指出：用实例的运行时间来度量算法的时间复杂性并不合适，因为这个实例时间与运行该算法的实际计算机性能有关。换句话说，这个实例时间不单纯反映算法的效率而是反映包括运行该算法的计算机在内的综合效率。我们引入算法复杂性的概念是为了比较解决同一个问题的不同算法的效率，而不想去比较运行该算法的计算机的性能。因而，不应该取算法运行的实例时间作为算法复杂性的尺度。我们希望，尽量单纯地反映作为算法精髓的计算方法本身的效率，而且在不实际运行该算法的情况下就能分析出它所需要的时间和空间。

[此贴子已经被作者于2005-9-15 7:34:49编辑过]

vibration · 发表于 2005-9-15 07:35

<H2>复杂性的计量</H2>
算法的复杂性是算法运行所需要的计算机资源的量，需要的时间资源的量称作时间复杂性，需要的空间（即存储器）资源的量称作空间复杂性。这个量应该集中反映算法中所采用的方法的效率，而从运行该算法的实际计算机中抽象出来。换句话说，这个量应该是只依赖于算法要解的问题的规模、算法的输入和算法本身的函数。如果分别用N、I和A来表示算法要解问题的规模、算法的输入和算法本身，用C表示算法的复杂性，那么应该有：
C =F(N,I,A)
其中F(N,I,A)是N,I,A的一个确定的三元函数。如果把时间复杂性和空间复杂性分开，并分别用T和S来表示，那么应该有：
T =T(N,I,A) (2.1)
和 S =S(N,I,A) (2.2)
通常，我们让A隐含在复杂性函数名当中，因而将（2.1）和（2.2）分别简写为
T =T(N,I)
和 S =S(N,I)
由于时间复杂性和空间复杂性概念类同，计算方法相似，且空间复杂性分析相对地简单些，所以下文将主要地讨论时间复杂性。
下面以T(N,I)为例，将复杂性函数具体化。
根据T(N,I)的概念，它应该是算法在一台抽象的计算机上运行所需的时间。设此抽象的计算机所提供的元运算有k种，他们分别记为O1,O2 ,..,Ok；再设这些元运算每执行一次所需要的时间分别为t1,t2,..,tk 。对于给定的算法A，设经过统计，用到元运算Oi的次数为ei，i=1,2,..,k ，很明显，对于每一个i，1<=i<=k，ei是N和I的函数，即ei=ei(N,I)。那么有：
<img src="http://algorithm.diy.myrice.com/algorithm/complexity/images/img2.gif"> (2.3)
其中ti，i=1,2,..,k,是与N,I无关的常数。
显然，我们不可能对规模N的每一种合法的输入I都去统计ei(N,I),i=1,2,…,k。因此T(N,I)的表达式还得进一步简化，或者说，我们只能在规模为N的某些或某类有代表性的合法输入中统计相应的ei , i=1,2,…,k，评价时间复杂性。
下面只考虑三种情况的复杂性，即最坏情况、最好情况和平均情况下的时间复杂性，并分别记为Tmax(N )、Tmin(N)和Tavg(N )。在数学上有：
<img src="http://algorithm.diy.myrice.com/algorithm/complexity/images/img5.gif"> (2.4)
<img src="http://algorithm.diy.myrice.com/algorithm/complexity/images/img7.gif"> (2.5)
<img src="http://algorithm.diy.myrice.com/algorithm/complexity/images/img9.gif"> (2.6)
其中，DN是规模为N的合法输入的集合；I *是DN中一个使T(N,I *)达到Tmax(N)的合法输入，<img src="http://algorithm.diy.myrice.com/algorithm/complexity/images/img11.gif">是DN中一个使T(N,<img src="http://algorithm.diy.myrice.com/algorithm/complexity/images/img12.gif">)到Tmin(N)的合法输入；而P(I)是在算法的应用中出现输入I 的概率。
以上三种情况下的时间复杂性各从某一个角度来反映算法的效率，各有各的用处，也各有各的局限性。但实践表明可操作性最好的且最有实际价值的是最坏情况下的时间复杂性。下面我们将把对时间复杂性分析的主要兴趣放在这种情形上。
一般来说，最好情况和最坏情况的时间复杂性是很难计量的，原因是对于问题的任意确定的规模N达到了Tmax(N)的合法输入难以确定，而规模N的每一个输入的概率也难以预测或确定。我们有时也按平均情况计量时间复杂性，但那时在对P(I)做了一些人为的假设（比如等概率）之后才进行的。所做的假设是否符合实际总是缺乏根据。因此，在最好情况和平均情况下的时间复杂性分析还仅仅是停留在理论上。
现在以<a href="http://algorithm.diy.myrice.com/algorithm/complexity/chapter1.htm" target="_blank" >上一章</A>提到的<a href="http://algorithm.diy.myrice.com/algorithm/complexity/chapter1.htm#pro1" target="_blank" >问题1</A>的<a href="http://algorithm.diy.myrice.com/algorithm/complexity/chapter1.htm#search" target="_blank" >算法Search</A>为例来说明如何利用(2.4)-(2.6)对它的Tmax、Tmin和Tavg进行计量。这里问题的规模以m计算，算法重用到的元运算有赋值、测试和加法等三种，它们每执行一次所需的时间常数分别为a,t,和s 。对于这个例子，如假设c在A中，那么容易直接看出最坏情况的输入出现在c=A[m]的情形，这时：
Tmax(m)=a+2mt+(m-1)s+(m-1)a+t+a=(m+1)a+(2m+1)t+(m-1)s (2.7)
而最好情况的输入出现在c=A[1]的情形。这时：
<img src="http://algorithm.diy.myrice.com/algorithm/complexity/images/img15.gif"> (2.8)
至于Tavg(m)，如前所述，必须对Dm上的概率分布做出假设才能计量。为简单起见，我们做最简单的假设：Dm上的概率分布是均等的，即P(A=c)=1/m 。若记Ti=T(m,Ii)，其中Ii表示A=c的合法输入，那么：
<img src="http://algorithm.diy.myrice.com/algorithm/complexity/images/img18.gif"> (2.9)
而根据与(2.7)类似的推导，有：
<img src="http://algorithm.diy.myrice.com/algorithm/complexity/images/img21.gif">
代入(2.9) ，则：
<img src="http://algorithm.diy.myrice.com/algorithm/complexity/images/img23.gif">
这里碰巧有：
Tavg(m)=(Tmax(m)+Tmin(m))/2
但必须指出，上式并不具有一般性。
类似地，对于算法B_Search照样可以按(2.4)-(2.6)计算相应的Tmax(m)、Tmin(m)和Tavg(m) 。不过，我们这里只计算Tmax(m) 。为了与Search比较，仍假设c在A中，即最坏情况的输入仍出现在c=A[m]时。这时，while循环的循环体恰好被执行了logm +1 即k+1 次。因为第一次执行时数据的规模为m，第二次执行时规模为m/2等等，最后一次执行时规模为1。另外，与Search少有不同的是这里除了用到赋值、测试和加法三种原运算外，还用到减法和除法两种元运算。补记后两种元运算每执行一次所需时间为b和d ，则可以推演出：
<img src="http://algorithm.diy.myrice.com/algorithm/complexity/images/img25.gif"> (2.10)
比较(2.7)和(2.10) ，我们看到m充分大时，在最坏情况下B_Search的时间复杂性远小于Search的时间复杂性。

vibration · 发表于 2005-9-15 07:35

<H2>复杂性的渐近性态及其阶</H2>
随着经济的发展、社会的进步、科学研究的深入，要求用计算机解决的问题越来越复杂，规模越来越大。但是，如果对这类问题的算法进行分析用的是第二段所提供的方法，把所有的元运算都考虑进去，精打细算，那么，由于问题的规模很大且结构复杂，算法分析的工作量之大、步骤之繁将令人难以承受。因此，人们提出了对于规模充分大、结构又十分复杂的问题的求解算法，其复杂性分析应如何简化的问题。
我们先要引入复杂性渐近性态的概念。设T(N)是在第二段中所定义的关于算法A的复杂性函数。一般说来，当N单调增加且趋于∞时,T(N)也将单调增加趋于∞。对于T(N)，如果存在T’(N)，使得当N→∞时有：
(T(N )-T’(N ))/T(N ) → 0
那么，我们就说T’(N)是T(N)当N→∞时的<DFN>渐近性态</DFN>，或叫T’(N)为算法A当N→∞的<DFN>渐近复杂性</DFN>而与T(N)相区别，因为在数学上，T’(N)是T(N)当N→∞时的渐近表达式。
直观上，T’(N)是T(N)中略去低阶项所留下的主项。所以它无疑比T(N)来得简单。比如当
T(N)=3N 2+4Nlog2N +7
时，T’(N)的一个答案是3N 2，因为这时有：
<img src="http://algorithm.diy.myrice.com/algorithm/complexity/images/img3.gif">
显然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)是它的一个<DFN>上界</DFN>，记为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)。
按照大Ο的定义，容易证明它有如下运算规则：
<OL>
<LI>Ο(f)+Ο(g)=Ο(max(f,g))；
<LI>Ο(f)+ Ο(g)=Ο(f +g)；
<LI>Ο(f)·Ο(g)= Ο(f·g)；
<LI>如果g(N)= Ο(f(N))，则Ο(f)+ Ο(g)= Ο(f)；
<LI>Ο(Cf(N))= Ο(f(N))，其中C是一个正的常数；
<LI>f =Ο(f)； </LI></OL>
规则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)
<BLOCKQUOTE>
<BLOCKQUOTE>
 =2C3h(N)
 =Ο(h)
 =Ο(max(f,g))</BLOCKQUOTE></BLOCKQUOTE>
其余规则的证明类似，请读者自行证明。
应用这些规则的一个例子：对于<a href="http://algorithm.diy.myrice.com/algorithm/complexity/chapter1.htm#search" target="_blank" >第一章中的算法search</A>，在<a href="http://algorithm.diy.myrice.com/algorithm/complexity/chapter2.htm" target="_blank" >第二章</A>给出了它的最坏情况下时间复杂性Tmax(m)和平均情况下的时间复杂性Tavg(m)的表达式。如果利用上述规则，立即有:
Tmax(m)=Ο(m)
和 Tavg(m)=Ο(m)+Ο(m)+Ο(m)=Ο(m)
另一个例子：估计下面二重循环算法段在最坏情况下的时间复杂性T(N)的阶。<PRE><CODE>for i:=l to N do
 for j:=1 to i do
begin
 S1;
 S2;
 S3;
 S4;
end;</CODE></PRE>
其中Sk (k=1,2,3,4)是单一的赋值语句。对于内循环体，显然只需Ο(l)时间。因而内循环只需
<img src="http://algorithm.diy.myrice.com/algorithm/complexity/images/img6.gif">
时间。累加起来便是外循环的时间复杂性：
<img src="http://algorithm.diy.myrice.com/algorithm/complexity/images/img8.gif">
应该指出，根据记号Ο的定义，用它评估算法的复杂性，得到的只是当规模充分大时的一个上界。这个上界的阶越低则评估就越精确，结果就越有价值。
关于记号Ω，文献里有两种不同的定义。本文只采用其中的一种，定义如下：如果存在正的常数C和自然数N0，使得当N≥N0时有f(N)≥Cg(N)，则称函数f(N)当N充分大时<DFN>下有界</DFN>，且g(N)是它的一个<DFN>下界</DFN>，记为f(N)=Ω(g(N))。这时我们还说f(N)的阶不低于g(N)的阶。
Ω的这个定义的优点是与Ο的定义对称，缺点是当f(N)对自然数的不同无穷子集有不同的表达式，且有不同的阶时，未能很好地刻画出f(N)的下界。比如当：
<img src="http://algorithm.diy.myrice.com/algorithm/complexity/images/img10.gif">
时，如果按上述定义，只能得到f(N)=Ω(1)，这是一个平凡的下界，对算法分析没有什么价值。
然而，考虑到Ω的上述定义有与Ο的定义的对称性，又考虑到常用的算法都没出现上例中那种情况，所以本文还是选用它。
我们同样也可以列举Ω的一些运算规则。但这里从略，只提供一个应用的例子。还是考虑<a href="http://algorithm.diy.myrice.com/algorithm/complexity/chapter1.htm#search" target="_blank" >算法Search</A>在最坏情况下的时间复杂性函数Tmax(m)。由它的<a href="http://algorithm.diy.myrice.com/algorithm/complexity/chapter2.htm#equ2_7" target="_blank" >表达式(2.7)</A>及已知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)<DFN>同阶</DFN>。比如，对于算法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)<DFN>低阶</DFN>，记为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对于Ο有如ω对于Ω。

vibration · 发表于 2005-9-15 07:36

<H2>复杂性渐近阶的重要性</H2>
计算机的设计和制造技术在突飞猛进，一代又一代的计算机的计算速度和存储容量在直线增长。有的人因此认为不必要再去苦苦地追求高效率的算法，从而不必要再去无谓地进行复杂性的分析。他们以为低效的算法可以由高速的计算机来弥补，以为在可接受的一定时间内用低效的算法完不成的任务，只要移植到高速的计算机上就能完成。这是一种错觉。造成这种错觉的原因是他们没看到：随着经济的发展、社会的进步、科学研究的深入，要求计算机解决的问题越来越复杂、规模越来越大，也呈线性增长之势；而问题复杂程度和规模的线性增长导致的时耗的增长和空间需求的增长，对低效算法来说，都是超线性的，决非计算机速度和容量的线性增长带来的时耗减少和存储空间的扩大所能抵销。事实上，我们只要对效率上有代表性的几个档次的算法作些简单的分析对比就能明白这一点。
我们还是以时间效率为例。设A1,A2,…和A6。是求解同一间题的6个不同的算法，它们的渐近时间复杂性分别为N，NlogN，N 2，N 3，2N，N!。让这六种算法各在C1和C2两台计算机上运行，并设计算机C2的计算速度是计算机C1的10倍。在可接受的一段时间内，设在C1上算法Ai可能求解的问题的规模为N1i，而在C2上可能求解的问题的规模为N2i，那么，我们就应该有Ti(N2i)=10Ti(N1i)，其中Ti(N)是算法Ai渐近的时间复杂性，i=1,2,…,6。分别解出N2i和N1i的关系，可列成下表：
表4-1算法与渐近时间复杂性的关系
<TABLE cellSpacing=0 width="95%" align=center border=1>

<TR>
<TH align=middle width="6%">算法</TH>
<TH align=middle width="23%">渐进时间复杂性T(N)</TH>
<TH align=middle width="24%">在C1上可解的规模N1</TH>
<TH align=middle width="23%">在C2上可解的规模N2</TH>
<TH align=middle width="24%">N1和N2的关系</TH></TR>
<TR>
<TD align=middle width="6%">A1</TD>
<TD align=middle width="23%">N</TD>
<TD align=middle width="24%">N11</TD>
<TD align=middle width="23%">N21</TD>
<TD align=middle width="24%">N21=10N11</TD></TR>
<TR>
<TD align=middle width="6%">A2</TD>
<TD align=middle width="23%">NlogN</TD>
<TD align=middle width="24%">N12</TD>
<TD align=middle width="23%">N22</TD>
<TD align=middle width="24%">N22≈10N12</TD></TR>
<TR>
<TD align=middle width="6%">A3</TD>
<TD align=middle width="23%">N2</TD>
<TD align=middle width="24%">N13</TD>
<TD align=middle width="23%">N23</TD>
<TD align=middle width="24%"><img src="http://algorithm.diy.myrice.com/algorithm/complexity/images/img96.gif"></TD></TR>
<TR>
<TD align=middle width="6%">A4</TD>
<TD align=middle width="23%">N3</TD>
<TD align=middle width="24%">N14</TD>
<TD align=middle width="23%">N24</TD>
<TD align=middle width="24%"><img src="http://algorithm.diy.myrice.com/algorithm/complexity/images/img98.gif"></TD></TR>
<TR>
<TD align=middle width="6%">A5</TD>
<TD align=middle width="23%">2N</TD>
<TD align=middle width="24%">N15</TD>
<TD align=middle width="23%">N25</TD>
<TD align=middle width="24%">N25 =N15+log10</TD></TR>
<TR>
<TD align=middle width="6%">A6</TD>
<TD align=middle width="23%">N!</TD>
<TD align=middle width="24%">N16</TD>
<TD align=middle width="23%">N26</TD>
<TD align=middle width="24%">N26 =N16+小的常数</TD></TR></TABLE>
从表4-1的最后一列可以清楚地看到，对于高效的算法A1，计算机的计算速度增长10倍，可求解的规模同步增长10倍；对于A2，可求解的问题的规模的增长与计算机的计算速度的增长接近同步；但对于低效的算法A3，情况就大不相同，计算机的计算速度增长10倍只换取可求解的问题的规模增加log10。当问题的规模充分大时，这个增加的数字是微不足道的。换句话说，对于低效的算法，计算机的计算速度成倍乃至数10倍地增长基本上不带来求解规模的增益。因此，对于低效算法要扩大解题规模，不能寄希望于移植算法到高速的计算机上，而应该把着眼点放在算法的改进上。
从表4-l的最后一列我们还看到，限制求解问题规模的关键因素是算法渐近复杂性的阶，对于表中的前四种算法，其渐近的时间复杂性与规模N的一个确定的幂同阶，相应地，计算机的计算速度的乘法增长带来的是求解问题的规模的乘法增长，只是随着幂次的提高，规模增长的倍数在降低。我们把渐近复杂性与规模N的幂同阶的这类算法称为多项式算法。对于表中的后两种算法，其渐近的时间复杂性与规模N的一个指数函数同阶，相应地计算机的计算速度的乘法增长只带来求解问题规模的加法增长。我们把渐近复杂性与规模N的指数同阶的这类算法称为指数型算法。多项式算法和指数型算法是在效率上有质的区别的两类算法。这两类算法的区别的内在原因是算法渐近复杂性的阶的区别。可见，算法的渐近复杂性的阶对于算法的效率有着决定性的意义。所以在讨论算法的复杂性时基本上都只关心它的渐近阶。
多项式算法是有效的算法。绝大多数的问题都有多项式算法。但也有一些问题还未找到多项式算法，只找到指数型算法。
我们在讨论算法复杂性的渐近阶的重要性的同时，有两条要记住：
<OL>
<LI>“复杂性的渐近阶比较低的算法比复杂性的渐近阶比较高的算法有效”这个结论，只是在问题的求解规模充分大时才成立。比如算法A4比A5有效只是在N 3<2N，即N≥c 时才成立。其中c是方程N 3=2N的解。当N <c时，A5反而比A4有效。所以对于规模小的问题，不要盲目地选用复杂性阶比较低的算法。其原因一方面是如上所说，复杂性阶比较低的算法在规模小时不一定比复杂性阶比较高的算法更有效；另方面，在规模小时，决定工作效率的可能不是算法的效率而是算法的简单性，哪一种算法简单，实现起来快，就选用那一种算法。
<LI>当要比较的两个算法的渐近复杂性的阶相同时，必须进一步考察渐近复杂性表达式中常数因子才能判别它们谁好谁差。显然常数因子小的优于常数因子大的算法。比如渐近复杂性为N1ogN/l00的算法显然比渐近复杂性为l00NlogN的算法来得有效。 </LI></OL>

vibration · 发表于 2005-9-15 07:36

<H2>算法复杂性渐近阶的分析</H2>
前两段讲的是算法复杂性渐近阶的概念和对它进行分析的重要性。本段要讲如何具体地分析一个算法的复杂性的渐近阶，给出一套可操作的规则。算法最终要落实到用某种程序设计语言（如Pascal）编写成的程序。因此算法复杂性渐近阶的分析可代之以对表达该算法的程序的复杂性渐近阶的分析。
如前所提出，对于算法的复杂性，我们只考虑最坏、最好和平均三种情况，而通常又着重于最坏情况。为了明确起见，本段限于针对最坏情况。
仍然以时间复杂性为例。这里给出分析时间复杂性渐近阶的八条规则。这八条规则已覆盖了用Pascal语言程序所能表达的各种算法在最坏情况下的时间复杂性渐近阶的分析。
在逐条地列出并解释这入条规则之前，应该指出，当我们分析程序的某一局部(如一个语句，一个分程序，一个程序段，一个过程或函数)时，可以用具体程序的输入的规模N作为复杂性函数的自变量，也可以用局部的规模参数作为自变量。但是，作为最终结果的整体程序的复杂性函数只能以整体程序的输入规模为自变量。
对于串行的算法，相应的Pascal程序是一个串行的Pascal语句序列，因此，很明显，该算法的时间复杂性(即所需要的时间)等于相应的Pascal程序的每一个语句的时间复杂性(即所需要的时间)之和。所以，如果执行Pascal语句中的每一种语句所需要的时间都有计量的规则，那么，执行一个程序，即执行一个算法所需要的时间的计量便只是一个代数问题。接着，应用本节第三段所提供的Ο、Ω和θ等运算规则就可以分析出算法时间复杂性的渐近阶。
因此，我们的时间计量规则只需要针对Pascal有限的几种基本运算和几种基本语句。下面是这些规则的罗列和必要的说明。
<DL>
<DT>规则(1) </DT></DL>
赋值、比较、算术运算、逻辑运算、读写单个常量或单个变量等，只需要1个单位时间。
<DL>
<DT>规则(2) </DT></DL>
条件语句"if C then S1 else S2"只需要Tc+max(Ts1，Ts2)的时间，其中Tc是计算条件表达式C需要的时间，而Ts1和Ts2分别是执行语句S1和S2需要的时间。
<DL>
<DT>规则(3) </DT></DL>
选择语句"Case A of a1:S1; a2:S2; … ;am:Sm; end"，需要max(Ts1, Ts2，…，Tsm)的时间，其中Tsii是执行语句Si所需要的时间，i=l,2,…,m。
<DL>
<DT>规则(4) </DT></DL>
访问一个数组的单个分量或一个记录的单个域，只需要1个单位时间。
<DL>
<DT>规则(5) </DT></DL>
执行一个for循环语句需要的时间等于执行该循环体所需要的时间乘上循环的次数。
<DL>
<DT>规则(6) </DT></DL>
执行一个while循环语句"while C do S"或一个repeat循环语句" repeat S until C"，需要的时间等于计算条件表达式C需要的时间与执行循环S体需要的时间之和乘以循环的次数。与规则5不同，这里的循环次数是隐含的。
例如，b_search函数中的while循环语句。按规则(1)-(4)，计算条件表达式" (not found)and(U≥=L)"与执行循环体<PRE><CODE>I:=(U+L)div 2;
if c=A[I] then found:=true
 else if c>A[I] then L:=I+1
 else U:=I-1;</CODE></PRE>
只需要θ(1)时间，而循环次数为logm，所以，执行此while语句只需要θ(logm)时间。
在许多情况下，运用规则(5)和(6)常常须要借助具体算法的内涵来确定循环的次数，才不致使时间的估计过于保守。这里举一个例子。
考察程序段：
<DIV align=center>
<TABLE height=275 cellSpacing=0 cellPadding=0 width="90%" bgColor=#e0e0e0 border=0>

<TR>
<CENTER>
<TD vAlign=top width=515 height=9>　</TD></CENTER>
<TD vAlign=top align=middle width=72 height=9>　</TD></TR>
<TR>
<TD vAlign=top width=515 height=9>
Size:=m;</TD>
<TD vAlign=top align=middle width=72 height=9>1</TD></TR>
<TR>
<CENTER>
<TD vAlign=top width=515 height=18>
i:=1;</TD></CENTER>
<TD vAlign=top align=middle width=72 height=18>1</TD></TR>
<CENTER>
<TR>
<TD vAlign=top width=515 height=18>
while i<n do</TD>
<TD vAlign=top align=middle width=72 height=18> </TD></TR>
<TR>
<TD vAlign=top width=515 height=18>
 begin</TD>
<TD vAlign=top align=middle width=72 height=18> </TD></TR>
<TR>
<TD vAlign=top width=515 height=18>
 i:=i+1;</TD>
<TD vAlign=top align=middle width=72 height=18> </TD></TR></CENTER>
<TR>
<CENTER>
<TD vAlign=top width=515 height=21>
 S1;</TD></CENTER>
<TD vAlign=top align=middle width=72 height=21>θ(n)</TD></TR>
<TR>
<CENTER>
<TD vAlign=top width=515 height=18>
 if Size>0 then</TD></CENTER>
<TD vAlign=top align=middle width=72 height=18>1</TD></TR>
<CENTER>
<TR>
<TD vAlign=top width=515 height=18>
 begin</TD>
<TD vAlign=top align=middle width=72 height=18> </TD></TR></CENTER>
<TR>
<CENTER>
<TD vAlign=top width=515 height=18>
 在1到Size的范围内任选一个数赋值给t;</TD></CENTER>
<TD vAlign=top align=middle width=72 height=18>θ(1)</TD></TR>
<TR>
<CENTER>
<TD vAlign=top width=515 height=18>
 Size:=Size-t;</TD></CENTER>
<TD vAlign=top align=middle width=72 height=18>2</TD></TR>
<CENTER>
<TR>
<TD vAlign=top width=515 height=18>
 for j:=l to t do</TD>
<TD vAlign=top align=middle width=72 height=18> </TD></TR></CENTER>
<TR>
<CENTER>
<TD vAlign=top width=515 height=21>
 S2</TD></CENTER>
<TD vAlign=top align=middle width=72 height=21>θ(n)</TD></TR>
<CENTER>
<TR>
<TD vAlign=top width=515 height=18>
 end;</TD>
<TD vAlign=top align=middle width=72 height=18> </TD></TR>
<TR>
<TD vAlign=top width=515 height=18>
 end;</TD>
<TD vAlign=top align=middle width=72 height=18> </TD></TR></CENTER>
<TR>
<TD vAlign=top width=515 height=17>　</TD>
<TD vAlign=top align=middle width=72 height=17>　</TD></TR></TABLE></DIV>
程序在各行右端顶格处标注着执行相应各行所需要的时间。如果不对算法的内涵作较深入的考察，只看到1≤t≤Size≤m，就草率地估计while的内循环for的循环次数为Ο(m)，那么，程序在最坏情况下的时间复杂性将被估计为Ο(n 2+m·n 2)。反之，如果对算法的内涵认真地分析，结果将两样。事实上，在while的循环体内t是动态的,size也是动态的，它们都取决while的循环参数i，即t=t(i)记为ti；size=size(i)记为sizei ，i=l,2,…,n-1。对于各个i，1≤i≤n-1，ti与m的关系是隐含的，这给准确地计算for循环的循环体S2被执行的次数带来困难。上面的估计比较保守的原因在于我们把S2的执行次数的统计过于局部化。如果不局限于for循环，而是在整个程序段上统计S2被执行的总次数，那么，这个总次数等于<img src="http://algorithm.diy.myrice.com/algorithm/complexity/images/img13.gif">，又根据算法中ti的取法及sizei+1=sizei-ti，i=1,2,…,n-1 有sizen=size1-<img src="http://algorithm.diy.myrice.com/algorithm/complexity/images/img4.gif">。最后利用size1=m和sizen=0得到<img src="http://algorithm.diy.myrice.com/algorithm/complexity/images/img14.gif">=m 。于是在整个程序段上，S2被执行的总次数为m，所需要的时间为θ(mn)。执行其他语句所需要的时间直接运用规则(l)-(6)容易计算。累加起来，整个程序段在最坏情况下时间复杂性渐近阶为θ(n 2+mn)。这个结果显然比前面粗糙的估计准确。
<DL>
<DT>规则(7) </DT></DL>
对于goto语句。在Pascal中为了便于表达从循环体的中途跳转到循环体的结束或跳转到循环语句的后面语句，引入goto语句。如果我们的程序按照这一初衷使用goto语句，那么，在时间复杂性分析时可以假设它不需要任何额外的时间。因为这样做既不会低估也不会高估程序在最坏情况下的运行时间的阶。如果有的程序滥用了goto语句，即控制转移到前面的语句，那么情况将变得复杂起来。当这种转移造成某种循环时，只要与别的循环不交叉，保持循环的内外嵌套，则可以比照规则(1)-(6)进行分析。当由于使用goto语句而使程序结构混乱时，建议改写程序然后再做分析。
<DL>
<DT>规则(8) </DT></DL>
对于过程调用和函数调用语句，它们需要的时间包括两部分，一部分用于实现控制转移，另一部分用于执行过程(或函数)本身，这时可以根据过程(或函数)调用的层次，由里向外运用规则(l)-(7)进行分析，一层一层地剥，直到计算出最外层的运行时间便是所求。如果过程(或函数)出现直接或间接的递归调用，则上述由里向外逐层剥的分析行不通。这时我们可以对其中的各个递归过程(或函数)，所需要的时间假设为一个相应规模的待定函数。然后一一根据过程(或函数)的内涵建立起这些待定函数之间的递归关系得到递归方程。最后用求递归方程解的渐进阶的方法确定最坏情况下的复杂性的渐进阶。
递归方程的种类很多，求它们的解的渐近阶的方法也很多，我们将在下一段比较系统地给予介绍。本段只举一个简单递归过程(或函数)的例子来说明如何建立相应的递归方程，同时不加推导地给出它们在最坏情况下的时间复杂性的渐近阶。
例：再次考察函数b_search，这里将它改写成一个递归函数。为了简明，我们已经运用前面的规则(l)-(6)，统计出执行各行语句所需要的时间，并标注在相应行的右端：
<DIV align=center>
<CENTER>
<TABLE cellSpacing=0 cellPadding=0 width="95%" bgColor=#e0e0e0 border=0>

<TR>
<TD vAlign=top>
　</TD>
<TD vAlign=top align=middle width=120>
　</TD></TR>
<TR>
<TD vAlign=top>
Function b_search(C,L,U:integer):integer;</TD>
<TD vAlign=top align=middle width=120>
单位时间数</TD></TR>
<TR>
<TD vAlign=top>
var index,element:integer;</TD>
<TD vAlign=top align=middle width=120> </TD></TR>
<TR>
<TD vAlign=top>
 begin</TD>
<TD vAlign=top align=middle width=120> </TD></TR>
<TR>
<TD vAlign=top>
 if (U<L) then</TD>
<TD vAlign=top align=middle width=120>
 1</TD></TR>
<TR>
<TD vAlign=top>
 b_search:=0;</TD>
<TD vAlign=top align=middle width=120>
 1</TD></TR>
<TR>
<TD vAlign=top>
 else</TD>
<TD vAlign=top align=middle width=120> </TD></TR>
<TR>
<TD vAlign=top>
 begin</TD>
<TD vAlign=top align=middle width=120> </TD></TR>
<TR>
<TD vAlign=top>
 index:=(L+U) div 2;</TD>
<TD vAlign=top align=middle width=120>
 3</TD></TR>
<TR>
<TD vAlign=top>
 element:=A[index];</TD>
<TD vAlign=top align=middle width=120>
 2</TD></TR>
<TR>
<TD vAlign=top>
 if element=C then</TD>
<TD vAlign=top align=middle width=120>
 1</TD></TR>
<TR>
<TD vAlign=top>
 b_search:=index</TD>
<TD vAlign=top align=middle width=120>
 1</TD></TR>
<TR>
<TD vAlign=top>
 else if element>C then</TD>
<TD vAlign=top align=middle width=120> </TD></TR>
<TR>
<TD vAlign=top>
 b_search:=b_search(C,L,index-1)</TD>
<TD vAlign=top align=middle width=120>
 3+T(m/2)</TD></TR>
<TR>
<TD vAlign=top>
 else</TD>
<TD vAlign=top align=middle width=120> </TD></TR>
<TR>
<TD vAlign=top>
 b_search:=b_search(C,index+1,U);</TD>
<TD vAlign=top align=middle width=120>
 3+T(m/2)</TD></TR>
<TR>
<TD vAlign=top>
 end;</TD>
<TD vAlign=top align=middle width=120> </TD></TR>
<TR>
<TD vAlign=top>
 end;</TD>
<TD vAlign=top align=middle width=120> </TD></TR>
<TR>
<TD vAlign=top>　</TD>
<TD vAlign=top align=middle width=120>　</TD></TR></TABLE></CENTER></DIV>
其中T(m)是当问题的规模U-L+1=m时b_search在最坏情况下(这时，数组A[L..U]中没有给定的C)的时间复杂性。根据规则(l)-(8)，我们有：
<img src="http://algorithm.diy.myrice.com/algorithm/complexity/images/img16.gif">
或化简为
<img src="http://algorithm.diy.myrice.com/algorithm/complexity/images/img19.gif">
这是一个关于T(m)的递归方程。用下一段将介绍的迭代法，容易解得：
T(m)=11logm +l3=θ(logm)
在结束这一段之前，我们要提一下关于算法在最坏情况下的空间复杂性分析。我们照样可以给出与分析时间复杂性类似的规则。这里不赘述。然而应该指出，在出现过程(或函数)递归调用时要考虑到其中隐含的存储空间的额外开销。因为现有的实现过程(或函数)递归调用的编程技术需要一个隐含的、额外(即不出现在程序的说明中)的栈来支持。过程(或函数)的递归调用每深人一层就把本层的现场局部信息及调用的返回地址存放在栈顶备用，直到调用的最里层。因此递归调用一个过程(或函数)所需要的额外存储空间的大小即栈的规模与递归调用的深度成正比，其比例因子等于每深入一层需要保存的数据量。比如本段前面所举的递归函数b_search，在最坏情况下，递归调用的深度为logm，因而在最坏情况下调用它所需要的额外存储空间为θ(logm)。

vibration · 发表于 2005-9-15 07:37

<H2>递归方程解的渐近阶的求法</H2>
上一章所介绍的递归算法在最坏情况下的时间复杂性渐近阶的分析，都转化为求相应的一个递归方程的解的渐近阶。因此，求递归方程的解的渐近阶是对递归算法进行分析的关键步骤。
递归方程的形式多种多样，求其解的渐近阶的方法也多种多样。这里只介绍比较实用的五种方法。
<OL>
<LI>代入法 这个方法的基本步骤是先推测递归方程的显式解，然后用数学归纳法证明这一推测的正确性。那么，显式解的渐近阶即为所求。
<LI>迭代法 这个方法的基本步骤是通过反复迭代，将递归方程的右端变换成一个级数，然后求级数的和，再估计和的渐近阶；或者，不求级数的和而直接估计级数的渐近阶，从而达到对递归方程解的渐近阶的估计。
<LI>套用公式法 这个方法针对形如：T (n)=aT (n / b)+f (n) 的递归方程，给出三种情况下方程解的渐近阶的三个相应估计公式供套用。
<LI>差分方程法 有些递归方程可以看成一个差分方程，因而可以用解差分方程(初值问题)的方法来解递归方程。然后对得到的解作渐近阶的估计。
<LI>母函数法 这是一个有广泛适用性的方法。它不仅可以用来求解线性常系数高阶齐次和非齐次的递归方程，而且可以用来求解线性变系数高阶齐次和非齐次的递归方程，甚至可以用来求解非线性递归方程。方法的基本思想是设定递归方程解的母函数，努力建立一个关于母函数的可解方程，将其解出，然后返回递归方程的解。 </LI></OL>

账号		自动登录	找回密码
密码			我要加入

[经典算法] [转帖]算法的复杂性

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

回复：（vibration）[转帖]算法的复杂性

回复：（vibration）[转帖]算法的复杂性

回复：（vibration）[转帖]算法的复杂性

回复：（vibration）[转帖]算法的复杂性

回复：（vibration）[转帖]算法的复杂性

回复：（vibration）[转帖]算法的复杂性

回复：（vibration）[转帖]算法的复杂性