应《网络安全法》要求，自2017年10月1日起，未进行实名认证将不得使用互联网跟帖服务。为保障您的帐号能够正常使用，请尽快对帐号进行手机号验证，感谢您的理解与支持！

24小时热门版块排行榜    

小木虫论坛-学术科研互动平台 » 专业学科区 » 信息科学 » 算法Algorithm
51/1返回列表
查看: 513  |  回复: 4
只看楼主 @他人 存档 新回复提醒 (忽略) 收藏    在APP中查看
当前主题已经存档。

sdlj8051

金虫 (著名写手)

[交流] 算法Algorithm

算法 Algorithm

算法是在有限步骤内求解某一问题所使用的一组定义明确的规则。通俗点说，就是计算机解题的过程。在这个过程中，无论是形成解题思路还是编写程序，都是在实施某种算法。前者是推理实现的算法，后者是操作实现的算法。

一个算法应该具有以下五个重要的特征：

有穷性： 一个算法必须保证执行有限步之后结束；
确切性： 算法的每一步骤必须有确切的定义；
输入：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定除了初始条件；
输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；
可行性： 算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成。
　


Did you know

Algorithm 一词的由来


Algorithm(算法)一词本身就十分有趣。初看起来，这个词好像是某人打算要写“Logarithm”(对数)一词但却把头四个字母写的前后颠倒了。这个词一直到1957年之前在Webster's New World Dictionary(《韦氏新世界词典》)中还未出现，我们只能找到带有它的古代涵义的较老形式的“Algorism”(算术)，指的是用阿拉伯数字进行算术运算的过程。在中世纪时，珠算家用算盘进行计算，而算术家用算术进行计算。中世纪之后，对这个词的起源已经拿不准了，早期的语言学家试图推断它的来历，认为它是从把algiros(费力的)+arithmos(数字)组合起来派生而成的，但另一些人则不同意这种说法，认为这个词是从“喀斯迪尔国王Algor”派生而来的。最后，数学史学家发现了algorism(算术)一词的真实起源：它来源于著名的Persian Textbook(《波斯教科书》)的作者的名字Abu Ja'far Mohammed ibn Mûsâ al-Khowârizm （约公元前825年）——从字面上看，这个名字的意思是“Ja'far 的父亲，Mohammed 和 Mûsâ 的儿子，Khowârizm 的本地人”。Khowârizm 是前苏联XИBA(基发) 的小城镇 。Al-Khowârizm 写了著名的书Kitab al jabr w'al-muqabala (《复原和化简的规则》)；另一个词，“algebra”(代数)，是从他的书的标题引出来的，尽管这本书实际上根本不是讲代数的。

逐渐地，“algorism”的形式和意义就变得面目全非了。如牛津英语字典所说明的，这个词是由于同arithmetic(算术)相混淆而形成的错拼词。由algorism又变成algorithm。一本早期的德文数学词典 Vollstandiges Mathematisches Lexicon (《数学大全辞典》) ，给出了Algorithmus (算法)一词的如下定义：“在这个名称之下，组合了四种类型的算术计算的概念，即加法、乘法、减法、除法”。拉顶短语algorithmus infinitesimalis (无限小方法) ，在当时就用来表示Leibnitz(莱布尼兹)所发明的以无限小量进行计算的微积分方法。

1950年左右，algorithm一词经常地同欧几里德算法(Euclid's algorithm)联系在一起。这个算法就是在欧几里德的《几何原本》(Euclid's Elements ,第VII卷，命题i和ii)中所阐述的求两个数的最大公约数的过程(即辗转相除法)。



伪代码的使用 Usage of Pseudocode
伪代码(Pseudocode)是一种算法描述语言。使用为代码的目的是为了使被描述的算法可以容易地以任何一种编程语言(Pascal, C, Java, etc)实现。因此，伪代码必须结构清晰，代码简单，可读性好，并且类似自然语言。

下面介绍一种类Pascal语言的伪代码的语法规则。

伪代码的语法规则
在伪代码中，每一条指令占一行(else if 例外，)，指令后不跟任何符号（Pascal和C中语句要以分号结尾）；
书写上的“缩进”表示程序中的分支程序结构。这种缩进风格也适用于if-then-else语句。用缩进取代传统Pascal中的begin和end语句来表示程序的块结构可以大大提高代码的清晰性；同一模块的语句有相同的缩进量，次一级模块的语句相对与其父级模块的语句缩进；
例如：

line 1
line 2
   sub line 1
   sub line 2
     sub sub line 1
    sub sub line 2
   sub line 3
line 3

而在Pascal中这种关系用begin和end的嵌套来表示，

  line 1
  line 2
  begin
    sub line 1
    sub line 2
    begin
      sub sub line 1
      sub sub line 2            
    end;
    sub line 3
  end;
  line 3
在C中这种关系用{ 和 } 的嵌套来表示，

  line 1
  line 2
  {
     sub line 1
    sub line 2
    {
       sub sub line 1
    sub sub line 2
     }
    sub line 3
  }
  line 3
  
在伪代码中，通常用连续的数字或字母来标示同一即模块中的连续语句，有时也可省略标号。
例如：

  1. line 1
  2. line 2
     a. sub line 1
     b. sub line 2
       1. sub sub line 1
       2. sub sub line 2
     c. sub line 3
  3. line 3
符号△后的内容表示注释；
在伪代码中，变量名和保留字不区分大小写，这一点和Pascal相同，与C或C++不同；
在伪代码中，变量不需声明，但变量局部于特定过程，不能不加显示的说明就使用全局变量；
赋值语句用符号←表示，x←exp表示将exp的值赋给x，其中x是一个变量，exp是一个与x同类型的变量或表达式（该表达式的结果与x同类型）；多重赋值i←j←e是将表达式e的值赋给变量i和j，这种表示与j←e和i←e等价。
例如：

   x←y
   x←20*(y+1)
   x←y←30
以上语句用Pascal分别表示为：

  x := y;
  x := 20*(y+1);
  x := 30; y := 30;
以上语句用C分别表示为：

  x = y;
  x = 20*(y+1);
  x = y = 30;
选择语句用if-then-else来表示，并且这种if-then-else可以嵌套，与Pascal中的if-then-else没有什么区别。
例如:

  if (Condition1)
    then [ Block 1 ]
    else if (Condition2)
           then [ Block 2 ]
           else [ Block 3 ]  
循环语句有三种：while循环、repeat-until循环和for循环，其语法均与Pascal类似，只是用缩进代替begin - end；
例如：

  1. x ← 0
  2. y ← 0
  3. z ← 0
  4. while x < N
       1. do x ← x + 1
       2.    y ← x + y
       3.    for t ← 0 to 10
               1. do z ← ( z + x * y ) / 100
               2.    repeat
                       1. y ← y + 1
                       2. z ← z - y
               3.    until z < 0
       4.    z ← x * y
  5. y ← y / 2
上述语句用Pascal来描述是：

   x := 0;
   y := 0;
   z := 0;
   while x < N do
   begin
     x := x + 1;
     y := x + y;
     for t := 0 to 10 do
     begin
       z := ( z + x * y ) / 100;
       repeat
         y := y + 1;
         z := z - y;
       until z < 0;
     end;
     z := x * y;
   end;
   y := y / 2;
