文档介绍：第4章 分治法
概 述
递 归
排序问题中的分治法
组合问题中的分治法
几何问题中的分治法
1
概 述
分治法的设计思想
分治法的求解过程
2
将一个难以直接解决的大问题，划分成一些规模较小的子问题，以便各个击破，分而治之。更一般地说，将要求解的原问题划分成k个较小规模的子问题，对这k个子问题分别求解。如果子问题的规模仍然不够小，则再将每个子问题划分为k个规模更小的子问题，如此分解下去，直到问题规模足够小，很容易求出其解为止，再将子问题的解合并为一个更大规模的问题的解，自底向上逐步求出原问题的解。
分治法的设计思想
3
2. 独立子问题：各子问题之间相互独立，这涉及到分治法的效率，如果各子问题不是独立的，则分治法需要重复地解公共的子问题。
1. 平衡子问题：最好使子问题的规模大致相同。也就是将一个问题划分成大小相等的k个子问题（通常k＝2），这种使子问题规模大致相等的做法是出自一种平衡（Balancing）子问题的思想，它几乎总是比子问题规模不等的做法要好。
启发式规则：
4
子问题1
的规模是n/2
子问题1的解
子问题2的解
子问题2
的规模是n/2
原问题的解
原问题
的规模是n
分治法的典型情况
5
分治法的求解过程
一般来说，分治法的求解过程由以下三个阶段组成：
（1）划分：既然是分治，当然需要把规模为n的原问题划分为k个规模较小的子问题，并尽量使这k个子问题的规模大致相同。
（2）求解子问题：各子问题的解法与原问题的解法通常是相同的，可以用递归的方法求解各个子问题，有时递归处理也可以用循环来实现。
（3）合并：把各个子问题的解合并起来，合并的代价因情况不同有很大差异，分治算法的有效性很大程度上依赖于合并的实现。
6
例：计算an，应用分治技术得到如下计算方法：
34
32
32
81
31
31
9
31
31
9
3
3
3
3
分解问题
求解每个子问题
合并子问题的解
不是所有的分治法都比简单的蛮力法更有效。
分析时
间性能
ë
û
é
ù
î
í
ì
>
´
=
=
1
1
2
2
n
a
a
n
a
a
n
n
n
如果
如果
7
通用分治递推式
问题规模为n的实例被划分为 b个规模为n/b的实例,其中a个实例需要求解,假设n是b的幂
T(n)=aT(n/b)+f(n)
8
主定理
如果在递推式中f(n)∈(nd），其中d≥0
当a<bd时
当a=bd时
当a>bd时
9
递 归
递归的定义
递归函数的运行轨迹
递归函数的内部执行过程
10