【习题解答】抽象算法设计与分析

注： 本题解为个人完成，难免有疏漏，请勿抄袭，仅供参考，同时欢迎留言指正。 ##1.1 ###(1) 算法设计 ###(2) 本问针对个人设计的算法，假设所有输入等可能出现，则： + 有可能性, 序最大, 进行第2、5行比较; + 有可能性, 序不为最大, 进行第2、5、7行比较;

最坏情况 需要进行3次比较。 平均情况 需要进行次比较

###(3) 本问求最坏情况(面向所有输入)比较次数的下界(面向所有算法)。即

易得结果为3次，下面给出严格证明，分为两个步骤： + 存在一个可行算法，使得最坏输入情况的比较次数等于3; + 不存在一个可行的算法，最坏输入情况的比较次数都小于3。

前者用举例证明：如第1小问设计的算法，最坏情况的比较次数就是3; 后者用反证法：假设某可行算法进行了不到3次比较，通过改变输入，可以使得3个整数中至少有1对整数之间的序关系是未知的，那么就需要进行3次比较，产生矛盾。因此后者得证。 综合上述，最坏情况比较次数的下界为3次。

##1.2 本题和1.1非常类似，只需要进行略微的修改即可。 ###(1) 算法设计 ###(2) 本问针对个人设计的算法，假设所有输入等可能出现，则： + 有可能性, 序最大, 进行第2、5行比较; + 有可能性, 序不为最大, 进行第2、5、7行比较;

最坏情况 需要进行3次比较。 平均情况 需要进行次比较

###(3) 本问求最坏情况(面向所有输入)比较次数的下界(面向所有算法)。即

前者用举例证明：如第1小问设计的算法，最坏情况的比较次数就是3; 后者用反证法：假设某可行算法进行了不到3次比较，通过改变输入，可以使得3个整数中至少有1对整数之间的序关系是未知的，那么不能确定中位数。具体而言对于a、b、c三个数： (i) 若已知1对序关系(a,b)，那么不能确定中位数； (ii) 若已知2对序关系(a,b)和(a,c)，这两对序关系必然相同,否则(b,c)的序关系就可知,故不能确定中位数。那么就需要进行3次比较，产生矛盾。因此后者得证。 综合上述，最坏情况比较次数的下界为3次。

##1.3 ###(1) 答：例如全集，子集、、、、。按这个算法最后找到的最小覆盖是。但正确的最小覆盖是。

###(2) 最小集合覆盖是一个NP问题，这里就简单给出一种集合覆盖的求法，答案不唯一

正确性证明：如果集合族是的一个覆盖，即，那么算法中的if语句满足，那么将会返回S，显然求得了一个集合覆盖;

如果集合族不是的一个覆盖，那么算法中的if语句不满足，else块将被运行,同时找不到满足条件的，使得(否则是的覆盖，产生矛盾)。因此不存在集合覆盖，算法将报错退出，符合预期。

###(3) 答：不能保证得到最小覆盖，例如全集，子集、、、。按这个算法最后找到的覆盖是。但最小覆盖是。

##1.4 1)的算法描述 2)的算法描述 3)的算法描述

反例：例如,,T=101，上述三个算法都找不到满足要求的硬币集合，但是存在集合{1,100}满足要求。

##1.5 本题很经典，可以考虑如果用状态机来解决，要怎么画 算法设计 正确性证明 (1)当的时候，程序返回第三个return，即a=1和b=1，算法正确工作。

(2)设当的时候，程序正确，即从第三个return中返回了a=k和b=1,那么当的时候，程序还是返回第三个return，返回值是a=k+1,b=1，程序正确。

(3)故对于任意，程序都正确

以上证明了模3等于2的所有正整数的正确性，模3等于1和0的情况同理，从略。

本题证明核心是使用数学归纳法。

##1.6 注意本题并不是指KMP算法的next，而是在下一页附上了算法的内容。 证明： (1)当时，后继是1显然算法正确；

(2)当时,算法返回2n+1,显然也正确；

(3)若时算法正确，则时,算法返回,也就是,故此时算法正确

(4)故对任意非负整数，显然算法都正确。

##1.7 本题证明的核心还是归纳推理，但是和数学归纳法不同，本题的推理是有限回合的，也就是利用循环不变式进行证明 我们先观察一下每次循环的结果(注意! 我们要通过观察找循环不变式！)： + 当3-4行的for循环第1次执行的开始， + 当3-4行的for循环第2次执行的开始， + 当3-4行的for循环第3次执行的开始，那么通过观察归纳，for循环第j次执行(j=1,2,3...,n)的开始时：

，

而j=n-i (i是循环变量，i=n-1,n-2,..,0)，那么用i来替换j以表示p，我们就知道了循环不变式是

也就是说循环开始时，根据循环变量i，循环不变式p都是上述的形式，上述都是心里活动，下面就是用循环不变式证明算法正确性的标准三步走格式。

(1)初始化：，显然正确

(2)保持：当前循环开始时满足循环不变式，

经过循环体运算后，

那么下一轮刚开始的时候，i会自减1，故循环不变式仍然满足。

(3)终止：当i为0，最后一次循环开始时，有循环不变式，故最后一次循环结束后，，显然返回值p就是我们希望的值。

故算法正确。

注：关于循环不变式的内容，可以参考算法导论第二章2.1的内容，本题是算导原题，即习题2.3

##1.8 不妨直接证第二问，也就是说当，证明算法正确。那么考虑对进行强数学归纳法。

(1)当，显然返回正确

(2)假设(是非负整数)时，算法正确

则对于，因为,则子调用INT-MULT正确，则返回,又由数学知识，。故此时返回值为，也是正确的。

(3)因此对任意,是非负整数，算法都正确。

##1.9 题干给的是输入r的概率密度函数，利用积分可以得到：，，，

故平均情况时间复杂度就是

##1.10 该算法判断数组中元素是不是没有重复的，没有重复则返回TRUE，有重复返回FALSE。

当数组没有重复元素，两层循环全部跑完，返回TRUE的情况，就是最坏情况。复杂度是

。

在给定条件下，两个元素等可能的取n个位置中的两个，每种情况也就是的概率，也可以理解成两层循环的中的每个if生效的概率是相等的。因此平均情况时间复杂度为：

首先，本题的输入是数组A[0...n-1]，那么输入规模就是n。现在的目标就是求n无穷大的时候，算法平均时间代价的量级。题干给的k认为是一个常数，不属于问题的输入规模。又任意两个数相等的概率是，故从数学期望来看需要的平均比较次数是k。故平均情况时间复杂度是O(k)。但作为答案，这种说法比较粗糙，下面给出个人认为的相对合理的计算方法。

假设时间复杂度的主项是，则:

取极限后，

故

从而时间复杂度是

注：个人认为如果把k不当作问题的规模，也可以写成O(1)。下面不妨思考一下本题的最坏情况时间复杂度，由抽屉原理，前k+1个数必然有重复的元素，那么最坏情况时间代价就是，也就是。如果考虑k不是规模，那么也可以认为是。