上述语句用C或C++来描述是：

  x = y = z = 0;
  while( z < N )
  {
    x ++;
    y += x;
    for( t = 0; t < 10; t++ )
    {
       z = ( z + x * y ) / 100;
       do {
          y ++;
          z -= y;
       } while( z >= 0 );
    }
    z = x * y;                 
  }
  y /= 2;   
数组元素的存取有数组名后跟“[下标]”表示。例如A[j]指示数组A的第j个元素。符号“ …”用来指示数组中值的范围。
例如：

A[1…j]表示含元素A[1], A[2], … , A[j]的子数组；

复合数据用对象(Object)来表示，对象由属性(attribute)和域(field)构成。域的存取是由域名后接由方括号括住的对象名表示。
例如：

数组可被看作是一个对象，其属性有length，表示其中元素的个数，则length[A]就表示数组A中的元素的个数。在表示数组元素和对象属性时都要用方括号，一般来说从上下文可以看出其含义。

用于表示一个数组或对象的变量被看作是指向表示数组或对象的数据的一个指针。对于某个对象x的所有域f，赋值y←x就使f[y]=f[x]，更进一步，若有f[x]←3，则不仅有f[x]=3，同时有f[y]=3，换言之，在赋值y←x后，x和y指向同一个对象。

有时，一个指针不指向任何对象，这时我们赋给他nil。

函数和过程语法与Pascal类似。
函数值利用 “return (函数返回值)” 语句来返回，调用方法与Pascal类似；过程用 “call 过程名”语句来调用；

例如：

   1. x ← t + 10
   2. y ← sin(x)
   3. call CalValue(x,y)
参数用按值传递方式传给一个过程：被调用过程接受参数的一份副本，若他对某个参数赋值，则这种变化对发出调用的过程是不可见的。当传递一个对象时，只是拷贝指向该对象的指针，而不拷贝其各个域。

[ Last edited by 幻影无痕 on 2006-11-16 at 07:30 ]
回复此楼

» 猜你喜欢
1楼 2006-08-26 09:36:25
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

sdlj8051

金虫 (著名写手)
算法的复杂性

傅清祥 王晓东
算法与数据结构 , 电子工业出版社,1998

摘要

本文介绍了算法的复杂性的概念和衡量方法，并提供了一些计算算法的复杂性的渐近阶的方法。

目录

§                            简介

§                            比较两对算法的效率

§                            复杂性的计量

§                            复杂性的渐近性态及其阶

§                            复杂性渐近阶的重要性

§                            算法复杂性渐近阶的分析

§                            递归方程组的渐近阶的求法

§                            1.代入法

§                            2.迭代法

§                            3.套用公式法

§                            4.差分方程法

§                            5.母函数法



简介

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

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

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

关于算法的复杂性，有两个问题要弄清楚：

用怎样的一个量来表达一个算法的复杂性；
对于给定的一个算法，怎样具体计算它的复杂性。
让我们从比较两对具体算法的效率开始。

比较两对算法的效率

考虑问题1：已知不重复且已经按从小到大排好的m个整数的数组A[1..m]（为简单起见。还设m=2 k，k是一个确定的非负整数）。对于给定的整数c，要求寻找一个下标i，使得A=c；若找不到，则返回一个0。

问题1的一个简单的算法是：从头到尾扫描数组A。照此，或者扫到A的第i个分量，经检测满足A=c；或者扫到A的最后一个分量，经检测仍不满足A=c。我们用一个函数Search来表达这个算法：

Function Search (c:integer):integer;

Var J:integer;

Begin

J:=1; {初始化}

{在还没有到达A的最后一个分量且等于c的分量还没有找到时，

查找下一个分量并且进行检测}

While (A
         j:=j+1;

If A[j]=c then search:=j {在数组A中找到等于c的分量，且此分量的下标为j}

           else Search:=0; {在数组中找不到等于c的分量}

End;

容易看出，在最坏的情况下，这个算法要检测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的分量，后一种情况则找不到。

这个新算法因为有反复把供查找的数组分成两半，然后在其中一半继续查找的特征，我们称为二分查找算法。它可以用函数B_Search来表达：

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;

容易理解，在最坏的情况下最多只要测A中的k+1(k=logm,这里的log以2为底，下同)个分量，就判断c是否在A中。

算法Search和B_Search解决的是同一个问题，但在最坏的情况下（所给定的c不在A中），两个算法所需要检测的分量个数却大不相同，前者要m=2 k个，后者只要k+1个。可见算法B_Search比算法Search高效得多。

以上例子说明：解同一个问题，算法不同，则计算的工作量也不同，所需的计算时间随之不同，即复杂性不同。

上图是运行这两种算法的时间曲线。该图表明，当m适当大（m>m0）时，算法B_Search比算法Search省时，而且当m更大时，节省的时间急剧增加。

不过，应该指出：用实例的运行时间来度量算法的时间复杂性并不合适，因为这个实例时间与运行该算法的实际计算机性能有关。换句话说，这个实例时间不单纯反映算法的效率而是反映包括运行该算法的计算机在内的综合效率。我们引入算法复杂性的概念是为了比较解决同一个问题的不同算法的效率，而不想去比较运行该算法的计算机的性能。因而，不应该取算法运行的实例时间作为算法复杂性的尺度。我们希望，尽量单纯地反映作为算法精髓的计算方法本身的效率，而且在不实际运行该算法的情况下就能分析出它所需要的时间和空间。

复杂性的计量
算法的复杂性是算法运行所需要的计算机资源的量，需要的时间资源的量称作时间复杂性，需要的空间（即存储器）资源的量称作空间复杂性。这个量应该集中反映算法中所采用的方法的效率，而从运行该算法的实际计算机中抽象出来。换句话说，这个量应该是只依赖于算法要解的问题的规模、算法的输入和算法本身的函数。如果分别用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)。那么有：

(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 )。在数学上有：

(2.4)

(2.5)

(2.6)

其中，DN是规模为N的合法输入的集合；I *是DN中一个使T(N,I *)达到Tmax(N)的合法输入，是DN中一个使T(N,)到Tmin(N)的合法输入；而P(I)是在算法的应用中出现输入I 的概率。

以上三种情况下的时间复杂性各从某一个角度来反映算法的效率，各有各的用处，也各有各的局限性。但实践表明可操作性最好的且最有实际价值的是最坏情况下的时间复杂性。下面我们将把对时间复杂性分析的主要兴趣放在这种情形上。

一般来说，最好情况和最坏情况的时间复杂性是很难计量的，原因是对于问题的任意确定的规模N达到了Tmax(N)的合法输入难以确定，而规模N的每一个输入的概率也难以预测或确定。我们有时也按平均情况计量时间复杂性，但那时在对P(I)做了一些人为的假设（比如等概率）之后才进行的。所做的假设是否符合实际总是缺乏根据。因此，在最好情况和平均情况下的时间复杂性分析还仅仅是停留在理论上。

现在以上一章提到的问题1的算法Search为例来说明如何利用(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]的情形。这时：

(2.8)

至于Tavg(m)，如前所述，必须对Dm上的概率分布做出假设才能计量。为简单起见，我们做最简单的假设：Dm上的概率分布是均等的，即P(A=c)=1/m 。若记Ti=T(m,Ii)，其中Ii表示A=c的合法输入，那么：

