1.3 算法及算法分析

算法与数据结构的关系非常紧密，在算法设计时总是先要确定相应的数据结构，而在讨论某一种数据结构时也必然会涉及相应的算法。下面就从算法特性、算法描述和算法分析三个方面对算法进行介绍。

1.3.1 算法特性

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

（1）有穷性：一个算法必须在有穷步之后结束，即必须在有限时间内完成。

（2）确定性：算法的每一步必须有确切的定义，无二义性，且在任何条件下算法只有唯一一条执行路径，即对于相同的输入只能得出相同的输出。

（3）可行性：算法中的每一步都可以通过已经实现的基本运算的有限次执行得以实现。

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

（5）输出：一个算法具有一个或多个输出，这些输出同输入之间存在某种特定的关系。

算法的含义与程序十分相似，但又有区别。一个程序不一定满足有穷性。例如，对于操作系统，只要整个系统不遭破坏，它将永远不会停止，即使没有作业需要处理，它仍处于动态等待中。因此，操作系统不是一个算法。另外，程序中的指令必须是机器可执行的，而算法中的指令则无此限制。算法代表了对问题的求解方法，而程序则是算法在计算机上的特定实现。一个算法若用程序设计语言来描述，就是一个程序。

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

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

（1）正确性：算法的执行结果应当满足预先规定的功能和性能要求。正确性要求表明算法必须满足实际需求，达到解决实际问题的目标。

（2）可读性：一个算法应当思路清晰、层次分明、简单明了、易读易懂。可读性要求表明算法主要是人与人之间交流解题思路和进行软件设计的工具，因此可读性必须要强。同时一个可读性强的算法，其程序的可维护性、可扩展性都要好得多，因此，许多时候人们往往在一定程度上牺牲效率来提高可读性。

（3）健壮性：当输入不合法数据时，应能适当处理，不至于引起严重后果。健壮性要求表明算法要全面细致地考虑所有可能的边界情况，并对这些边界条件做出完备的处理，尽可能使算法没有意外的情况。

（4）高效性：有效使用存储空间和有较好的时间效率。高效性主要是指时间效率，即解决相同规模的问题时间尽可能短。

一般来说，数据结构上的基本操作主要有以下几种。

（1）查找：寻找满足特定条件的数据元素所在的位置。

（2）读取：读出指定位置上数据元素的内容。

（3）插入：在指定位置上添加新的数据元素。

（4）删除：删去指定位置上对应的数据元素。

（5）更新：修改某个数据元素的值。

1.3.2 算法描述

算法的描述方法很多，根据描述方法的不同，大致可将算法描述分为以下4种。

（1）自然语言算法描述：用人类自然语言（如中文、英文等）来描述算法，同时还可插入一些程序设计语言中的语句来描述，这种方法也称为非形式算法描述。其优点是不需要专门学习，任何人都可以直接阅读和理解，但直观性很差，复杂的算法难写难读。

（2）框图算法描述：这是一种图示法，可以采用方框图、流程图、N-S图等来描述算法，这种描述方法在算法研究的早期曾流行过。它的优点是直观、易懂，但用来描述比较复杂的算法就显得不够方便，也不够清晰简洁。

（3）伪代码算法描述：如类C语言算法描述。这种算法描述很像程序，但它不能直接在计算机上编译、运行。这种方法很容易编写、阅读算法，而且格式统一，结构清晰，专业设计人员经常使用类C语言来描述算法。

（4）高级程序设计语言编写的程序或函数：这是直接用高级语言来描述算法，它可在计算机上运行并获得结果，使给定问题能在有限时间内被求解，通常这种算法描述也称为程序。

【例1.5】 求两个整数m、n(m≥n)的最大公因子，该算法的不同描述方法如下。

（1）非形式算法描述（自然语言算法描述）如下。

① [求余数]以n除m，并令r为余数(0≤r<n)；

② [判断余数是否为零]若r=0，则结束算法，n就是最大公因子；

③ [替换并返回步骤①]若r≠0，则m ← n，n ← r，返回步骤①。

（2）算法的框图描述如图1.7所示。

（3）C语言函数描述如下。

int max_common_factor(int m，int n)
{
int r；
r＝m%n ；
while(r!＝0)
      { m=n；n=r；r=m%n；}
        return n ；
}

本书主要介绍算法的思路和实现过程，且尽可能地给出算法对应的C语言函数或程序（或类C语言算法描述），方便读者阅读或上机运行，以便更好地理解算法。

1.3.3 算法分析

所谓好的算法，除了满足上文提到的几个基本要求外，还必须以较少的时间与空间代价来解决相同规模的问题。因此，一个算法的优劣，可以从该算法在计算机上运行的时间和所占存储空间来衡量和评判。算法分析就是预先分析算法在实际执行时的时空代价指标。

