算法 Algorithm

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

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

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

　

 

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语言的伪代码的语法规则。

伪代码的语法规则

  1. 在伪代码中，每一条指令占一行(else if 例外，)，指令后不跟任何符号（Pascal和C中语句要以分号结尾）；
  2. 书写上的“缩进”表示程序中的分支程序结构。这种缩进风格也适用于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. 在伪代码中，通常用连续的数字或字母来标示同一即模块中的连续语句，有时也可省略标号。

例如：

  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
  1. 符号△后的内容表示注释；
  2. 在伪代码中，变量名和保留字不区分大小写，这一点和Pascal相同，与C或C++不同；
  3. 在伪代码中，变量不需声明，但变量局部于特定过程，不能不加显示的说明就使用全局变量；
  4. 赋值语句用符号←表示，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;
  1. 选择语句用if-then-else来表示，并且这种if-then-else可以嵌套，与Pascal中的if-then-else没有什么区别。

例如: 

  if (Condition1) 
    then [ Block 1 ]
    else if (Condition2) 
           then [ Block 2 ]
           else [ Block 3 ] 
  1. 循环语句有三种：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;   
  1. 数组元素的存取有数组名后跟“[下标]”表示。例如A[j]指示数组A的第j个元素。符号“ …”用来指示数组中值的范围。

例如：

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

  1. 复合数据用对象(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。

  1. 函数和过程语法与Pascal类似。

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

例如： 

   1. x ← t + 10
   2. y ← sin(x)
   3. call CalValue(x,y)

参数用按值传递方式传给一个过程：被调用过程接受参数的一份副本，若他对某个参数赋值，则这种变化对发出调用的过程是不可见的。当传递一个对象时，只是拷贝指向该对象的指针，而不拷贝其各个域。

算法的复杂性

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

摘要

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

目录

§                            简介

§                            比较两对算法的效率

§                            复杂性的计量

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

§                            复杂性渐近阶的重要性

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

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

§                            1.代入法

§                            2.迭代法

§                            3.套用公式法

§                            4.差分方程法

§                            5.母函数法

 

简介

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

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

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

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

  1. 用怎样的一个量来表达一个算法的复杂性；
  2. 对于给定的一个算法，怎样具体计算它的复杂性。

让我们从比较两对具体算法的效率开始。

比较两对算法的效率

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

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

Function Search (c:integer):integer;

Var J:integer;

Begin

 J:=1; {初始化}

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

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

 While (A[i]<c)and(j<m) do

         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只可能在A[m/2+1],A[m/2+2],..,A[m]之中，因而下一步只要在A[m/2+1],A[m/2+2],..,A[m]中继续查找。不管哪一种情形，都把下一步需要继续查找的范围缩小了一半。再拿这一半的子数组的中间分量与c比较，重复上述步骤。照此重复下去，总有一个时候，或者找到一个i使得A[i]=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[i]=c)=1/m 。若记Ti=T(m,Ii)，其中Ii表示A[i]=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)。

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

  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) 。根据记号Ο的定义，存在正常数C1和自然数N1，使得对所有的N≥N1，有F(N)≤C1 f(N)。类似地，设G(N)=Ο(g)，则存在正的常数C2和自然数N2使得对所有的