(2.9)

而根据与(2.7)类似的推导，有：



代入(2.9) ，则：



这里碰巧有：

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 ，则可以推演出：

(2.10)

比较(2.7)和(2.10) ，我们看到m充分大时，在最坏情况下B_Search的时间复杂性远小于Search的时间复杂性。

复杂性的渐近性态及其阶

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

我们先要引入复杂性渐近性态的概念。设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对于Ο有如ω对于Ω。
赞一下 回复此楼
2楼2006-08-26 09:37:55
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

sdlj8051

金虫 (著名写手)
复杂性渐近阶的重要性
计算机的设计和制造技术在突飞猛进，一代又一代的计算机的计算速度和存储容量在直线增长。有的人因此认为不必要再去苦苦地追求高效率的算法，从而不必要再去无谓地进行复杂性的分析。他们以为低效的算法可以由高速的计算机来弥补，以为在可接受的一定时间内用低效的算法完不成的任务，只要移植到高速的计算机上就能完成。这是一种错觉。造成这种错觉的原因是他们没看到：随着经济的发展、社会的进步、科学研究的深入，要求计算机解决的问题越来越复杂、规模越来越大，也呈线性增长之势；而问题复杂程度和规模的线性增长导致的时耗的增长和空间需求的增长，对低效算法来说，都是超线性的，决非计算机速度和容量的线性增长带来的时耗减少和存储空间的扩大所能抵销。事实上，我们只要对效率上有代表性的几个档次的算法作些简单的分析对比就能明白这一点。

我们还是以时间效率为例。设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算法与渐近时间复杂性的关系

算法
渐进时间复杂性T(N)
在C1上可解的规模N1
在C2上可解的规模N2
N1和N2的关系

A1
N
N11
N21
N21=10N11

A2
NlogN
N12
N22
N22≈10N12

A3
N2
N13
N23


A4
N3
N14
N24


A5
2N
N15
N25
N25 =N15+log10

A6
N!
N16
N26
N26 =N16+小的常数


从表4-1的最后一列可以清楚地看到，对于高效的算法A1，计算机的计算速度增长10倍，可求解的规模同步增长10倍；对于A2，可求解的问题的规模的增长与计算机的计算速度的增长接近同步；但对于低效的算法A3，情况就大不相同，计算机的计算速度增长10倍只换取可求解的问题的规模增加log10。当问题的规模充分大时，这个增加的数字是微不足道的。换句话说，对于低效的算法，计算机的计算速度成倍乃至数10倍地增长基本上不带来求解规模的增益。因此，对于低效算法要扩大解题规模，不能寄希望于移植算法到高速的计算机上，而应该把着眼点放在算法的改进上。

从表4-l的最后一列我们还看到，限制求解问题规模的关键因素是算法渐近复杂性的阶，对于表中的前四种算法，其渐近的时间复杂性与规模N的一个确定的幂同阶，相应地，计算机的计算速度的乘法增长带来的是求解问题的规模的乘法增长，只是随着幂次的提高，规模增长的倍数在降低。我们把渐近复杂性与规模N的幂同阶的这类算法称为多项式算法。对于表中的后两种算法，其渐近的时间复杂性与规模N的一个指数函数同阶，相应地计算机的计算速度的乘法增长只带来求解问题规模的加法增长。我们把渐近复杂性与规模N的指数同阶的这类算法称为指数型算法。多项式算法和指数型算法是在效率上有质的区别的两类算法。这两类算法的区别的内在原因是算法渐近复杂性的阶的区别。可见，算法的渐近复杂性的阶对于算法的效率有着决定性的意义。所以在讨论算法的复杂性时基本上都只关心它的渐近阶。

多项式算法是有效的算法。绝大多数的问题都有多项式算法。但也有一些问题还未找到多项式算法，只找到指数型算法。

我们在讨论算法复杂性的渐近阶的重要性的同时，有两条要记住：

“复杂性的渐近阶比较低的算法比复杂性的渐近阶比较高的算法有效”这个结论，只是在问题的求解规模充分大时才成立。比如算法A4比A5有效只是在N 3<2N，即N≥c 时才成立。其中c是方程N 3=2N的解。当N 当要比较的两个算法的渐近复杂性的阶相同时，必须进一步考察渐近复杂性表达式中常数因子才能判别它们谁好谁差。显然常数因子小的优于常数因子大的算法。比如渐近复杂性为N1ogN/l00的算法显然比渐近复杂性为l00NlogN的算法来得有效。
算法复杂性渐近阶的分析

前两段讲的是算法复杂性渐近阶的概念和对它进行分析的重要性。本段要讲如何具体地分析一个算法的复杂性的渐近阶，给出一套可操作的规则。算法最终要落实到用某种程序设计语言（如Pascal）编写成的程序。因此算法复杂性渐近阶的分析可代之以对表达该算法的程序的复杂性渐近阶的分析。

如前所提出，对于算法的复杂性，我们只考虑最坏、最好和平均三种情况，而通常又着重于最坏情况。为了明确起见，本段限于针对最坏情况。

仍然以时间复杂性为例。这里给出分析时间复杂性渐近阶的八条规则。这八条规则已覆盖了用Pascal语言程序所能表达的各种算法在最坏情况下的时间复杂性渐近阶的分析。

在逐条地列出并解释这入条规则之前，应该指出，当我们分析程序的某一局部(如一个语句，一个分程序，一个程序段，一个过程或函数)时，可以用具体程序的输入的规模N作为复杂性函数的自变量，也可以用局部的规模参数作为自变量。但是，作为最终结果的整体程序的复杂性函数只能以整体程序的输入规模为自变量。

对于串行的算法，相应的Pascal程序是一个串行的Pascal语句序列，因此，很明显，该算法的时间复杂性(即所需要的时间)等于相应的Pascal程序的每一个语句的时间复杂性(即所需要的时间)之和。所以，如果执行Pascal语句中的每一种语句所需要的时间都有计量的规则，那么，执行一个程序，即执行一个算法所需要的时间的计量便只是一个代数问题。接着，应用本节第三段所提供的Ο、Ω和θ等运算规则就可以分析出算法时间复杂性的渐近阶。

因此，我们的时间计量规则只需要针对Pascal有限的几种基本运算和几种基本语句。下面是这些规则的罗列和必要的说明。

规则(1)

赋值、比较、算术运算、逻辑运算、读写单个常量或单个变量等，只需要1个单位时间。

规则(2)

条件语句"if C then S1 else S2"只需要Tc+max(Ts1，Ts2)的时间，其中Tc是计算条件表达式C需要的时间，而Ts1和Ts2分别是执行语句S1和S2需要的时间。

规则(3)

选择语句"Case  A  of  a1:S1; a2:S2; … ;am:Sm;  end"，需要max(Ts1, Ts2，…，Tsm)的时间，其中Tsii是执行语句Si所需要的时间，i=l,2,…,m。

规则(4)

访问一个数组的单个分量或一个记录的单个域，只需要1个单位时间。

规则(5)

执行一个for循环语句需要的时间等于执行该循环体所需要的时间乘上循环的次数。

规则(6)

执行一个while循环语句"while C do S"或一个repeat循环语句" repeat S until C"，需要的时间等于计算条件表达式C需要的时间与执行循环S体需要的时间之和乘以循环的次数。与规则5不同，这里的循环次数是隐含的。

