分治算法学习笔记。
分治的基本概念
把一个任务,分成形式和原任务相同,但规模更小的几个部分任务 (通常是两个部分),分别完成,或只需要选一部分完成。然后再处理完成后的这一个或几个部分的结果,实现整个任务的完成。
分治的典型应用
二分查找
二分查找函数中,为了防止 $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$ 大的数
应用快排的思想
-
求排列的逆序数
在归并排序的基础上完成