注：
本题解为个人完成，难免有疏漏，请勿抄袭，仅供参考，同时欢迎留言指正。
## 4.1
利用数学归纳法即可，本题的归纳推理除了个人推荐的自顶向下的方式，也可以自底向上。
+ 的情况，只有一个根节点， + 假设的情况，k是非负整数，有命题成立，则对于任意的情况，可以把这个树分解为根节点和左右子树，这里有左右子树的树高不超过k显然成立
，则叶子总数量。 + 故命题成立
4.4
注意体会这两道题的区别，和解答思路的区别
1）只需要给出一个满足条件的算法，最坏情况用5次比较对4个元素排序，我们知道可以花3次比较来确定其中三个数的序关系，即。记排序后的三个数为，则对于最后一个数的序，我们第4次比较把它和中位数进行比较，无论比较结果如何，至少能确定和其中的2个的序关系，然后第5次比较留给最后一个不确定的序关系即可。
具体算法的规范书写从略。
- 本题不光要找到一个算法，对5个元素进行排序，并且要证明在最坏情况下这个方法是最优的。那么理论上就需要穷尽所有的比较方法，然后找到其中最优的方法。个人尝试了一下决策树和穷举的思路，过于复杂，这里推荐另一种思路：先放缩得到算法比较次数的下界，再给出最坏情况下能取到下界比较次数的算法。
我们考虑5个元素所有可能的序关系的集合，一开始没进行任何比较，集合大小是全排列5!=120。
对于一次比较，可以把集合划分为两个子集合，设其大小为。最坏情况下最多只能消除的元素,故对于大小为120的集合，比较次数的下界是。下面再给出一个具体的算法，最坏情况比7次即可，下面只给出思路：
+ 第一次比较，1和2比 + 第二次比较，3和4比 + 第三次比较，和比，得到 + 第四次比较，和比，得到 +
第五、六、七次比较，把5个数中除去最大值和最小值剩下的三个数排序
按这个思路表达成算法形式即可，详略。
4.8
这个题目需要结合线性时间选择算法，后面的章节中是有详细讲解的。那不妨假设已经知道了，可以以的复杂度找到个数的中位数，那么由中位数把原数组一分为二，则可以用分治思想，先解决原问题(个数排成)分解后两个子问题(个数排成)。
因为不适合用定理，我们直接求和计算即可，，项数为
故最后的复杂度是，详细的算法书写从略。
注：本题还有一个基于堆的实现方法，复杂度也是。大概方法就是以每个子数组的首元素进行堆排序，次的调整，总复杂度。
4.9
只给思路，假设螺钉的数组是,螺母的数组是,则在中随便取一个元素，可以把分解为三个部分，其中螺钉螺母是吻合的。然后再用中的把数组分为三个部分，这样以的复杂度就把问题分解了，并且子问题有两个(和)，规模都是原先的一半。
故由主定理可以知道，平均情况复杂度是，本质还是快排的思想。
4.11
注：根据评论区留言，答案已修正，更新时间2022.4.17
### (1) 反证即可，设对于,之间的任意一个元素,如果、都不是逆序，则不是逆序，矛盾。故必然对应一个逆序对，故之间的个元素至少对应了个逆序对，加上本身是逆序对，故逆序对个数，由已知逆序对至多有个，故，命题得证。
(2)
本质就是要求不超过次比较，找到所有的逆序对 +
先把所有相邻的两个元素比较 *
此过程中每找到了逆序对(k,k+1)，都跳过下一次比较(k+1,k+2)，因为这一定不是逆序对，否则(k,k+2)也是逆序对，矛盾。
+ 若共发现对逆序对，无逆序对，比较次 + 若共发现对逆序对，则无其他逆序对，比较次 + 若发现对逆序对，假设位置是，则左边的部分(下标到)已经排好序，右边的部分(下标到)也已经排好序，若存在另一个逆序对，可设为，此时一定在左部分，一定在右部分。且根据第一题，我们知道和之间恰隔了一个元素。故另一个逆序对若存在，则只可能是或两者中的一个。所以再检查这两对即可。比较次
因此最坏情况下，比较次数不超过。
##4.14 两次排序即可： + 先把每个词自身排个序，作为每个词的属性 +
然后词之间按属性排序
最后判断相邻的词属性是不是一样即可，因此所有易位词都相邻了。