例如，b_search函数中的while循环语句。按规则(1)-(4)，计算条件表达式" (not found)and(U≥=L)"与执行循环体

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;

只需要θ(1)时间，而循环次数为logm，所以，执行此while语句只需要θ(logm)时间。

在许多情况下，运用规则(5)和(6)常常须要借助具体算法的内涵来确定循环的次数，才不致使时间的估计过于保守。这里举一个例子。

考察程序段：

　
　

Size:=m;
1

i:=1;
1

while i   

    begin
  

      i:=i+1;
  

      S1;
θ(n)

      if  Size>0  then
1

         begin
  

         在1到Size的范围内任选一个数赋值给t;
θ(1)

             Size:=Size-t;
2

             for j:=l  to  t  do
  

                 S2
θ(n)

         end;
  

    end;
  

　
　


程序在各行右端顶格处标注着执行相应各行所需要的时间。如果不对算法的内涵作较深入的考察，只看到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被执行的总次数，那么，这个总次数等于，又根据算法中ti的取法及sizei+1=sizei-ti，i=1,2,…,n-1 有sizen=size1-。最后利用size1=m和sizen=0得到=m 。于是在整个程序段上，S2被执行的总次数为m，所需要的时间为θ(mn)。执行其他语句所需要的时间直接运用规则(l)-(6)容易计算。累加起来，整个程序段在最坏情况下时间复杂性渐近阶为θ(n 2+mn)。这个结果显然比前面粗糙的估计准确。

规则(7)

对于goto语句。在Pascal中为了便于表达从循环体的中途跳转到循环体的结束或跳转到循环语句的后面语句，引入goto语句。如果我们的程序按照这一初衷使用goto语句，那么，在时间复杂性分析时可以假设它不需要任何额外的时间。因为这样做既不会低估也不会高估程序在最坏情况下的运行时间的阶。如果有的程序滥用了goto语句，即控制转移到前面的语句，那么情况将变得复杂起来。当这种转移造成某种循环时，只要与别的循环不交叉，保持循环的内外嵌套，则可以比照规则(1)-(6)进行分析。当由于使用goto语句而使程序结构混乱时，建议改写程序然后再做分析。

规则(8)

对于过程调用和函数调用语句，它们需要的时间包括两部分，一部分用于实现控制转移，另一部分用于执行过程(或函数)本身，这时可以根据过程(或函数)调用的层次，由里向外运用规则(l)-(7)进行分析，一层一层地剥，直到计算出最外层的运行时间便是所求。如果过程(或函数)出现直接或间接的递归调用，则上述由里向外逐层剥的分析行不通。这时我们可以对其中的各个递归过程(或函数)，所需要的时间假设为一个相应规模的待定函数。然后一一根据过程(或函数)的内涵建立起这些待定函数之间的递归关系得到递归方程。最后用求递归方程解的渐进阶的方法确定最坏情况下的复杂性的渐进阶。

递归方程的种类很多，求它们的解的渐近阶的方法也很多，我们将在下一段比较系统地给予介绍。本段只举一个简单递归过程(或函数)的例子来说明如何建立相应的递归方程，同时不加推导地给出它们在最坏情况下的时间复杂性的渐近阶。

例：再次考察函数b_search，这里将它改写成一个递归函数。为了简明，我们已经运用前面的规则(l)-(6)，统计出执行各行语句所需要的时间，并标注在相应行的右端：

　
　

Function b_search(C,L,U:integer):integer;
单位时间数

var index,element:integer;
  

