1.2 算法和算法分析

1.2.1 算法及其描述

1．算法的特性

一个运算实现是通过算法来表述的，算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每条指令表示一个或多个操作。算法设计应满足以下几条目标。

（1）正确性：要求算法能够正确地执行预先规定的功能和性能要求。这是最重要也是最基本的标准。

（2）可使用性：要求算法能够很方便地使用。这个特性也叫作用户友好性。

（3）可读性：算法应该易于人的理解，也就是可读性好。为了达到这个要求，算法的逻辑必须是清晰的、简单的和结构化的。

（4）健壮性：要求算法具有很好的容错性，即提供异常处理，能够对不合理的数据进行检查。不经常出现异常中断或死机现象。

（5）高效率与低存储量需求：通常算法的效率主要指算法的执行时间。对于同一个问题如果有多种算法可以求解，执行时间短的算法效率高。算法存储量指的是算法执行过程中所需的最大存储空间。效率和低存储量这两者都与问题的规模有关。

【例1.5】即使输入非法数据，算法也能适当地做出反应或进行处理，不会产生预料不到的运行结果，这种算法好坏的评价因素称为________。

A．正确性

B．易读性

C．健壮性

D．时空性

解：一个算法对于非法数据输入不会产生预料不到的运行结果，称为算法的健壮性。本题答案为C。

算法具有以下5个重要特性。

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

（2）确定性：算法中每一条指令必须有确切的含义，不会产生二义性。

（3）可行性：算法中每一条运算都必须是足够基本的，就是说它们原则上都能精确地执行，甚至人们仅用笔和纸做有限次运算就能完成。

（4）输入性：一个算法有零个或多个输入。大多数算法中输入参数是必要的，但对于较简单的算法，如计算1+2的值，不需要任何输入参数，因此算法的输入可以是零个。

（5）输出性：一个算法有一个或多个输出。算法用于某种数据处理，如果没有输出，这样的算法是没有意义的，这些输出是同输入有着某些特定关系的量。

说明：算法和程序是有区别的，程序是指使用某种计算机语言对一个算法的具体实现，即具体要怎么做，而算法侧重于对解决问题的方法描述，即要做什么。算法必须满足有限性，而程序不一定满足有限性，如Windows操作系统在用户没有退出、硬件不出现故障以及不断电的条件下理论上可以无限时运行，所以严格讲算法和程序是两个不同的概念。当然算法也可以直接用计算机程序来描述，这样算法和程序就是一回事了，本书就采用这种方式。

【例1.6】有下列两段描述：

这两段描述均不能满足算法的特性，试问它们违反了算法的哪些特性？

解：①这是一个死循环，违反了算法的有限性特性。②出现除零错误，违反了算法的可行性特性。

2．算法的描述

描述算法的方式很多，有的采用类Pascal语言，有的采用自然语言伪码。本书采用C/C++语言来描述算法的实现过程，通常用C/C++函数来描述算法。

以设计求1+2+…+n值的算法为例说明C/C++语言描述算法的一般形式，该算法如图1.16所示。

通常用函数的返回值表示算法能否正确执行，有时当算法只有一个返回值或者返回值可以区分算法是否正确执行时，用函数返回值来表示算法的执行结果，另外还可以带有形参表示算法的输入输出。任何算法（用函数描述）都是被调用的（在C/C++语言中除main函数外任何一个函数都会被其他函数调用，如何一个函数不被调用，这样的函数是没有意义的）。在C语言中调用函数时只有从实参到形参的单向值传递，执行函数时若改变了形参而对应的实参不会同步改变。例如，设计以下主函数调用图1.16中的Sum1函数。

      void main()
      {    int a=10,b=0;
           if(Sum1(a,b))printf(＂%d\n＂,b);
           else printf(＂参数错误\n＂);
      }

执行时发现输出结果为0。这是因为b对应的形参为s（在内存中b和s存放在不同的位置），Sum1函数执行后s=55，但s并没有回传给b，b的值仍然为0。在C语言中可以用传指针方式来实现形参的回传，但增加了函数设计的复杂性。为此C++语言中增加了引用型参数的概念，引用型参数名前需加上&，表示这样的形参在执行后会将结果回传给对应的实参。上例采用的C++语言描述算法如图1.17所示。

当将形参s改为引用类型的参数后，执行时main函数的输出结果就正确了，即输出55。由于C语言不支持引用类型，C++语言支持引用类型，所以本书算法描述语言为C/C++语言，实际上除引用类型外，其他均用C语言的语句。

