分治

分治的基本思想

分治（Divide and Conquer）

• 分而治之，是处理复杂问题的一个最基本、也最常用的策略之一

基本思想

规模为N的原始问题 ==> 若干规模较小的同类子问题 ==> 若干规模更小的同类子问题 ==> 直接求解规模更小的子问题 ==> 将各个子问题的解合并为原问题的解

分治的实例———找假币

12个一模一样的硬币，已知==只有一枚是假币==，并且假币和真币的重量不一样（假设假币比真币轻），问如何用一个天平把假币从这12枚硬币中找出来，只能称3次

1. 最简单的办法： 直接求解的找假币问题： 2枚称1次
2. 稍复杂的：3枚，需要称几次？
3. 分治法 + 排除法
   1. 12枚分成两等份，每份6枚；
   2. 假币那端的6枚再次分为两等分，每份3枚；
   3. 有假币的那一端的3枚硬币中任意取出2个去称重。
4. 分治法
   1. 把12枚硬币分成3等份，每份4枚；
   2. 在有假币的那一端的4枚硬币中，任取两枚到天平两端去称重；
   3. 若假币在余下的那两枚中，则把这两枚硬币放到天平两端去称重。

典型分治的方法

• 最常用的是二分法
  • 每次将原问题分解为两个子问题
    • 一分为二的哲学思想的应用
    • 许多经典的算法，并归排序、拆半查找、二分法就方程的根等
  • 合并是算法的关键
    • 无统一的模式

分治的实例

• 归并排序
  • 将相邻的两个有序数列合并成一个新的有序数列：总是取两个剩余序列中排在前面的最小数放到合并后的序列中，

分治方法给我们的哲学思考——换一个角度，一分为二地观察和思考问题，

• 化繁为简
• 化难为易
• 化大为小
• 化未知为已知