【习题解答】 分治算法设计要素

注： 本题解为个人完成，难免有疏漏，请勿抄袭，仅供参考，同时欢迎留言指正。 ## 7.1 用朴素的两层遍历当然可以，也可以基于归并排序或堆排序进行改进。

7.4

(1)

一般不作说明的要求分析复杂度，考虑最坏情况即可：

(2)

分治的思想，原数组分为左右两个部分，相当于可以先解决两个子问题，然后合并两个排序好的部分即可。

复杂度即

即复杂度为

7.5

(1)

• 计算左右子树的高度
• 树高就是

复杂度

(2)

首先按照上一问的思想，我们可以用O(n)的复杂度，给树的每个节点标注高度。然后直径用分治来解决就很容易：

• 首先计算左子树、右子树两个子问题的直径
• 然后原树直径

空间复杂度和时间复杂度都是，但其实本质上，以每个节点为根的树的高度和直径的计算可以放在一起进行，这样额外空间开销就只需要。即：

• 首先计算左子树、右子树两个子问题的直径和树高
• 然后原树直径，原树高，同时返回原树的高和直径即可。

注：有的同学利用两次dfs来找直径，也是可以的。即从根出发dfs，找到最远的节点，该节点一定是直径的端点；然后以该端点再做一次dfs，找到最远的另一个端点，就可以找到直径。