分治算法

分治算法学习笔记。

分治的基本概念

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

分治的典型应用

二分查找

二分查找函数中，为了防止 $L + R$ 过大溢出，建议使用 $mid = L + (R - L)/2$.

例题

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

归并排序

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

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

快速排序

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

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

例题

• 输出前 $m$ 大的数

  应用快排的思想

• 求排列的逆序数

  在归并排序的基础上完成