1.3 算法和算法的分析

1.3.1 算法及算法的描述

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

（1）有穷性。一个算法必须总是（对任何合法的输入值）在执行有穷步之后结束，且每一步都可在有穷时间内完成。

（2）确定性。算法中每一条指令必须有确切的含义，不能产生二义性。在任何条件下，算法只有唯一的一条执行路径，即对于相同的输入只能得出相同的输出。

（3）可行性。一个算法是可行的，即算法中描述的操作可通过已经实现的基本运算执行有限次来实现。

（4）输入。一个算法有零个或多个输入，这些输入取自于某个特定的对象的集合。

（5）输出。一个算法有一个或多个输出。这些输出是与输入有着一定关系的量。

《数据结构》中所讨论的算法，可用不同的方式进行描述，常用的有类Pascal、类C、类C++、类Java程序设计语言，本教材以类C语言为描述工具。每一算法可用一个或多个简化了的C语言（类C）函数进行描述，简化是针对高级语言的语法细节所做的，如对函数内部的局部变量可不作声明而直接使用，交换两个变量x、y的值，不使用3条赋值语句，而仅简记为一条语句x←→y；再如对结构体变量可以整体赋值，等等。需要注意的是，《数据结构》中的算法，因为用类C描述，所以不等同于C语言程序，若要上机运行某一算法，则必须将其完善为C语言程序。即增加main()函数，main()函数中增添实现算法的函数调用语句，在实现算法的函数中补充、完善语法细节。

1.3.2 算法设计的要求

1.正确性

正确性的含义是算法对于一切合法的输入数据都能够得出满足规格说明要求的结果，事实上要验证算法的正确性是极为困难的，因为通常情况下合法的输入数据量太大，用穷举法逐一验证是不现实的。所谓的算法正确性是指算法达到了测试要求。

2.可读性

可读性是指人对算法阅读理解的难易程度，可读性高的算法便于人之间的交流，有利于算法的调试与修改。

3.健壮性

对于非法的输入数据，算法能给出相应的响应，而不是产生不可预料的后果。

4.效率与低存储量需求

效率指的是算法的执行时间。对于解决同一问题的多个算法，执行时间短的算法效率高。存储量需求指算法执行过程中所需要的最大存储空间。效率与低存储量需求两者都与问题的规模有关，求100个人的平均分与求1000个人的平均分显然不同。

1.3.3 算法的分析

1.算法效率的度量

算法执行的时间是其对应的程序在计算机上运行所消耗的时间。程序在计算机上运行所需时间与下列因素有关：

（1）算法本身选用的策略；

（2）书写程序的语言；

（3）编译产生的机器代码质量；

（4）机器执行指令的速度；

（5）问题的规模。

度量一个算法的效率应抛开具体机器的软、硬件环境，而书写程序的语言、编译产生的机器代码质量、机器执行指令的速度都属于软、硬件环境。对于一个特定算法只考虑算法本身的效率，而算法自身的执行效率是问题规模的函数。对同一个问题，选用不同的策略就对应不同的算法，不同的算法对应有各自的问题规模函数，根据这些函数就可以比较（解决同一个问题的）不同算法的优劣。

2.算法的时间复杂度

一个算法的执行时间大致上等于其所有语句执行时间的总和，语句的执行时间是指该条语句的执行次数和执行一次所需时间的乘积。语句执行一次实际所需的具体时间是与机器的软、硬件环境（机器速度、编译程序质量和输入数据等）密切相关的，与算法设计的好坏无关。所以，可以用算法中语句的执行次数来度量一个算法的效率。

首先定义算法中一条语句的语句频度，语句频度是指语句在一个算法中重复执行的次数。以下给出了两个n×n阶矩阵相乘算法中的各条语句，以及每条语句的语句频度。

语句       语句频度
for (i=0;i<n;i++)     n+1
     for (j=0;j<n;j++)     n(n+1)
         {  c[i][j]=0;       n2
            for (k=0;k<n;k++)   n2(n+1)
                c[i][j]=c[i][j]+a[i][k]*b[k][j];n3
         }