需要注意的是，在C/C++语言中，数组本身就是一种引用类型，所以当数组作为形参需要回传数据时，其数组名之前不需要加引用等&，它自动将形参数组的值回传给实参数组。

算法中引用型参数的作用如图1.18所示。在设计算法时，如果某个形参需要将执行结果回传给实参，需要将该形参设计为引用型参数。带有引用型参数的程序不能在Turbo C中运行，可以在Visual C++、Dev C++、BC++等编译环境中运行。

说明：C语言没有提供实参到形参的双向传递，可以说这是C语言的一个缺陷，在很多计算机语言中都改进了这一点，例如在Visual Basic语言中，函数形参需要指定是ByVal（单向值传递）还是ByRef（双向传递）。在C++中提供了引用类型，通过将函数形参定义为引用类型以实现实参到形参的双向传递。

所以在设计一个算法时，先要弄清楚哪些是算法的输入，哪些是算法的输出。将输入采用输入型参数表示（每个参数含数据类型和参数名称），而输出采用输出型参数表示，输出型参数名称的前面加上引用符号“&”。有些情况下，输入和输出是合为一体的，此时将其作为输出型参数处理。

例如，交换两个整数x和y的值，对于算法swap而言，x和y既是输入又是输出，需要将它们设计成引用型参数，算法如下。

      void swap(int &x,int &y)
      {    int tmp=x;
           x=y;y=x;
      }

1.2.2 算法分析

计算机资源主要包括计算时间和内存空间。算法分析是分析算法占用计算机资源的情况，所以算法分析的两个主要方面是分析算法的时间复杂度和空间复杂度，其目的不是分析算法是否正确或是否容易阅读，主要是考察算法的时间和空间效率，以求改进算法或对不同的算法进行比较。

那么如何评价算法的效率呢？通常有两种衡量算法效率的方法：事后统计法和事前分析估算法。前者存在这些缺点：一是必须执行程序，二是存在其他因素掩盖算法本质。所以下面均采用事前分析估算法来分析算法效率。

1．算法时间复杂度分析

一个算法用高级语言实现后，在计算机上运行时所消耗的时间与很多因素有关，如计算机的运行速度、编写程序采用的计算机语言、编译产生的机器语言代码质量和问题的规模等。在这些因素中，前三个都与具体的机器有关。撇开这些与计算机硬件、软件有关的因素，仅考虑算法本身的效率高低，可以认为一个特定算法的“运行工作量”的大小，只依赖于问题的规模（通常用整数量n表示），或者说，它是问题规模的函数，这就是事前分析估算法的基本思路。

一个算法是由控制结构（顺序、分支和循环三种）和原操作（指固有数据类型的操作）构成的，算法的运行时间取决于两者的综合效果。例如，如图1.19所示是算法Solve，其中形参a是一个m行n列的数组，当a是一个方阵（m=n）时求主对角线所有元素之和并返回1，否则返回0。从中看到该算法由4部分组成，包含两个顺序结构、一个分支结构和一个循环结构。

算法的执行时间主要与问题规模有关，例如数组的元素个数、矩阵的阶数等都可作为问题规模。所谓一个语句的频度，即指该语句在算法中被重复执行的次数。算法中所有语句的频度之和记作T（n），它是问题规模n的函数。一个算法的语句的频度之和T（n）与算法的执行时间成正比，所以可以将T（n）看作算法的执行时间。当问题规模n趋向无穷大时，T（n）的数量级称为渐进时间复杂度，简称为时间复杂度，记作T（n）=O（f（n））。

上述表达式中，“O”的含义是为T（n）找到了一个上界f（n），其严格的数学定义是：T（n）的数量级表示为O（f（n）），是指存在正常量c≠0和n0（为一个足够大的正整数），使得成立。如图1.20所示，当n≥n时，总有T（n）≤cf（n）成立。0

例如，T（n）=5n3—2n2+3n—100，则T（n）=O（n3），因为。T（n）≠O（n4），因为，当n足够大时，c1值趋于0。T（n）≠O（n2），因为c2=，当n足够大时，c2值趋于∞。

另外，由于算法的时间复杂度是T（n）数量级，而算法中基本运算语句的频度与T（n）同数量级，所以通常采用算法中基本运算语句的频度来分析算法的时间复杂度，被视为算法基本运算的语句一般是最深层循环内的语句，如图1.19所示的算法中s+=a[i][i]就是该算法的基本运算语句。

用O（f（n））表示算法执行时间T（n）的时候，函数f（n）通常取较简单的形式，如O（1）、O（log2n）、O（n）、O（nlog2n）、O（n2）、O（n3）、O（2n）等。在n较大的情况下，常见的时间复杂度之间存在下列关系。

