ふわふわ時間

0%

分治算法

分治算法学习笔记。


分治的基本概念

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

分治的典型应用

二分查找

二分查找函数中,为了防止 \(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\) 大的数
    • 应用快排的思想
  • 求排列的逆序数
    • 在归并排序的基础上完成