begin
  

   if (U       1

            b_search:=0;
      1

   else
  

    begin
  

      index:=(L+U) div 2;
      3

      element:=A[index];
      2

      if element=C then
      1

        b_search:=index
      1

   else if element>C then
  

        b_search:=b_search(C,L,index-1)
    3+T(m/2)

      else
  

        b_search:=b_search(C,index+1,U);
    3+T(m/2)

    end;
  

end;
  

　
　


其中T(m)是当问题的规模U-L+1=m时b_search在最坏情况下(这时，数组A[L..U]中没有给定的C)的时间复杂性。根据规则(l)-(8)，我们有：



或化简为



这是一个关于T(m)的递归方程。用下一段将介绍的迭代法，容易解得：

T(m)=11logm +l3=θ(logm)

在结束这一段之前，我们要提一下关于算法在最坏情况下的空间复杂性分析。我们照样可以给出与分析时间复杂性类似的规则。这里不赘述。然而应该指出，在出现过程(或函数)递归调用时要考虑到其中隐含的存储空间的额外开销。因为现有的实现过程(或函数)递归调用的编程技术需要一个隐含的、额外(即不出现在程序的说明中)的栈来支持。过程(或函数)的递归调用每深人一层就把本层的现场局部信息及调用的返回地址存放在栈顶备用，直到调用的最里层。因此递归调用一个过程(或函数)所需要的额外存储空间的大小即栈的规模与递归调用的深度成正比，其比例因子等于每深入一层需要保存的数据量。比如本段前面所举的递归函数b_search，在最坏情况下，递归调用的深度为logm，因而在最坏情况下调用它所需要的额外存储空间为θ(logm)。

递归方程解的渐近阶的求法
上一章所介绍的递归算法在最坏情况下的时间复杂性渐近阶的分析，都转化为求相应的一个递归方程的解的渐近阶。因此，求递归方程的解的渐近阶是对递归算法进行分析的关键步骤。

递归方程的形式多种多样，求其解的渐近阶的方法也多种多样。这里只介绍比较实用的五种方法。

代入法 这个方法的基本步骤是先推测递归方程的显式解，然后用数学归纳法证明这一推测的正确性。那么，显式解的渐近阶即为所求。
迭代法  这个方法的基本步骤是通过反复迭代，将递归方程的右端变换成一个级数，然后求级数的和，再估计和的渐近阶；或者，不求级数的和而直接估计级数的渐近阶，从而达到对递归方程解的渐近阶的估计。
套用公式法 这个方法针对形如：T (n)=aT (n / b)+f (n) 的递归方程，给出三种情况下方程解的渐近阶的三个相应估计公式供套用。
差分方程法  有些递归方程可以看成一个差分方程，因而可以用解差分方程(初值问题)的方法来解递归方程。然后对得到的解作渐近阶的估计。
母函数法 这是一个有广泛适用性的方法。它不仅可以用来求解线性常系数高阶齐次和非齐次的递归方程，而且可以用来求解线性变系数高阶齐次和非齐次的递归方程，甚至可以用来求解非线性递归方程。方法的基本思想是设定递归方程解的母函数，努力建立一个关于母函数的可解方程，将其解出，然后返回递归方程的解。
本章将逐一地介绍上述五种井法，并分别举例加以说明。

本来，递归方程都带有初始条件，为了简明起见，我们在下面的讨论中略去这些初始条件。

递归方程组解的渐进阶的求法——代入法
用这个办法既可估计上界也可估计下界。如前面所指出，方法的关键步骤在于预先对解答作出推测，然后用数学归纳法证明推测的正确性。

例如，我们要估计T(n)的上界，T(n)满足递归方程：



其中是地板(floors)函数的记号，表示不大于n的最大整数。

我们推测T(n)=O(nlog n)，即推测存在正的常数C和自然数n0，使得当n≥n0时有：

T(n)≤Cnlog n (6.2)

事实上，取n0=22=4，并取



那么，当n0≤n≤2n0时，(6.2)成立。今归纳假设当2k-1n0≤n≤2kn0 ，k≥1时，(1.1.16)成立。那么，当2kn0≤n≤2k+1n0时，我们有：



即(6.2)仍然成立，于是对所有n≥n0，(6.2)成立。可见我们的推测是正确的。因而得出结论：递归方程(6.1)的解的渐近阶为O(nlogn)。

这个方法的局限性在于它只适合容易推测出答案的递归方程或善于进行推测的高手。推测递归方程的正确解，没有一般的方法，得靠经验的积累和洞察力。我们在这里提三点建议：

(1) 如果一个递归方程类似于你从前见过的已知其解的方程，那么推测它有类似的解是合理的。作为例子，考虑递归方程：



右边项的变元中加了一个数17，使得方程看起来难于推测。但是它在形式上与(6.1)很类似。实际上，当n充分大时

与

相差无几。因此可以推测(6.3)与(6.1)有类似的上界T(n)=O(nlogn)。进一步，数学归纳将证明此推测是正确的。

(2)从较宽松的界开始推测，逐步逼近精确界。比如对于递归方程(6.1)，要估计其解的渐近下界。由于明显地有T(n)≥n，我们可以从推测T(n)=Ω(n)开始，发现太松后，把推测的阶往上提，就可以得到T(n)=Ω(nlog n)的精确估计。

(3)作变元的替换有时会使一个末知其解的递归方程变成类似于你曾见过的已知其解的方程，从而使得只要将变换后的方程的正确解的变元作逆变换，便可得到所需要的解。例如考虑递归方程：



看起来很复杂，因为右端变元中带根号。但是，如果作变元替换m=logn，即令n=2m ，将其代入(6.4)，则(6.4)变成：



把m限制在正偶数集上，则(6.5)又可改写为：

T(2m)=2T(2m/2)+m

若令S(m)=T(2m)，则S(m)满足的递归方程：

S(m)=2S(m/2)+m ，

与(6.1)类似，因而有：

S(m)=O(m1og m)，

进而得到T(n)=T(2m)=S(m)=O(m1ogm)=O(lognloglogn) (6.6)

上面的论证只能表明：当(充分大的)n是2的正偶次幂或换句话说是4的正整数次幂时(6.6)才成立。进一步的分析表明(6.6)对所有充分大的正整数n都成立，从而，递归方程(6.4)解的渐近阶得到估计。

在使用代入法时，有三点要提醒：

(1)记号O不能滥用。比如，在估计(6.1)解的上界时，有人可能会推测T(n)=O(n)，即对于充分大的n，有T(n)≤Cn ，其中C是确定的正的常数。他进一步运用数学归纳法，推出：



从而认为推测T(n)=O(n)是正确的。实际上，这个推测是错误的，原因是他滥用了记号O ，错误地把(C+l)n与Cn等同起来。

(2)当对递归方程解的渐近阶的推测无可非议，但用数学归纳法去论证又通不过时，不妨在原有推测的基础上减去一个低阶项再试试。作为一个例子，考虑递归方程



其中是天花板(floors)函数的记号。我们推测解的渐近上界为O(n)。我们要设法证明对于适当选择的正常数C和自然数n0，当n≥n0时有T(n)≤Cn。把我们的推测代入递归方程，得到：



我们不能由此推断T(n)≤Cn，归纳法碰到障碍。原因在于(6.8)的右端比Cn多出一个低阶常量。为了抵消这一低阶量，我们可在原推测中减去一个待定的低阶量b，即修改原来的推测为T(n)≤Cn-b 。现在将它代人(6.7)，得到：



只要b≥1，新的推测在归纳法中将得到通过。

(3)因为我们要估计的是递归方程解的渐近阶，所以不必要求所作的推测对递归方程的初始条件（如T(0)、T(1)）成立，而只要对T(n)成立，其中n充分大。比如，我们推测(6.1)的解T(n)≤Cnlogn，而且已被证明是正确的，但是当n=l时，这个推测却不成立，因为(Cnlogn)|n=1=0而T(l)>0。
赞一下 回复此楼
3楼2006-08-26 09:38:37
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

sdlj8051

金虫 (著名写手)
递归方程组解的渐进阶的求法——迭代法
用这个方法估计递归方程解的渐近阶不要求推测解的渐近表达式，但要求较多的代数运算。方法的思想是迭代地展开递归方程的右端，使之成为一个非递归的和式，然后通过对和式的估计来达到对方程左端即方程的解的估计。

作为一个例子，考虑递归方程：



接连迭代二次可将右端项展开为：



由于对地板函数有恒等式：



(6.10)式可化简为：



这仍然是一个递归方程，右端项还应该继续展开。容易看出，迭代 i 次后，将有

（6.11）

而且当



时，(6.11)不再是递归方程。这时：

(6.13)

又因为[a]≤a，由(6.13)可得：



而由(6.12)，知i≤log4n ，从而

，

代人(6.14)得：



即方程(6.9)的解  T(n)=O(n)。

从这个例子可见迭代法导致繁杂的代数运算。但认真观察一下，要点在于确定达到初始条件的迭代次数和抓住每次迭代产生出来的"自由项"(与T无关的项)遵循的规律。顺便指出，迭代法的前几步迭代的结果常常能启发我们给出递归方程解的渐近阶的正确推测。这时若换用代入法，将可免去上述繁杂的代数运算。



图6-1 与方程(6.15)相应的递归树

为了使迭代法的步骤直观简明、图表化，我们引入递归树。靠着递归树，人们可以很快地得到递归方程解的渐近阶。它对描述分治算法的递归方程特别有效。我们以递归方程

T(n)=2T(n/2)+n2 (6.15)

为例加以说明。图6-1展示出(6.15)在迭代过程中递归树的演变。为了方便，我们假设n恰好是2的幂。在这里，递归树是一棵二叉树，因为(6.15)右端的递归项2T(n/2)可看成T(n/2)+T(n/2)。图6-1(a)表示T(n)集中在递归树的根处，(b)表示T(n)已按(6.15)展开。也就是将组成它的自由项n2留在原处，而将2个递归项T(n/2)分别摊给它的2个儿子结点。(c)表示迭代被执行一次。图6-1(d)展示出迭代的最终结果。

图6-1中的每一棵递归树的所有结点的值之和都等于T(n)。特别，已不含递归项的递归树(d)中所有结点的值之和亦然。我们的目的是估计这个和T(n)。我们看到有一个表格化的办法：先按横向求出每层结点的值之和，并记录在各相应层右端顶格处，然后从根到叶逐层地将顶格处的结果加起来便是我们要求的结果。照此，我们得到(6.15)解的渐近阶为θ(n2)。

再举一个例子。递归方程：

T(n)= T(n/3)+ T(2n/3)+n (6.16)

的迭代过程相应的递归树如图6-2所示。其中，为了简明，再一次略去地板函数和天花板函数。



图6-2迭代法解(6.16)的递归树

当我们累计递归树各层的值时，得到每一层的和都等于n，从根到叶的最长路径是



设最长路径的长度为k，则应该有

，

得

，

于是



即T(n)=O(nlogn) 。

以上两个例子表明，借助于递归树，迭代法变得十分简单易行。

递归方程组解的渐进阶的求法——套用公式法
这个方法为估计形如：

T(n)=aT(n/b)+f(n) (6.17)

的递归方程解的渐近阶提供三个可套用的公式。(6.17)中的a≥1和b≥1是常数，f (n)是一个确定的正函数。

(6.17)是一类分治法的时间复杂性所满足的递归关系，即一个规模为n的问题被分成规模均为n/b的a个子间题，递归地求解这a个子问题，然后通过对这a个子间题的解的综合，得到原问题的解。如果用T(n)表示规模为n的原问题的复杂性，用f(n)表示把原问题分成a个子问题和将a个子问题的解综合为原问题的解所需要的时间，我们便有方程(6.17)。

这个方法依据的是如下的定理：设a≥1和b≥1是常数f (n)是定义在非负整数上的一个确定的非负函数。又设T(n)也是定义在非负整数上的一个非负函数，且满足递归方程(6.17)。方程(6.17)中的n/b可以是[n/b]，也可以是n/b。那么，在f(n)的三类情况下，我们有T(n)的渐近估计式：

若对于某常数ε>0，有
，
则
；
若
，
则
；
若对其常数ε>0，有

且对于某常数c>1和所有充分大的正整数n有af(n/b)≤cf(n)，则T(n)=θ(f(n))。
这里省略定理的证明。

在应用这个定理到一些实例之前，让我们先指出定理的直观含义，以帮助读者理解这个定理。读者可能已经注意到，这里涉及的三类情况，都是拿f(n)与作比较。定理直观地告诉我们，递归方程解的渐近阶由这两个函数中的较大者决定。在第一类情况下，函数较大，则T(n)=θ()；在第三类情况下，函数f(n)较大，则T(n)=θ(f (n))；在第二类情况下，两个函数一样大，则T(n)=θ()，即以n的对数作为因子乘上f(n)与T(n)的同阶。

此外，定理中的一些细节不能忽视。在第一类情况下f(n)不仅必须比小，而且必须是多项式地比小，即f(n)必须渐近地小于与的积，ε是一个正的常数；在第三类情况下f(n)不仅必须比大，而且必须是多项式地比大，还要满足附加的“正规性”条件：af(n/b)≤cf(n)。这个附加的“正规性”条件的直观含义是a个子间题的再分解和再综合所需要的时间最多与原问题的分解和综合所需要的时间同阶。我们在一般情况下将碰到的以多项式为界的函数基本上都满足这个正规性条件。

还有一点很重要，即要认识到上述三类情况并没有覆盖所有可能的f(n)。在第一类情况和第二类情况之间有一个间隙：f(n)小于但不是多项式地小于；类似地，在第二类情况和第三类情况之间也有一个间隙：f(n)大于但不是多项式地大于。如果函数f(n)落在这两个间隙之一中，或者虽有，但正规性条件不满足，那么，本定理无能为力。

下面是几个应用例子。

例1 考虑

T(n)=9T(n/3)+n0

对照(6.17)，我们有a=9，b=3， f(n)=n， ，取，便有，可套用第一类情况的公式，得T(n)=θ(n2)。

例2 考虑

T(n)=T(2n/3)+1

对照(6.17)，我们有a=1，b=3/2， f(n)=1，，可套用第二类情况的公式，得T(n)=θ(logn)。

例3 考虑

T(n)=3T(n/4)+nlogn

对照(6.17)，我们有a=3，b=4， f(n)=nlog n， ，只要取，便有。进一步，检查正规性条件：



只要取c=3/4，便有af(n/b)≤cf(n)，即正规性条件也满足。可套用第三类情况的公式，得T(n)=θ(f(n))=θ(nlogn)。

最后举一个本方法对之无能为力的例子。

考虑

T(n)=2T(n/2)+nlogn

对照(6.17)，我们有a=2，b=2， f(n)=nlog n， ，虽然f(n)渐近地大于，但f(n)并不是多项式地大于，因为对于任意的正常数ε，

，

即f(n)在第二类情况与第三类情况的间隙里，本方法对它无能为力。



递归方程组解的渐进阶的求法——差分方程法
这里只考虑形如：

T(n)=c1T(n-1)+c2T(n-2)+…+ ckT(n-k)+f(n)，n≥k (6.18)

的递归方程。其中ci (i=l，2，…，k)为实常数，且ck≠0。它可改写为一个线性常系数k阶非齐次的差分方程：

T(n)-c1T(n-1)- c2T(n-2)-…-ckT(n-k)=f(n)，n≥k (6.19)

(6.19)与线性常系数k阶非齐次常微分方程的结构十分相似，因而解法类同。限于篇幅，这里直接给出(6.19)的解法，略去其正确性的证明。

第一步，求(6.19)所对应的齐次方程：

T(n)-c1T(n-1)- c2T(n-2)-…-ckT(n-k)=0 (6.20)

的基本解系：写出(6.20)的特征方程：

C(t)=tk-c1tk-1-c2tk-2 -…-ck=0 (6.21)

若t=r是(6.21)的m重实根，则得(6.20)的m个基础解rn，nrn，n2rn，…，nm-1rn；若ρeiθ和ρe-iθ是(6.21)的一对l重的共扼复根，则得(6.20)的2l个基础解ρncosnθ，ρnsinnθ，nρncosnθ，nρnsinnθ，…，nl-1ρncosnθ，nl-1ρncosnθ。如此，求出(6.21)的所有的根，就可以得到(6.20)的k个的基础解。而且，这k个基础解构成了(6.20)的基础解系。即(6.20)的任意一个解都可以表示成这k个基础解的线性组合。

第二步，求(6.19)的一个特解。理论上，(6.19)的特解可以用Lagrange常数变易法得到。但其中要用到(6.20)的通解的显式表达，即(6.20)的基础解系的线性组合，十分麻烦。因此在实际中，常常采用试探法，也就是根据f(n)的特点推测特解的形式，留下若干可调的常数，将推测解代人(6.19)后确定。由于(6.19)的特殊性，可以利用迭加原理，将f(n)线性分解为若干个单项之和并求出各单项相应的特解，然后迭加便得到f(n)相应的特解。这使得试探法更为有效。为了方便，这里对三种特殊形式的f(n)，给出(6.19)的相应特解并列在表6-1中，可供直接套用。其中pi，i=1,2,…,s是待定常数。

表6-1 方程(6.19)的常用特解形式

f(n)的形式
条    件
方程(6.19)的特解的形式

an
C(a)≠0


a是C(t)的m重根


ns
C(1)≠0


1是C(t)的m重根


nsan
C(a)≠0


a是C(t)的m重根



第三步，写出(6.19)即(6.18)的通解

(6.22)

其中{Ti(n)，i=0,1,2,…,n}是(6.20)的基础解系，g(n)是(6.19)的一个特解。然后由(6.18)的初始条件

T(i)=Ti ，i=1,2,…,k-1

来确定(6.22)中的待定的组合常数{ai}，即依靠线性方程组



或



解出{ai}，并代回(6.22)。其中βj=Tj-g(j)，j=0,1,2,…,k-1。

第四步，估计(6.22)的渐近阶，即为所要求。

下面用两个例子加以说明。

例l 考虑递归方程



它的相应特征方程为：

C(t)=t2-t-1=0

解之得两个单根和。相应的(6.20)的基础解系为{r0n，r1n}。相应的(6.19)的一个特解为F*(n)=-8，因而相应的(6.19)的通解为：

F(n)=a0r0n +a1r1n- 8

令其满足初始条件，得二阶线性方程组：



或



或



解之得，，从而



于是

。

例2 考虑递归方程

T(n)=4T(n-1)-4T(n-2)+2nn (6.23)

和初始条件T(0)=0，T(1)=4/3。

它对应的特征方程(6.21)为

C(t)=t2-4t+4=0

有一个两重根r =2。故相应的(6.20)的基础解系为{2n，2nn}。由于f(n)=2nn，利用表6-1，相应的(6.19)的一个特解为

T*(n)=n2(p0+p1n)2n，

代人(6.23)，定出p0=1/2，p1=1/6。因此相应的(6.19)的通解为：

T(n)=a02n+a1n2n+n2(1/2+n/6)2n，

令其满足初始条件得a0=a1=0，从而

T(n)=n2(1/2+n/6)2n

于是T(n)=θ(n32n)。

递归方程组解的渐进阶的求法——母函数法
关于T(n)的递归方程的解的母函数通常设为：

(6.24)

当(6.24)右端由于T(n)增长太快而仅在x=0处收敛时可另设

(6.25)

如果我们可以利用递归方程建立A(x)的一个定解方程并将其解出，那么，把A(x)展开成幂级数，则xn或xn/n!项的系数便是所求的递归方程的解。其渐近阶可接着进行估计。

下面举两个例子加以说明。

例1 考虑线性变系数二阶齐次递归方程

(n-1)T(n)=(n-2)T(n-1)+2T(n-2) ，n≥2 (6.26)

和初始条件T(0)=0，T(1)=1。根据初始条件及(6.26)，可计算T(2)=0，T(3)=T(1)=1。

设{T(n)}的母函数为：



由于T (0)=T (2)=0，T(1)= 1，有 ：



令 B(x)= A (x)/x，即：



那么：



利用(6.26)并代入T (3)= 1，得



即



两边同时沿[0,x]积分，并注意到B(0)=1，有：



把B(x)展开成幂级数，得



从而



最后得



例2 考虑线性变系数一阶非齐次递归方程

D(n)=nD(n-1)+(-1)n  n≥1 (6.27)

及初始条件D (0)= 1

很明显D(n)随n的增大而急剧增长。如果仍采用(6.24)形式的函数，则(6.24)的右端可能仅在x=0处收敛，所以这里的母函数设为：



用xn/n!乘以(6.27)的两端，然后从1到∞求和得：



化简并用母函数表达，有：

A(x) -1= xA(x)+e-x-1

或

(1-x)A(x)=e-x

从而

A(x)=e-x/(1-x)

展成幂级数，则：



故
赞一下 回复此楼
4楼2006-08-26 09:39:11
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

sdlj8051

金虫 (著名写手)
算法设计策略
这里介绍了一般的算法设计策略，阐述各方法的理论基础、主要思想及其适用范围。同时针对一些具体问题来讲述如何用这些一般的理论以及各种抽象数据类型对问题进行抽象描述，并用最有效的方式设计出解决问题的高效算法。它们将生动地再现计算机程序设计方法学的理论、抽象和设计三个过程，而且，通过对算法正确性的证明和复杂性的分析，深化对大问题的复杂性、概念和形式模型、效率和抽象的层次、折衷和结论等在计算机学科中重复出现的概念的理解。

必须强调指出，对于某些问题(如NP--完全问题)而言，用这里的方法和任何已知的方法都不可能设计出有效的算法。对于这种问题，人们常常考虑利用具体输入的某些特点来设计有效算法或设计求问题近似解的有效算法。这一部分内容我们将在高级专题中讨论。

在对有关算法进行形式描述时我们采用类Pascal的伪代码，并作了一些简化，略去不言而喻的一些说明，如函数、形参、变量等类型说明。

这里主要讨论的算法设计策略有：

递归技术 —— 最常用的算法设计思想，体现于许多优秀算法之中
分治法 —— 分而制之的算法思想，体现了一分为二的哲学思想
模拟法 —— 用计算机模拟实际场景，经常用于与概率有关的问题
贪心算法 —— 采用贪心策略的算法设计
状态空间搜索法 —— 被称为“万能算法”的算法设计策略
随机算法 —— 利用随机选择自适应地决定优先搜索的方向
动态规划 —— 常用的最优化问题解决方法
摘要

本文介绍了分治法的基本思想和基本步骤，通过实例讨论了利用分治策略设计算法的途径。

目录

§                            简介

§                            分治法的基本思想

§                            分治法的适用条件

§                            分治法的基本步骤

§                            分治法的复杂性分析

§                            分治法的几种变形

§                            分治法的实例分析

§                            其他资料

参考文献

现代计算机常用数据结构和算法，潘金贵 等 编著，南京大学出版社，1992
算法与数据结构，傅清祥 王晓东 编著，电子工业出版社，1998
Dictionary of Algorithms, Data Structures, and Problems ，Paul E. Black ，http://hissa.nist.gov/dads/ , 下载该网站的镜像（1,682KB）
简介
对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。

分治法的基本思想

任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。问题的规模越小，越容易直接求解，解题所需的计算时间也越少。例如，对于n个元素的排序问题，当n=1时，不需任何计算。n=2时，只要作一次比较即可排好序。n=3时只要作3次比较即可，…。而当n较大时，问题就不那么容易处理了。要想直接解决一个规模较大的问题，有时是相当困难的。

分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。

如果原问题可分割成k个子问题，1
分治法的适用条件
分治法所能解决的问题一般具有以下几个特征：

该问题的规模缩小到一定的程度就可以容易地解决；
该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。
利用该问题分解出的子问题的解可以合并为该问题的解；
该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。
上述的第一条特征是绝大多数问题都可以满足的，因为问题的计算复杂性一般是随着问题规模的增加而增加；第二条特征是应用分治法的前提，它也是大多数问题可以满足的，此特征反映了递归思想的应用；第三条特征是关键，能否利用分治法完全取决于问题是否具有第三条特征，如果具备了第一条和第二条特征，而不具备第三条特征，则可以考虑贪心法或动态规划法。第四条特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然可用分治法，但一般用动态规划法较好。

分治法的基本步骤
分治法在每一层递归上都有三个步骤：

分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；
解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题；
合并：将各个子问题的解合并为原问题的解。
它的一般的算法设计模式如下：

Divide-and-Conquer(P)

1.  if |P|≤n0

2.    then return(ADHOC(P))

3.  将P分解为较小的子问题 P1 ,P2 ,...,Pk

4.  for i←1 to k

5.    do yi ← Divide-and-Conquer(Pi)    △ 递归解决Pi

6.  T ← MERGE(y1,y2,...,yk)             △ 合并子问题

7.  return(T)

其中|P|表示问题P的规模；n0为一阈值，表示当问题P的规模不超过n0时，问题已容易直接解出，不必再继续分解。ADHOC(P)是该分治法中的基本子算法，用于直接解小规模的问题P。因此，当P的规模不超过n0时，直接用算法ADHOC(P)求解。算法MERGE(y1,y2,...,yk)是该分治法中的合并子算法，用于将P的子问题P1 ,P2 ,...,Pk的相应的解y1,y2,...,yk合并为P的解。

根据分治法的分割原则，原问题应该分为多少个子问题才较适宜？各个子问题的规模应该怎样才为适当？这些问题很难予以肯定的回答。但人们从大量实践中发现，在用分治法设计算法时，最好使子问题的规模大致相同。换句话说，将一个问题分成大小相等的k个子问题的处理方法是行之有效的。许多问题可以取k=2。这种使子问题规模大致相等的做法是出自一种平衡(balancing)子问题的思想，它几乎总是比子问题规模不等的做法要好。

分治法的合并步骤是算法的关键所在。有些问题的合并方法比较明显，如下面的例1，例2；有些问题合并方法比较复杂，或者是有多种合并方案，如例3，例4；或者是合并方案不明显，如例5。究竟应该怎样合并，没有统一的模式，需要具体问题具体分析。

分治法的复杂性分析

从分治法的一般设计模式可以看出，用它设计出的程序一般是一个递归过程。因此，分治法的计算效率通常可以用递归方程来进行分析。为方便起见，设分解阈值n0=1，且算法ADHOC解规模为1的问题耗费1个单位时间。又设分治法将规模为n的问题分成k个规模为n/m的子问题去解，而且，将原问题分解为k个子问题以及用算法MERGE将k个子问题的解合并为原问题的解需用f(n)个单位时间。如果用T(n)表示该分治法Divide-and-Conquer(P)解规模为|P|=n的问题P所需的计算时间，则有:

（1）

用算法的复杂性中递归方程解的渐进阶的解法介绍的解递归方程的迭代法，可以求得(1)的解:

（2）

注意，递归方程(1)及其解(2)只给出n等于m的方幂时T(n)的值，但是如果认为T(n)足够平滑，那么由等于m的方幂时T(n)的值可以估计T(n)的增长速度。通常，我们可以假定T(n)是单调上升的，从而当mi≤n
另一个需要注意的问题是，在分析分治法的计算效率时，通常得到的是递归不等式：

(3)

由于我们关心的一般是最坏情况下的计算时间复杂度的上界，所以用等于号(=)还是小于或等于号(≤)是没有本质区别的。

分治法的几种变形
二分法 dichotomy
一种每次将原问题分解为两个子问题的分治法，是一分为二的哲学思想的应用。这种方法很常用，由此法产生了许多经典的算法和数据结构。

分解并在解决之前合并法 divide and marriage before conquest
一种分治法的变形，其特点是将分解出的子问题在解决之前合并。

管道传输分治法 pipelined divide and conquer
一种分治法的变形，它利用某种称为“管道”的数据结构在递归调用结束前将其中的某些结果返回。此方法经常用来减少算法的深度。

注: divide and marriage before conquest和pipelined divide and conquer 方法我并不太了解，只在某些参考文献上看过其名称。其原文定义如下：
divide and marriage before conquest:A variant of divide and conquer in which subproblems created in the "divide" step are merged before the "conquer" step.
pipelined divide and conquer:A divide and conquer paradigm in which partial results from recursive calls can be used before the calls complete. The technique is often useful for reducing the depth of an algorithm.
如果你有关于这两种算法的资料请告诉我(mailto:Starfish.h@china.com)。

分治法的实例分析

以上讨论的是分治法的基本思想和一般原则，下面我们用具体的例子来说明如何针对具体问题用分治法来设计有效解法。

例1和例2是分治法的经典范例，其分解和合并过程都比较简单明显；例3和例4的合并方法有多种选择，只有选择最好的合并方法才能够改进算法的复杂度；例5是一个计算几何学中的问题，它的合并步骤需要较高的技巧。例6则是IOI'95的试题 Wires and Switches 。

例1 二分查找
例2 快速排序
例3 大整数乘法
例4 Strassen矩阵乘法
例5 最接近点对问题
例6 导线和开关
更多实例请参阅分治法问题集

其他资料

请参阅以下文章：

递归技术
贪心法
动态规划
分治法问题集
赞一下 回复此楼
5楼2006-08-26 09:39:27
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖
相关版块跳转 我要订阅楼主 sdlj8051 的主题更新
51/1返回列表
普通表情 龙 兔 虎 猫 高级回复 (可上传附件)
最具人气热帖推荐 [查看全部] 作者 回/看 最后发表
[考研] 0703化学调剂，求导师收 +4 天天好运来上岸� 2026-03-24 4/200 2026-03-24 15:23 by cuifj
[考研] 300求调剂，材料科学英一数二 +3 leaflight 2026-03-24 3/150 2026-03-24 15:10 by 冠c哥
[考研] 一志愿北京化工大学材料与化工 264分各科过A区国家线 +3 哈哈157349 2026-03-21 3/150 2026-03-24 14:11 by zhyzzh
[基金申请] 请教下大家 2026年国家基金申请是双盲审吗？ +3 lishucheng1 2026-03-22 5/250 2026-03-24 08:22 by gltch
[考研] 材料/农业专业，07/08开头均可，过线就行 +3 呵唔哦豁 2026-03-23 4/200 2026-03-23 22:30 by 汪！？！
[考研] 323求调剂 +6 洼小桶 2026-03-18 6/300 2026-03-23 00:29 by king123！
[考研] 生物学071000 329分求调剂 +5 我爱生物生物爱� 2026-03-17 5/250 2026-03-22 16:42 by tcx007
[考研] 生物学调剂 +5 Surekei 2026-03-21 5/250 2026-03-22 14:39 by tcx007
[考研] 085600材料与化工306 +4 z1z2z3879 2026-03-21 4/200 2026-03-21 23:44 by ms629
[考研] 280求调剂 +11 咕噜晓晓 2026-03-18 12/600 2026-03-21 22:40 by ACS Nano——
[考研] 初试 317 +7 半拉月丙 2026-03-20 7/350 2026-03-21 22:26 by peike
[考研] 考研调剂 +3 呼呼？~+123456 2026-03-21 3/150 2026-03-21 20:04 by 无际的草原
[考研] 336求调剂 +5 rmc8866 2026-03-21 5/250 2026-03-21 17:24 by 学员8dgXkO
[考研] 一志愿重庆大学085700资源与环境总分308求调剂 +7 墨墨漠 2026-03-20 7/350 2026-03-21 16:36 by barlinike
[考研] 材料与化工（0856）304求 B区 调剂 +3 邱gl 2026-03-21 3/150 2026-03-21 13:47 by lature00
[考研] 一志愿重庆大学085700资源与环境专硕，总分308求调剂 +3 墨墨漠 2026-03-18 3/150 2026-03-21 00:39 by JourneyLucky
[考研] 304求调剂 +6 曼殊2266 2026-03-18 6/300 2026-03-21 00:32 by JourneyLucky
[考研] 南京大学化学376求调剂 +3 hisfailed 2026-03-19 6/300 2026-03-20 23:43 by hisfailed
[考研] 320求调剂0856 +3 不想起名字112 2026-03-19 3/150 2026-03-19 22:53 by 学员8dgXkO
[考博] 26博士申请 +3 1042136743 2026-03-17 3/150 2026-03-17 23:30 by 轻松不少随
信息提示
关闭
请填处理意见
关闭