【习题解答】 对手论证

注： 本题解为个人完成，难免有疏漏，请勿抄袭，仅供参考，同时欢迎留言指正。 ## 19.1 决策树每个节点进行比较，最坏情况就是决策树从根到叶的最长路径L，显然，其中叶子的数目至少是，对应着第k大元素的n个不同的结果。因此，即最坏情况时间复杂度的下界是

19.3

• 最多有一个逆序对意味着逆序只可能出现在相邻两个元素之间，那么所有非相邻的元素都不是逆序对
• 只要找到这个相邻逆序对，调换位置即可完成排序，说明次操作确实可以完成排序
• 为了便于理解，可以用图的方式刻画这个过程，即n个元素是n个点，比较一次的结果可以确定两个点之间边的方向，可以根据两个点之间的可达性判断逆序情况
• 假设某算法A自认为可以用不到次比较，就判断出逆序对是个还是个
• 对手先采取这样的策略：输入数据设置为无逆序，这样算法A的每次比较都返回不是逆序对，最终一定返回无逆序对
• 进行了不到次比较，说明至少有一对相邻的节点之间是没有边的
• 此时在图中相互不可达，思考为什么
• 如果此时添加一条从到的边，图不会出现圈，思考为什么
• 对手可以按图当前表示的顺序关系重新构造输入数据，算法A有可能还是输出无逆序对，之所以说有可能是考虑到随机算法。
• 说明该算法有可能出错，从而得出矛盾，故比较次数的下界是

19.5

(1)

算法思路 + 利用锦标赛的方式，个元素为一组，每组内部比出的最大值为胜者，每轮的所有胜者进入下一轮。 + 注意，除非是决赛，否则如果有一组人凑不满个，就全部晋级到下一轮，这个是为了保证算法的最优性。

正确性 因为每轮必然会淘汰元素，而被淘汰的元素都不是对应组里5个元素的最大值，当然不可能是所有中的最大值，那么所有轮比完后剩下的最后一个元素，必然是最大值，因为其他元素都被淘汰了。

最优性 算法每次都会排除个元素，一共不重复的排除了个元素，故本算法进行了次，假设有一个算法找到了最大值，且次数小于次，那么必然存在至少2个元素没有被排除，对手可以设置输入，使得该算法输出的最大值不是正确结果，因此该算法不正确，由此证明了不存在更优的算法。

(2)

算法思路 + 锦标赛的轮数是 + 最坏情况是冠军没有轮空过 + 每轮sort-five都是五个元素排序，都有第二名 + 所有可能的第二大元素，在最坏情况有，对这些可能的第二名调用第一问的求最大算法即可 + 本算法选出次大元素的最坏情况时间复杂度是

正确性 + 选最大的元素时，没有和最大值比过就被淘汰的一定不是第二大 + 在所有可能的第二大中选出最大的那个，显然就是第二大的元素

最优性 + 证明最优性，就是证明不存在一个算法最坏情况比我们的代价小 + 我们可以构造一个输入的生成方式(对手策略)，使得对于任何算法，在该输入下代价都大于等于我们算法的代价。即找到对手策略，使得对任何算法，在最大者选出后，和最大者比赛输的第二名元素的总数不小于 + 假设初始每个人都有1个金币，小组胜出的获得小组所有其他人的金币，而对手的策略就是，改变输入数据，使得小组中金币最多的那个人胜出 + 注意，对于任意的一个算法，此时已经没有轮数的概念了，因为轮数是我们锦标赛算法中的，但是还是有小组赛的概念，即以5个人为单位进行比赛选出最大者 + 刚开始冠军有1个金币，比赛结束后，冠军拥有的金币数量是 + 因为每组比赛是金币最多的人胜出，因此该组比完后，胜者金币数量最多变为原来的5倍 + 因此冠军至少要比次小组赛，因此和最大者比赛输的元素的总数不小于 + 因此我们的算法是最优的

19.6

(1)

• 我们只考虑是大于的整数，等于或的情况意义不大
• 每次任意取数组中两个从没取过的数,进行比较
• 如果返回结果是"相同"，则继续循环取
• 如果返回结果是"不相同"，说明,中有且只有一个是特殊元素，那么把和数组任意非元素比一下即可，如"不相同"，则特殊元素是，否则是
• 如果数组只剩1个元素可取，则该元素是特殊元素
• 如果数组剩2个元素,可取，说明,中有且只有一个是特殊元素，那么把和数组任意非元素比一下即可，如"不相同"，则特殊元素是，否则是
• 说明算法为什么不超过

(2)

假设，则比较次数的期望是

(3)

• 为了证明方便，可以让对手设置，即为偶数
• 假设某算法A自认为需要最多需要次就能找到特殊元素
• 对手可以采取这样的策略：控制输入数据，使得为偶数，且算法A的每次比较都返回"相同"
• 该算法最多比较次，故比较次数用完时，必然存在至少2个元素从未参与比较
• 这样算法A无法判断特殊元素是哪一个，无论判断为哪个，对手都可以调整输入数据使得算法出错
• 故特殊元素问题最坏情况复杂度下界是

注：其实证偶数情况会让算法A出错已经足够了，为了思考的完整性，下面提一下奇数情况怎么整: + 对手控制输入为奇数时，调整输入数据，使得算法在第次比较以前(不包括)都返回"相同" + 第次比较(如果算法会进行到第的话)，如果发生在两个从未参与比较的元素之间，则比较返回"不相同"；如果有元素已经参与了比较，则返回"相同" + 如果算法比较次数小于其宣称的上界，则每次比较都是返回"相同"，而从未参与比较的元素至少有3个，故找不到逆序元素，矛盾 + 如果算法比较次数恰为其宣称的上界，那么前次返回"相同"，如果第次比较返回"相同"，则至少有2个元素还没参与比较，则无法确定特殊元素是哪个；如果第次比较返回"不相同"，那么由第发生在之前从未参与比较的两个元素之间，由对称性，同样无法确定特殊元素是哪一个