1.4　算法和算法分析

1.4.1　算法

算法是计算机科学中的基本概念，是对特定问题的求解步骤。算法须具有下列五个特征。

（1）输入：一个算法有0个或多个输入。

（2）输出：一个算法产生一个或多个输出，作为算法运算的结果。

（3）可行性：算法的每一个步骤都可以通过已经实现的基本运算来实现。

（4）确定性：算法的每一个步骤都必须有确切的含义，不会产生二义性。

（5）有穷性：算法必须能在执行有穷步之后终止。

算法的描述方式多种多样，可以用自然语言、流程图、程序设计语言或伪代码来描述。为了方便读者理解算法和上机验证算法，本书采用自然语言描述算法思想，并使用C语言描述算法的实现。

衡量一个算法的优劣，主要有以下几个基本标准。

（1）正确性

在合理的数据输入下，算法能够在有限的时间内产生满足预先规定的功能和性能要求。

（2）可读性

一个好的算法应当思路清晰、简单明了。可读性高的算法便于人们阅读、理解和交流；晦涩难懂的算法容易隐藏错误，不易被发现和调试。

（3）健壮性

一个好的算法应在输入不合法数据时，能做出适当处理，而不至于产生异常或是出现崩溃等严重后果。

（4）高效性

评价一个算法的效率主要包括时间和空间两方面。好的算法应具备执行效率高和占用存储空间少的特点。时间复杂度和空间复杂度是衡量算法效率的两个重要指标。

1.4.2　算法的时间复杂度

算法执行时间需通过依据该算法编制的程序在计算机上运行时所消耗的时间来度量。算法的时间复杂度一般是指程序运行从开始到结束所需的时间。而度量一个程序的执行时间通常有两种方法：事后统计法和事前估算法。事后统计法是将算法实现后计算其时间和空间开销，从而确定算法的效率。然而，时间和空间开销的计算与计算机软硬件环境相关，同一个算法在不同的机器上执行所花的时间也不一样，这种方法存在明显的缺陷，因此，不予采纳。本书采用事前估算法评估算法效率。

抛开与计算机软硬件相关的因素，影响算法时间效率最主要的因素是问题规模。问题规模通常是指算法的输入量，一般用整数n表示。例如，采用相同的排序算法对10个元素进行排序与对100 000个元素进行排序所需的时间显然是不同的。

一个算法时间花销与算法中语句的执行次数成正比例。算法中语句执行次数多，它的时间花销就多。一个算法中的语句执行次数称为语句频度。

一般情况下，算法中基本运算执行次数用T(n)表示，若有问题规模n的某个函数f(n)，使存在自然数n0，正常数c，当n大于等于n0时，T(n)≤cf(n)，则称f(n)是T(n)的渐近上界。记为

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

大O记号表示算法的一种渐近时间复杂度。渐近时间复杂度也常简称为时间复杂度。大O记号用以表达一个算法运行时间的上界，估计算法的执行时间的数量级。

下面举例说明算法的渐近时间复杂度的求解。

程序1.1　简单求和程序

程序1.1语句执行次数为5，算法的渐近时间复杂度为O(1)，属于常数级。

程序1.2　累加求和程序

程序1.2语句执行次数为2n+4，算法的渐近时间复杂度T(n)=O(n)。

程序1.3　矩阵求和程序

程序1.3语句执行次数为3+n+1+n(n+1)+n2=2n2+2n+4，算法的渐近时间复杂度T(n)=O(n2)。

一般情况下，可以通过考察一个程序中的关键操作的执行次数来计算算法的渐近时间复杂度。所谓关键操作是对算法执行时间贡献最大的操作。例如，程序1.2中，语句sum=sum+1可被认为是关键操作，其执行次数为n，由此计算可得算法的渐近时间复杂度也是O(n)。

常见的渐近时间复杂度从小到大依次是O(1)<O(log2 n)<O(n)<O(nlog2 n)<O(n2)<O(n3)。

1.4.3　最坏、最好和平均情况时间复杂度

算法的时间复杂度不仅与问题规模相关，如果输入数据不同，算法所需的时间开销也会不同。例如，在包含n个元素的数组中找给定元素x，设算法从左向右搜索，如果待搜索的元素x正好是第一个元素，则所需的查找时间最短，这就是算法的最好情况。如果待搜索的元素x是最后一个元素或是不在数组中，则是算法的最坏情况。如果需要多次在数组中查找元素，并且假定以相等的概率查找每个数组元素，则是算法时间代价的平均情况。

对于算法的时间复杂度分析，存在三种情况，对应三种时间复杂度，即最好情况、最坏情况和平均情况时间复杂度。相关示例将在后续章节中给出。

1.4.4　算法的空间复杂度

算法的空间复杂度往往是指对应的程序从运行开始到结束所需的存储量。

程序运行所需的存储空间包括两部分。

（1）固定部分。这部分空间与问题规模无关，主要包括程序代码、常量、简单变量等所占的空间。

（2）可变部分。这部分空间大小与问题规模有关。例如，长度为1 000的两个数组相加，与长度为10的两个数组相加，所需的存储空间是不同的。这部分存储空间除了包括数据元素所占的空间外，还包括算法执行所需的额外空间，如递归栈所用的空间。

算法的空间复杂度的讨论类似于时间复杂度，但空间复杂度一般按最坏情况来分析。