【算法笔记】分治法--中位数与顺序统计量
问题一:最大值、最小值问题
输入:数组A[i,…,j]
输出:max和min
法一:遍历两次分别找到max和min,共需2n-2次
法二:归并思路,同时找到max和min,共需3/2n-2次
拓展--线性时间的选择问题(中位数和顺序统计量)
法一:按照快速排序的思路递归查找主元,最坏情况O(n^2)
法二:线性时间内的选择算法--分治法
过程:
- 分组:每组5个数,最后一组可能不足5个
- 排序:选择每组的中位数
- 选择:中位数中的中位数(MoM)
- 划分:用MoM中心作为划分,记它的坐标为k
- 递归运算:
时间复杂度分析:
伪代码