1.3 抽象算法分析
面对一个算法问题，当我们已经为之设计一个正确算法的时候，下一个关键问题就是分析所设计的算法是否高效。为此，首先需要针对抽象算法设计的特点，讨论抽象算法的性能指标。以此为基础，进一步讨论算法的最坏情况和平均情况复杂度分析。
1.3.1 抽象算法的性能指标
算法性能分析的主要任务是度量算法执行所消耗的资源，而这样的资源主要体现在时间和空间这两个方面。这一问题表面上看很简单：要度量一个算法执行的时间，就直接记录其运行的物理时间；度量一个算法执行所耗的空间，就直接度量算法运行需要的存储空间的比特数。
这一做法看似精确，其实存在较大的局限。因为一个算法的实际执行的物理时间和存储空间是与执行平台相关的，也是与实现语言相关的，另外还与运行环境中的诸多其他因素相关。这一度量看似精确，其实它依赖的具体因素太多，反而未能准确表征算法的性能好坏。从计算模型的角度来看，由于我们是在RAM模型上设计抽象的算法，所以算法性能度量指标也应该具有机器无关、实现语言无关的特征，同时它还需要能够较为准确地表征算法的性能。
一个在度量的一般性和精确性之间取得较好权衡的时间复杂度指标是RAM模型上执行简单操作的个数。执行操作的个数在很大程度上决定了算法执行的快慢，一个算法的具体实现的具体运行时间，同其执行操作的个数往往具有线性关系。类似地，对于空间复杂度，我们可以直接用算法需要用到的RAM模型中寄存器的个数来度量。这一组性能指标源自于抽象的RAM模型，所以它也具有机器无关、实现语言无关的抽象性，能够较好地表征一个抽象算法的性能。这样，我们就将抽象算法分析的问题变成了一个计数(counting)问题：统计简单操作的个数和存储单元的个数。
在实际的算法分析中，我们还可以对简单操作的个数这一指标作进一步的精炼。在算法分析时，我们往往并不关心所有的简单操作，而是仅关注一些所谓的关键操作(critical operation)。这主要是因为，算法执行的大量简单操作都是辅助性的，并不是算法运作的核心，并且一个算法执行的辅助性的简单操作，其个数往往和关键操作的个数满足一个线性关系，所以关键操作的个数能够准确表征算法的性能，同时它还大幅简化了算法分析。例如，在排序算法分析中，我们着重关注的是元素的比较(comparison of keys)这一关键操作。一方面，元素的先后顺序完全是由元素之间的两两比较的结果来决定的；另一方面，虽然排序必不可少地需要进行其他简单操作，如存储单元的读写、辅助变量的创建与修改等，但是这些辅助性的简单操作的执行，主要是由元素的比较决定的，它们的个数也不超过元素比较个数的某一个倍数。很多情况下，算法的关键操作是不言自明的，必要的时候我们可以在算法分析之前，明确约定算法的关键操作。常见算法问题中的关键操作如表1.1所示。
表1.1 常见算法问题中的关键操作
算法问题关键操作排序、选择、查找元素的比较图遍历节点信息的简单处理串匹配字符的比较矩阵运算两个矩阵元素之间的简单运算
有了度量算法复杂度的指标，我们就可以进一步分析算法的复杂度，进而比较算法性能的好坏。这主要包括最坏情况复杂度分析和平均情况复杂度分析，下面分别讨论这两个问题。
1.3.2 最坏情况时间复杂度分析
由于算法可以接受不同的输入，所以它的复杂度对于不同输入一般是不一样的。对于输入而言，它的一个核心的属性是其规模，这很大程度上决定了算法复杂度的高低。所以算法分析的本质不是具体的一个复杂度的值，而是输入规模n到算法复杂度的一个函数关系f(n)。
不过进一步分析，上述思路中有一个小的漏洞：即使对于同样的输入规模，算法的执行时间也可能不同。所以同样的问题规模n可能有多个代价值与之相对应，也就是问题规模到算法复杂度的映射并不是一个函数映射。为此，我们引入算法的最坏情况复杂度的概念，其含义是在给定的规模下，最坏的输入所对应的算法复杂度。因为对于给定的问题规模n，其最高代价是确定的，所以我们就建立了问题规模n与最坏情况复杂度W(n)之间的函数关系。最坏情况复杂度不仅仅是数学上的一个函数关系，它同样有比较直观的现实意义。当我们能够接受一个算法的最坏情况复杂度时，我们就可以在任何情况下确保安全地使用该算法。
我们可以严格地定义W(n)如下。当问题输入规模为n时，算法所有可能的合法输入集合记为Dn，一个具体的算法输入实例记为I，f(I)表示对于具体的输入实例I算法的时间复杂度，则算法最坏情况时间复杂度可以定义为：W(n)=maxI∈Dn f(I)这里主要讨论最坏情况时间复杂度，最坏情况空间复杂度的定义是类似的。
我们通过一个具体的例子来展示算法的最坏情况时间复杂度分析。假设需要在数组A［1..n］中查找输入的元素e。为了简化后续分析，假设e必然存在于数组A［1..n］中，且仅出现1次。我们提出一个基于遍历所有输入元素的算法来解决这一问题，其实现如算法2所示。算法2：SEQUENTIAL-SEARCH(A［1..n］,e)
1 for i∶=1 to n do
2 if A［i］=e then
3 return i ;基于对输入元素的假设，我们发现算法2的代价主要取决于元素e出现于数组中的位置。元素e的位置越靠后，算法的代价越大。所以其最坏情况代价对应于e出现于A［n］位置时的代价n。所以算法2的最坏情况时间复杂度W(n)=n。
1.3.3 平均情况时间复杂度分析
仅靠最坏情况时间复杂度尚不能充分表征算法的性能。一种经常出现的情况是，算法在遇到某些输入时代价很高，所以它的最坏情况时间复杂度很高。但是这些“坏输入”出现的可能性很小，所以综合来看这样的算法的性能是良好的。此时应该有一个比最坏情况时间复杂度更“公平”的指标来度量算法的代价。为此，我们引入平均情况时间复杂度的概念。
为了表征不同输入出现的可能性不同的情况，假设算法所有可能的输入服从某个概率分布，这样算法的时间复杂度就成为一个随机变量，而它的期望值A(n)就被定义为算法的平均情况时间复杂度。记每个输入I出现的概率为Pr{I}，则：A(n)=∑I∈DnPr{I}・f(I)同样考察上述元素查找的问题。假设所有可能的输入等概率地出现。由于元素e必然出现于数组A［1..n］中的某一个位置上，算法的代价仅受元素e实际出现的位置影响。所有可能的输入按照元素e出现位置的不同分为n种情况，分别对应于元素e出现在A［1］,A［2］,…,A［n］这n个位置上。分析这每种情况出现的概率及其对应的算法代价，我们得出算法的平均情况时间复杂度为：A(n)=∑ni=11n・i=n+121.4 习题
1.1 （3个数排序） 输入3个各不相同的整数：
1） 请设计一个算法将输入的3个整数排序。
2） 在最坏情况下、平均情况下你的算法分别需要进行多少次比较？(假设所有可能的输入等概率出现。)
3） 在最坏情况下将3个不同整数排序至少需要多少次比较？请证明你的结论。
1.2 （3个数的中位数） 输入3个各不相同的整数：
1） 请设计一个寻找3个数的中位数的算法。
2） 在最坏情况下、平均情况下你的算法分别需要进行多少次比较？(假设所有可能的输入等概率出现。)
3） 在最坏情况下找出3个不同整数的中位数至少需要多少次比较？请证明你的结论。
1.3 （集合覆盖问题） 定义集合的最小覆盖如下：已知全集U={1,…,n}。给定U的子集组成的集合族S={S1,…,Sm}，找出S的最小子集T，满足∪Si∈TSi=U。例如，全集U={1,2,3,4,5}有下面几个子集，S1={1,3,5},S2={2,4},S3={1,4}和S4={2,5}，则最小覆盖为{S1,S2}。
1） 找出下面算法失败的例子：首先选择S中最大的集合Si，并从全集中将Si中的所有元素删除；然后从S中剩余的集合中挑选最大的并从全集中删除对应元素；重复上述过程直到全集中的所有元素都被覆盖。
2） 请设计一个算法计算输入全集的一个集合覆盖，并证明你所设计算法的正确性。
3） 你所设计的算法能否保证总是得出最小覆盖？如果不能，请针对你的算法设计一个反例。
1.4 （换硬币问题） 定义换硬币问题如下：给定n个硬币，它们的面值是正整数S={s1,s2,…,sn}；另外给定一个正整数金额值T。我们需要从S中找出若干个硬币，使得它们的面值和为T，或者返回“不存在这样的硬币集合”。我们给出3种不同的算法设计方案。
1） 依次扫描硬币s1,s2,…,sn，并累加金额。
2） 按面值从小到大的顺序依次扫描硬币，并累加金额。
3） 按面值从大到小的顺序依次扫描硬币，并累加金额。
在上述扫描过程中，如果金额值累积到正好为T，则返回已经扫描到的硬币；否则返回“不存在这样的硬币集合”。请将上述3种方案分别写成算法，并通过举反例的方式证明这3个算法的“不正确性”。
1.5 （多项式计算） HORNER算法是用来计算多项式P(x)=anxn+an－1xn－1+…+a1x+a0的，请证明其正确性。1 Algorithm: HORNER(A［0..n］, x)
2 p ∶= A［n］ ;/数组A［0..n］存放系数a0,a1,…,an/
3 for i∶=n－1 downto 0 do
4 p∶=p・x+A［i］ ;
5 return p ;1.6 （整数相乘） INT-MULT算法用来计算两个非负整数y、z的乘积。1 Algorithm: int INT-MULT(int y, int z)
2 if z=0 then
3 return 0;
4 else
5 return INT-MULTcy,zc + y・(z mod c);1） 令c=2，请证明算法的正确性。
2） 令c为任意的一个不小于2的常数，请证明算法的正确性。
1.7 算法的输入r为1到n之间的正整数，r取不同值的概率如下：Pr{r=i}=1n1≤i≤n4
2nn412nn22 perform 10 operations ;
3 else if n44 perform 20 operations ;
5 else if n26 perform 30 operations ;
7 else
8 perform n operations ;
