在这里留下心情
0%

分治法：确定无序序列查找中间值算法设计

Posted on Edited on

分治法

许多有用的算法结构上是递归的：为了解决一个给定的问题，算法一次或多次递归地调用其自身以解决紧密相关的若干子问题。这些算法典型的遵循分治法的思想：将原问题分解为几个规模较小但类似于原问题的子问题，递归地求解这些子问题，然后再合并这些子问题的解来建立原问题的解。

分治模式在每层递归时都有三个步骤：

  • 分解原问题为若干子问题，这些子问题是原问题规模较小的实例；
  • 解决这些子问题，递归地求解各子问题。然后若子问题的规模足够小，则直接求解；
  • 合并这些子问题的解成原问题的解。

问题描述

对于一个确定的无序序列 {x1, x2, x3, …, xn}（n >= 1），找出其中位数，即该数大于等于前面一半的元素，且不小于后一半元素：{x1, x2, …, xi} <= xi+1 <= {xi+2, xi+3, …, xn}。

解决方法

一般的思路，可以先对改无序序列进行排序，然后直接取中间的元素即可，这样平均时间复杂度也需要O(NlgN)。
这里使用类似快速排序的方法来求解，快速排序本身也是一种分治法。

快速排序的思想：

  • 分解：数组 A[p..r] 被划分为里两个（可能为空）子数组 A[p..q-1] 和 A[q+1..r]，使得 A[p..q-1] 中的每一个元素都小于等于 A[q]，而 A[q] 也小于等于 A[q+1..r] 中的每个元素。其中，计算下标 q 也是划分过程的一部分；
  • 解决：通过递归调用快速排序，对子数组 A[p..q-1] 和 A[q+1..r] 进行排序；
  • 合并：因为数组都是原址排序的，所以不需要合并操作：数组 A[p..r] 已经有序。

根据以上原理，可以比较容易想到，如何利用分治法查找中间值：

  • 分解：首先计算下标 q ，然后数组已经被划分维两个子数组： A[p..q-1] 和 A[q+1..r]。比较得到的划分下标 q 和 (n + 1)/2；如果 q == (n + 1)/2，则中间值为 A[q]；如果 q < (n + 1)/2，则表示中间值在 A[q+1..r] 这侧，否则在 A[p..q-1] 这侧；
  • 解决：根据上面的比较结果，如果没有查找到，则继续递归调用自身继续求解；
  • 合并：由于只是查找中间值，不需要进行合并操作。

算法复杂度分析

这里只讨论平均时间复杂度，每次都对子规模的数据进行平均分配：

  • 第一次平均分成两段，需要Ｔ(n/2)
  • 第二次在第一次的基础再平均分成两段，需要T(n/4)
  • …
  • 第 k 次在 k - 1 次的基础上评价分成两段，需要 T(n/2^k)

T(n) = T(n/2) + T(n/4) + … T(n/2^k) = n/2 + n/4 + … n/2^k 大约等于 2n

所以平均时间复杂度是O(n)。

算法实现

  • 查找中间值
1
2
3
4
5
6
7
8
9
10
11
FIND_MID(A, p, r, mid)
  if p == r
　　　　return A[p]
  if p < r
    q = PARTITION(A, p, r)
    if q == mid
      return A[q]
    if q < mid:
      FIND_MID(A, q + 1, r, mid - q)
    else
      FIND_MID(A, p, q - 1, mid)
  • 分区
1
2
3
4
5
6
7
8
9
PARTITION(A, p, r)
  x = A[r]
  i = p - 1
  for j = p to r - 1
    if A[j] <= x
      i = i + 1
      exchange A[i] with A[j]
  exchange A[i + 1] with A[r]
  return i + 1

详细实现代码，在这里

总结

合理的使用分治法求解问题，能够起到很好的效果。比如这里的查找中位数的算法，仅仅是利用了快拍这种分治的思想进行求解，在每次递归的过程中都是对子规模的数据求解，在比较好的情况下，效率是远远高于把数据排序之后再查找高出很多的。

附录

  • 分治法简介，摘抄自《算法导论》。