1.4 算法和算法分析

1.4.1 算法的概念

1.算法的定义

算法是由若干条指令所组成的有穷序列，其中每条指令表示计算机的一个或多个操作。

2.算法的特性

一个好的算法应该具有以下5个特性。

（1）有穷性。一个算法必须（对任何合法的输入值）在执行有限时间内完成，不能形成无穷循环。

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

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

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

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

3.好算法应达到的目标

算法与数据结构是相辅相成的。解决某一特定类型问题的算法可以选定不同的数据结构，而且选择恰当与否直接影响算法的效率。反之，一种数据结构的优劣由各种算法的执行来体现。

设计一个好的算法通常需要考虑以下几个方面的要求。

（1）正确性。要求算法能够正确地执行预先规定的功能，并达到所期望的性能要求。

（2）可读性。为了便于理解、测试和修改算法，算法应该具有良好的可读性。

（3）健壮性。当输入非法的数据时，算法应能恰当地做出反应或进行相应处理，而不是产生莫名奇妙的输出结果。并且处理出错的方法不应是中断程序的执行，而是返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理。

（4）高效性。要求算法的执行时间要尽可能的短，算法的效率就越高。

（5）低存储量。完成相同的功能，执行算法时所占用的附加存储空间要尽可能的少。

实际上，算法很难做到十全十美，因为上述要求有时会相互抵触。所以，实际操作中，应以算法正确为前提，根据具体情况而有所侧重。

1.4.2 算法的效率评价

一个好的算法首先要具备正确性、可读性和健壮性。在具备了这3个条件后，就应考虑算法的效率问题，即算法的时间效率（所需运算的时间）和空间效率（所占存储空间）两方面。对于求解同一个问题，可以设计出若干个算法，对于不同的算法进行性能分析是数据结构的一个重要内容。在算法满足正确性的前提下，如何评价不同算法的优劣呢？通常主要考虑算法的时间复杂度和空间复杂度这两方面。一般情况下，鉴于运算空间（内存）较为充足，所以把算法的时间复杂度作为重点分析。

1.时间复杂度（Time Complexity）

一个算法所需的运算时间通常与所解决问题的规模大小有关。问题规模是一个和输入有关的量，用n表示问题规模的量，通常把算法运行所需的时间T表示为n的函数，记为T（n）。不同的T（n）算法，当n增长时，运算时间增长的快慢很不相同。一个算法所需的执行时间就是该算法中所有语句执行次数之和。当n逐渐增大时T（n）的极限情况，一般简称为时间复杂度。

当讨论一个程序的运行时间时，注重的不是T（n）的具体值，而是它的增长率。T（n）的增长率与算法中数据的输入规模紧密相关，而数据输入规模往往用算法中的某个变量的函数来表示，通常是f（n）。随着数据输入规模的增大，f（n）的增长率与T（n）的增长率相近，因此T（n）同f（n）在数量级上是一致的。记作：

T（n）=O（f（n））

其中，大写字母O表示数量级（Order of Magnitude）的概念，f（n）为函数形式。例如，若T（n）= 3n2+5n+2，则3n2+5n+2的数量级与n2的数量级相同，所以T（n）=O（n2）。

注意，当T（n）为多项式时，可只取其最高次幂项并省略其系数，其他的次幂项及系数均略去不写。一般地，对于足够大的n，常用的时间复杂度（如图1-4所示）的大小次序如下：

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

算法时间复杂度的数量级越大，表示该算法的效率越低，反之越高。例如，O（1）为常数数量级，即算法的时间复杂性与输入规模n无关。

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

1  x=0;y=0;
2  for（k=1; k＜=n; k++）
3     x++;               （1）执行n次
4  for（i=1; i＜=n; i++）
5  for（j=1; j＜=n; j++）
6     y++;               （2）执行n2次

解：本程序有两个循环体，第一个循环的时间复杂度为n，第二个循环是双重循环，其时间复杂度为n2，所以上面程序段的时间复杂度为：

T（n）= n+n2

则其时间复杂度为：

T（n）=O（n2）

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

1  i=1;
2  while（i＜=n）
3     i=2*i;           （1）执行f（n）次

解：设第3行语句（1）执行次数是f（n），则2f（n）≤n，所以T（n）=O（log2n）。

【例1-8】 求两个矩阵相乘的函数的时间复杂度。

1  void mult（int a[][N], int b[][N], int c[][N]）
2  { /*以二维数组存储矩阵元素，c为a和b的乘积*/
3     for（i=0; i＜n; i++）                 （1） 执行n次
4       for（j=0; j＜n; j++）               （2） 执行n2次
5       {  c[i][j]=0;
6          for（k=0; k＜n; k++）            （3） 执行n3次
7          c[i][j]+=a[i][k]*b[k][j];
8       }
9  }

解：嵌套循环为每层循环次数的乘积，因为该函数为三重循环，所以时间复杂度为O（n3）。

2.空间复杂度（Space Complexity）

一个算法的空间复杂度是指程序运行开始到结束所需要的存储空间。包括算法本身所占用的存储空间、输入/输出数据占用的存储空间以及算法在运行过程中的工作单元和实现算法所需辅助空间。类似于算法的时间复杂度，算法所需存储空间的量度记作：

S（n）=O（f（n））

其中，n为问题的规模，一个程序上机执行时，除了需要存储空间来存放本身所用的指令、常数、变量和输入数据以外，还需要一些对数据进行操作的工作单元和实现算法所必需的辅助空间。在进行时间复杂度分析时，如果所占空间量依赖于特定的输入，一般都是按最坏情况来分析。