算法的复杂性

b · 发表于 2004-5-29 03:08:35

<H2>简介</H2>
<

><DFN> 算法的复杂性</DFN>是算法效率的度量，是评价算法优劣的重要依据。一个算法的复杂性的高低体现在运行该算法所需要的计算机资源的多少上面，所需的资源越多，我们就说该算法的复杂性越高；反之，所需的资源越低，则该算法的复杂性越低。 
<

>计算机的资源，最重要的是时间和空间（即存储器）资源。因而，算法的复杂性有<DFN>时间复杂性</DFN>和<DFN>空间复杂性</DFN>之分
<

> 不言而喻，对于任意给定的问题，设计出复杂性尽可能地的算法是我们在设计算法是追求的一个重要目标；另一方面，当给定的问题已有多种算法时，选择其中复杂性最低者，是我们在选用算法适应遵循的一个重要准则。因此，算法的复杂性分析对算法的设计或选用有着重要的指导意义和实用价值。
关于算法的复杂性，有两个问题要弄清楚： 
<OL>
<LI>用怎样的一个量来表达一个算法的复杂性；

<LI>对于给定的一个算法，怎样具体计算它的复杂性。 </LI></OL>
让我们从比较两对具体算法的效率开始。

b · 发表于 2004-5-29 03:12:56

<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来表达这个算法：

b · 发表于 2004-5-29 03:13:11

<

RE><CODE>Function Search (c:integer):integer;</CODE></PRE><

RE><CODE>
Var J:integer;</CODE></PRE><

RE><CODE>
Begin</CODE></PRE><PRE><CODE></CODE><CODE>J:=1; {初始化}</CODE><CODE>{在还没有到达A的最后一个分量且等于c的分量还没有找到时，</CODE><CODE>
查找下一个分量并且进行检测}
</CODE><CODE>While (A<c)and(j<m) do </CODE><CODE>
j:=j+1;
If A[j]=c then search:=j {在数组A中找到等于c的分量，且此分量的下标为j}
else Search:=0; {在数组中找不到等于c的分量}
End;</CODE></PRE>

b · 发表于 2004-5-29 03:15:43

<

>容易看出，在最坏的情况下，这个算法要检测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来表达：

b · 发表于 2004-5-29 03:15:54

<

>容易看出，在最坏的情况下，这个算法要检测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来表达：

b · 发表于 2004-5-29 03:16:03

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;

b · 发表于 2004-5-29 03:16:22

<

>容易理解，在最坏的情况下最多只要测A中的k+1(k=logm,这里的log以2为底，下同)个分量，就判断c是否在A中。<img src="http://algorithm.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更大时，节省的时间急剧增加。不过，应该指出：用实例的运行时间来度量算法的时间复杂性并不合适，因为这个实例时间与运行该算法的实际计算机性能有关。换句话说，这个实例时间不单纯反映算法的效率而是反映包括运行该算法的计算机在内的综合效率。我们引入算法复杂性的概念是为了比较解决同一个问题的不同算法的效率，而不想去比较运行该算法的计算机的性能。因而，不应该取算法运行的实例时间作为算法复杂性的尺度。我们希望，尽量单纯地反映作为算法精髓的计算方法本身的效率，而且在不实际运行该算法的情况下就能分析出它所需要的时间和空间。

<SCRIPT src="../../lib/footer.js">
<script>

复制代码

b · 发表于 2004-5-29 03:16:38

<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.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.myrice.com/algorithm/complexity/images/img5.gif"> (2.4)<img src="http://algorithm.myrice.com/algorithm/complexity/images/img7.gif"> (2.5)<img src="http://algorithm.myrice.com/algorithm/complexity/images/img9.gif"> (2.6)其中，DN是规模为N的合法输入的集合；I *是DN中一个使T(N,I *)达到Tmax(N)的合法输入，<img src="http://algorithm.myrice.com/algorithm/complexity/images/img11.gif">是DN中一个使T(N,<img src="http://algorithm.myrice.com/algorithm/complexity/images/img12.gif">)到Tmin(N)的合法输入；而P(I)是在算法的应用中出现输入I 的概率。以上三种情况下的时间复杂性各从某一个角度来反映算法的效率，各有各的用处，也各有各的局限性。但实践表明可操作性最好的且最有实际价值的是最坏情况下的时间复杂性。下面我们将把对时间复杂性分析的主要兴趣放在这种情形上。一般来说，最好情况和最坏情况的时间复杂性是很难计量的，原因是对于问题的任意确定的规模N达到了Tmax(N)的合法输入难以确定，而规模N的每一个输入的概率也难以预测或确定。我们有时也按平均情况计量时间复杂性，但那时在对P(I)做了一些人为的假设（比如等概率）之后才进行的。所做的假设是否符合实际总是缺乏根据。因此，在最好情况和平均情况下的时间复杂性分析还仅仅是停留在理论上。现在以<a href="http://algorithm.myrice.com/algorithm/complexity/chapter1.htm" target="_blank" >上一章</A>提到的<a href="http://algorithm.myrice.com/algorithm/complexity/chapter1.htm#pro1" target="_blank" >问题1</A>的<a href="http://algorithm.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.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.myrice.com/algorithm/complexity/images/img18.gif"> (2.9)而根据与(2.7)类似的推导，有：<img src="http://algorithm.myrice.com/algorithm/complexity/images/img21.gif">代入(2.9) ，则：<img src="http://algorithm.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.myrice.com/algorithm/complexity/images/img25.gif"> (2.10)比较(2.7)和(2.10) ，我们看到m充分大时，在最坏情况下B_Search的时间复杂性远小于Search的时间复杂性。

b · 发表于 2004-5-29 03:17:06

<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.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.myrice.com/algorithm/complexity/chapter1.htm#search" target="_blank" >第一章中的算法search</A>，在<a href="http://algorithm.myrice.com/algorithm/complexity/chapter2.htm" target="_blank" >第二章</A>给出了它的最坏情况下时间复杂性Tmax(m)和平均情况下的时间复杂性Tavg(m)的表达式。如果利用上述规则，立即有:Tmax(m)=Ο(m)和 Tavg(m)=Ο(m)+Ο(m)+Ο(m)=Ο(m)另一个例子：估计下面二重循环算法段在最坏情况下的时间复杂性T(N)的阶

b · 发表于 2004-5-29 03:17:47

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

		自动登录	找回密码
密码			注-册-帐-号