分治策略

分治的设计思想

改进分治算法的途经：

求第 k 大的元素最好： $K l o g 2^{K} = K^{2}$

高度之和小于等于 n - 1

证明：

讨论分组时为什么5个元素一组，3个一组或7个一组行不行？

分析：递归调用

1.求m*的工作量与 $∣ M ∣ = n / t$ 相关，t 为每组元素数，t 大， $∣ M ∣$ 小

2.归约后子问题大小与分组元素数 t 有关, t 大，子问题规模大

关键：

$∣ M ∣$ 与归约后子问题规模之和小于 n，递归树每行的工作量构成公比小于 1 的等比级数，算法复杂度才是 $O (n)$

选第k小算法的时间分析

3分组不行，5分组可以，7分组也行