算法中所有语句的总执行次数为Tn=2n3+3n2+2n+1，从中可以看出，语句总的执行次数是问题的规模（矩阵的阶）n的函数f(n)（Tn=f(n)）。进一步简化，可用Tn表达式中n的最高次幂，即最高次幂项忽略其系数来度量算法执行时间的数量级，称为算法的时间复杂度，记做：

T(n)=O(f(n))

以上算法的时间复杂度为T(n)=O(n3)。

算法中所有语句的总执行次数Tn是问题规模n的函数，即Tn=f(n)，其中n的最高次幂项与算法中称为原操作的语句的语句频度对应，原操作是实现算法基本运算的操作，上面算法中的原操作是c[i][j]=c[i][j]+a[i][k]*b[k][j]。一般情况下原操作由最深层循环内的语句实现。

T(n)随n的增大而增大，增长得越慢，其算法的时间复杂度越低。下列3个程序段中分别给出了原操作count++的3个不同数量级的时间复杂度。

（1）count++；

其时间复杂度为O(1)，称为常数阶时间复杂度。

（2）for (i=1;i<=n;i++)

count++;

其时间复杂度为O(n)，是线性阶时间复杂度。

（3）for (i=1;i<=n;i++)

for (j=1;j<=n;j++)
     count++;

其时间复杂度为O(n2)，是平方阶时间复杂度。

又如以下两个算法，它们所呈现的时间复杂度分别是O(log2n)和O(n×m)。

（1）i=1；

while (i<n)
    i=2*i;

（2）for (i=0;i<n;i++)

for (j=0;j<m;j++)
     a[i][j]=0;

3.最坏时间复杂度

算法中基本操作重复执行的次数还随问题的输入数据集的不同而不同，例如下面的冒泡排序算法：

void Bubble(int a[], int n)
/*对整数数组a中的n个元素从小到大排序*/
{  int i=0, j;
   int change ;
   do
   {  change=0 ;
      for (j=0;j<n-i-1;j++)
      if( a[j]>a[j+1])
          {
                  a[j]←→ a[j+1];/*交换序列中相邻的两个整数*/
                  change=1;
          }
       i=i+1 ;
   }while (i<n-1 && change )
}

在这个算法中，“交换序列中相邻的两个整数”（a[j]←→a[j+1]）为原操作。当a中初始序列为自小到大有序时，原操作的执行次数为0；当初始序列为自大到小有序时，原操作的执行次数为n(n-1)/2。对于这类算法时间复杂度的分析，一种解决的方法是计算它的平均值，即考虑它对所有可能输入数据集的期望值，此时相应的时间复杂度为算法的平均时间复杂度。然而在很多情况下，算法的平均时间复杂度是难以确定的，通常的做法是讨论算法在最坏情况下的时间复杂度。例如，冒泡排序在最坏情况下（初始序列为自大到小有序时）的时间复杂度就为T(n)=O(n2)。本教材中，如不进行特殊说明，所讨论的各算法的时间复杂度均指最坏情况下的时间复杂度。

4.常见的时间复杂度

常见的时间复杂度有：O(1)常数阶、O(n)线性阶、O(n2)平方阶、O(n3)立方阶、O(2n)指数阶、O(log2n)对数阶和线性对数阶O(nlog2n)。时间复杂度（从小到大排列）的比较如表1-2所示。

表1-2 常用的时间复杂度的比较

5.算法的空间复杂度

关于算法的存储空间需求，类似于算法的时间复杂度，采用空间复杂度作为算法所需存储空间的量度，记为

S(n)=O(f(n))

其中n为问题的规模。一般情况下，一个程序在机器上执行时，除了需要寄存程序本身所用的指令、常数、变量和输入数据以外，还需要一些对数据进行操作的辅助存储空间。其中对于输入数据所占的具体存储量只取决于问题本身，与算法无关，这样只需要分析该算法在实现时所需要的辅助空间单元数就可以了。若算法执行时所需要的辅助空间相对于输入数据量而言是个常数，则称这个算法为原地工作，辅助空间为O(1)。如果所占辅助空间量依赖于特定的输入，则除特别指明外，均按最坏情况来分析。

算法的执行时间和存储空间的耗费是一对矛盾体，即算法执行的高效通常是以增加存储空间为代价的，反之亦然。不过，就一般情况而言，常常以算法执行时间作为算法优劣的主要衡量指标。本教材对算法的空间复杂度不作进一步讨论。