【算法笔记】分治法--中位数与顺序统计量

问题一:最大值、最小值问题

输入:数组A[i,…,j]

输出:max和min

法一:遍历两次分别找到max和min,共需2n-2次

法二:归并思路,同时找到max和min,共需3/2n-2次

imgimg

拓展--线性时间的选择问题(中位数和顺序统计量)

法一:按照快速排序的思路递归查找主元,最坏情况O(n^2)

法二:线性时间内的选择算法--分治法

过程:

  1. 分组:每组5个数,最后一组可能不足5个
  2. 排序:选择每组的中位数
  3. 选择:中位数中的中位数(MoM)

imgimg

  1. 划分:用MoM中心作为划分,记它的坐标为k
  2. 递归运算:

imgimg

时间复杂度分析:

伪代码

imgimg