1.5 算法分析基础知识

算法（Algorithm）是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。

算法具有5个主要的特性：有穷性、确定性、可行性、输入、输出。

算法时间复杂度：算法在运行时所要花费的时间。

算法空间复杂度：算法在运行时所要花费的空间。

算法分析则主要考察算法的时间复杂度与空间复杂度，在空间不受限制的情况下，时间复杂度决定了一个算法的好坏。

1.5.1 算法描述

算法不同于程序代码，程序代码必须依赖于一种程序语言。算法只是对求解某个问题方法的描述，实现它的代码可以是C语言、C++、Delphi、Java等。

算法的描述方法有多种，常用的有：自然语言、伪代码、流程图等。

例：求N个数的平均值。N个数放在数组S中。

自然语言描述

          输入：数组S，个数N
          输出：平均值
          1 i=0
            sum = 0
          2 如果i＜N
            3 Sum = sum +S[i]
            4I=I+1 返回第2步
          5 返回sum/n

伪代码（类C伪代码）

          int aver(int ＊S, int N)
          {
          for(i=0;i＜N;i++)
              sum+=S[i];
          return sum/N;
          }

流程图如图1-5所示。

自然语言描述简单易懂，其中也包含一些简单的数学描述式。伪代码与程序代码很接近，省略了很多变量定义，以及与具体语言相关的细节，改写成程序最为容易。流程图直观，对算法的理解很有帮助。

1.5.2 算法时间复杂度分析

一个算法所耗费的时间是算法中所有语句执行时间之和，而每条语句的执行时间是该语句的执行次数（频度）与该语句执行一次所需时间（因机器不同而不同）的乘积。

为了消除机器硬件给算法时间分析带来的影响，我们并不真正计算算法运行实际所耗费的时间，而是以语句执行的次数代替语句执行的时间。通常，一个算法是由控制结构（顺序、选择和循环）和“原操作”（指固有数据类型的操作，一条基本语句）构成的，而算法时间复杂度取决于两者的综合效果。算法时间复杂度就是所有“原操作”执行次数之和，它一般与输入数据量n相关。

将求N个数平均值的算法按程序完整写出来，如下：

          1 int aver(int ＊S, int N)
          2 {
          3    int i,sum;
          4    for(i=0;i＜N;i++)
          5        sum+=S[i];
          6    return sum/N;
          7 }

第1，2，7行代码都是函数定义相关的，不占用时间。

第3行为变量定义，不占用时间。

第4行为控制语句，在分析的时候忽略。

第5行为“原操作”，执行1次（不考虑具体执行时间为多少秒），但第4行的循环控制了第5行要执行N次。

第6行为“原操作”，执行1次。

所以总的时间为N+1。

一般，一个算法所耗费的时间将随输入数据量n的增大而增大。所以算法的时间复杂性是输入数据量n的函数，这时就称该算法的时间代价为T（n）。

评价算法的时间复杂性，就是设法找出T(n)和n的关系，即求出T（n）。如T(n)=3n2+4n+10。在进行算法分析的时候，一般考虑当n充分大时的情况，所以常常用渐进时间复杂性来表示。当n充分大时，3n2是时间耗费的主要方面，4n及常数10都是次要方面。3n2中，3n2又是主要方面，常数3又是次要方面。用渐进符号O来表示，则T(n)=O(n2)。

再来看求平均值的例子，总时间为N+1。当N充分大时，1可以忽略不计。所以时间复杂性为O(n)。

有时候，“原操作”执行次数并不是一眼就能看清楚的。看下面这个例子：

          1 int search(int alpha,int beta,int depth)
          2 {
          3    if(depth＜0)
          4        return Eval();
          5
          6    n = Gen();
          7    for(i=0;i＜n;i++)
          8    {
          9        value = search(-beta, -alpha, depth-1);  //递归调用
          10       if(value ＞ beta)
          11           return beta;
          12       if(value ＞ alpha)
          13           alpha =value;
          14   }
          15   return alpha;
          16 }

这是本书后面重点要介绍的搜索算法，在这里做了简化。

可以看出由for循环控制的第9行代码执行次数最多，执行了n次。由10，11行代码也看出，循环控制随时有中断的可能。只能说最坏情况下执行n次。注意这里的n是一个不确定的值，它由第6行的函数调用产生。另外值得注意的是，第9行代码本身是一个函数调用，而且是递归调用。所以要分析这样一个算法的时间复杂性就比较难了。

一个简化的方法就是在程序执行时进行统计。在函数外变量一个统计变量，在函数内部进行计数。

          0 int num = 0;
          1 int search(int alpha,int beta,int depth)
          2 {
          3    if(depth＜0)
          4        return Eval();
          5    num++;
          6    n = Gen();
          7    for(i=0;i＜n;i++)
          8    {
          9        value = search(-beta, -alpha, depth-1);  //递归调用
          10       if(value ＞ beta)
          11           return beta;
          12       if(value ＞ alpha)
          13           alpha =value;
          14   }
          15   return alpha;
          16 }

如果是要统计第9行代码执行的次数则将num++放在第9行之前就行。这里把它放在第5行处，是结合搜索算法的具体意义，即统计搜索树中展开结点的个数。