O（1）＜O（log2n）＜O（n）＜O（nlog2n）＜O（n2）＜O（n3）＜O（2n）＜O（n!）

对于求1+2+…+n值，如图1.17所示的算法（称为算法1）不如下面的算法（称为算法2）好。

      int Sum2(int n,int &s)
      {    if(n<0)return 0;
           else return n ∗ (n+1)/2;
      }

因为算法1的时间复杂度为O（n），而算法2的时间复杂度为O（1）。

一般地，若T1（n）、T2（n）是程序段P1、P2的执行时间，并且T1（n）=O（f（n）），T2（n）= O（g（n）），则先执行P1，再执行P2的总执行时间是T1（n）+T2（n）=O（MAX（f（n），g（n））（其中MAX为取最大值函数），这称为加法规则。乘法规则是，T1（n）×T2（n）=O（f（n）×g（n）），用于多重循环的情况。

例如，每个简单语句，如赋值语句、输入输出语句，它们的执行时间与问题规模无关，对应的时间复杂度为O（1）。对于条件语句if（条件）子句1 else子句2，if的条件判断通常为O（1），对应的时间复杂度为MAX（O（子句1），O（子句2））。循环语句往往与问题规模n相关，一重循环对应的时间复杂度为O（n），对于多重循环，应分析其中基本运算语句的执行次数，以此求出对应的时间复杂度。

【例1.7】分析以下算法的时间复杂度。

解：本算法用于计算两个n阶方阵a和b相乘，并将结果存放到方阵c中。这里采用两种方法分析算法的时间复杂度。

方法1：从求算法中所有语句的频度来分析算法时间复杂度。语句①的执行频度为n+1（注意i＜n判断语句需执行n+1次）；语句②的执行频度为n（n+1）；语句③的执行频度为n2；语句④的执行频度为n2（n+1）；语句⑤的执行频度为n3。

算法的执行时间是其中所有语句频度之和，故：

T（n）=2n3+3n2+2n+1=O（n3）

方法2：从算法中基本运算的频度来分析算法时间复杂度。本算法中的基本运算是语句⑤，其执行频度为n3。则：

T（n）=n3=O（n3）

从中看到，两种方法的结果相同，而第二种方法更加简洁。

【例1.8】程序段

      i=n; x=0;
      do
      {   x=x+5 ∗ i;
          i——;
      } while(i>0);

的时间复杂度为________。

A．O（1）

B．O（n）

C．O（n2）

D．O（n3）

解：该程序段中while循环内的语句为基本运算语句，设其运算次数为T（n），i从n开始，直到i=0结束，所以T（n）=n=O（n）。本题答案为B。

【例1.9】给出以下算法的时间复杂度。

解：其中基本运算语句是while循环内的语句。设while循环语句执行的次数为m，i从1开始递增，最后取值为1+2m，有：

i=1+2m≤n，

即

T（n）=m≤（n—1）/2=O（n）

该算法的时间复杂度为O（n）。

2．算法空间复杂度分析

一个算法的存储量包括形参所占空间和临时变量所占空间等。在对算法进行存储空间分析时，只考察临时变量所占空间，如图1.21所示，其中临时空间为变量i、maxi占用的空间。所以，空间复杂度是对一个算法在运行过程中临时占用的存储空间大小的量度，一般也作为问题规模n的函数，以数量级形式给出，记作：S（n）=O（g（n）），其中，“O”的含义与时间复杂度中的含义相同。

若所需临时空间相对于输入数据量来说是常数，则称此算法为原地工作或就地工作。若所需临时空间依赖于特定的输入，则通常按最坏情况来考虑。

为什么算法占用的空间只考虑临时空间，而不必考虑形参的空间呢？这是因为形参的空间会在调用该算法的算法中考虑，例如，以下maxfun算法调用图1.21的max算法：

      void maxfun()
      {    int b[]={1,2,3,4,5},n=5;
           printf(＂Max=%d\n＂,max(b,n));
      }

maxfun算法中为b数组分配了相应的内存空间，其空间复杂度为O（n），如果在max算法中再考虑形参a的空间，这样就重复计算了占用的空间。实际上，在C/C++语言中，maxfun调用max时，max的形参a只是一个指向实参b数组的指针，形参a只分配一个地址大小的空间，并非另外分配5个整型单元的空间。

【例1.10】分析例1.7和例1.9算法的空间复杂度。

解：这两个算法中，需临时分配空间的变量只有固定几个变量，故它们的空间复杂度均为O（1），即这些算法均为原时工作算法。