分治算法

分治的基本概念

把一个任务,分成形式和原任务相同,但规模更小的几个部分任务(通常是两个部分),分别完成,或只需要选一部分完成。然后再处理完成后的这一个或几个部分的结果,实现整个任务的完成。

分治的典型应用

二分查找

二分查找函数中,为了防止 $L + R$ 过大益处,$mid = L + (R - L)/2$.

例题

  • 输入n ( n<= 100,000)个整数,找出其中的两个数,它们之和等于整数m(假定肯定有解)。题中所有整数都能用 int 表示。
  • POJ 2456: Aggressive cows

归并排序

数组排序任务可以如下完成:

  • 把前一半排序
  • 把后一半排序
  • 将两半归并到一个新的有序数组,然后再拷贝回原数组,排序完成。

快速排序

数组排序任务可以如下完成:

  • 设 $k = a[0]$,将 $k$ 挪到适当位置,使得比 $k$ 小的元素都在 $k$ 左边,比 $k$ 大的元素都在 $k$ 右边,和 $k$ 相等的,不关心在 $k$ 左右出现均可 ($O(n)$时间完成)
  • 把 $k$ 左边的部分快速排序
  • 把 $k$ 右边的部分快速排序

例题

  • 输出前 $m$ 大的数
    • 应用快排的思想
  • 求排列的逆序数
    • 在归并排序的基础上完成