当一个算法被转换成程序并在计算机上执行时，其运行所需要的时间一般取决于下列几个因素。

（1）硬件的速度。即主机本身运行速度，主要与CPU的主频和字长有关，也与主机系统采用的技术有关，如多机系统的运算速度一般比单机系统要快。

（2）实现算法的程序设计语言。实现算法的语言的级别越高，其执行效率相对就越低。

（3）编译程序所生成目标代码的质量。代码优化较好的编译程序所生成的程序质量较高。

（4）算法所采用的策略。采用不同设计思路与解题方法，其时空代价是不同的，一般情况下时间指标与空间指标常常是矛盾的两个方面。

（5）问题的规模。例如，求100以内的素数与求1 000以内的素数的执行时间必然不同。

显然，在各种因素都不能确定的情况下，很难比较算法的执行时间。也就是说，用算法的绝对执行时间来衡量算法的效率是不合适的。为此，可以将上述各种与计算机相关的软、硬件因素都确定下来，仅对采用不同策略的算法，分析其运行代价随问题规模大小变化的对应关系，即运行代价仅依赖于问题的规模（通常用正整数n表示），或者说它是问题规模的函数。这种函数被称为算法的时间复杂度和空间复杂度。

1.时间复杂度

一个程序的时间复杂度（Time Complexity）是指该程序的运行时间与问题规模的对应关系。一个算法是由控制结构和原操作（所谓原操作是指从算法中选取对于所研究问题是基本运算的操作）构成的，其执行时间取决于两者的综合效果。为了便于比较同一问题的不同的算法，通常的做法是：从算法中选取一种对于所研究的问题来说是基本运算的原操作，以该原操作重复执行的次数为算法的时间度量。一般情况下，算法中原操作重复执行的次数是该算法所处理问题的规模n的某个函数T(n)。

【例1.6】 两个n×n阶的矩阵相乘的程序中的主要语句及其重复次数如下。

原操作语句的执行频度

for ( i=0；i<n；i++ )
    for ( j=0；j<n；j++ )
      {  s [ i ][ j ]=0；                  n2
         for ( k=0；k<n；k++ )
            s [ i ][ j ]=s [ i ][ j ]+a [ i ][ k ] * b [ k ][ j ]；    n3
}

则该段程序的时间复杂度T(n)=cn3+n2，其中c为常量，表示算术运算时间是简单赋值运算时间的常数倍。

许多时候，精确地计算T(n)是困难的，人们引入渐进时间复杂度在数量上估计一个算法的执行时间，也能够达到分析算法的目的。

定义（大Ο记号）：如果存在两个正常数c和n0，使得对所有的n（n≥n0），有：

T(n) ≤ c*f (n)

则T(n)＝Ο( f (n))。

例如，一个程序的实际执行时间为T(n)＝2.7n3+3.8n2+5.3，则T(n)＝Ο(n3)。

使用大Ο记号表示的算法的时间复杂度称为算法的渐进时间复杂度（Asymptotic Time Complexity）。

通常用Ο(1)表示常数级时间复杂度，表明这样的算法执行时间是恒定的，不随问题规模的扩大而增长，显然这是最理想的，但往往难以实现。此外，常见的渐进时间复杂度还有：

（1）O(log2n)，对数级复杂度；

（2）Ο(n)，线性复杂度；

（3）Ο(n2)和Ο(n3)，分别为平方级和立方级复杂度；

（4）Ο(2n)，指数级复杂度。

上述时间复杂度随问题规模n的扩大其增长速度是不同的，其增长速度的快慢次序表示如下：

Ο(1)<Ο(log2n)<Ο(n)<Ο(nlog2n)<Ο(n2)<Ο(n3)<Ο(2n)

2.空间复杂度

一个程序的空间复杂度（Space Complexity）是指程序运行从开始到结束所需的存储量与问题规模的对应关系，记做：

S(n)=Ο(f(n))

其中n为问题的规模（或大小）。

一个上机执行的程序除了需要存储空间来寄存本身所用指令、常数、变量和输入数据外，还需要一些对数据进行操作的工作单元和存储为实现计算所需信息的辅助空间。若输入数据所占空间只取决于问题本身、和算法无关，则只需分析除输入数据和程序之外的额外空间，否则应同时考虑输入数据本身所需空间（和输入数据的表示形式有关）。若额外空间相对于输入数据量来说是常数，则称此算法为原地工作，辅助空间为Ο(1)。如果所占空间量依赖于特定的输入，则除特别指明外，均按最坏情况来分析。

算法执行时间的耗费和所占存储空间的耗费是相互矛盾的，难以兼得。即算法执行时间上的节省是以增加存储空间为代价的，反之亦然。不过，一般而言，常常已以算法执行时间作为算法优劣的主要衡量指标。