第 2章 递归与分治策略
将要求解的较大规模的问题分割成 k个更小规模的子问题。
算法总体思想
n
T(n/2) T(n/2) T(n/2) T(n/2)
T(n) =
对这 k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为 k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。
算法总体思想
对这 k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为 k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。
nT(n) =
n/2
T(n/4)T(n/4)T(n/4)T(n/4)
n/2
T(n/4)T(n/4)T(n/4)T(n/4)
n/2
T(n/4)T(n/4)T(n/4)T(n/4)
n/2
T(n/4)T(n/4)T(n/4)T(n/4)
将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。
算法总体思想
将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。
nT(n) =
n/2
T(n/4)T(n/4)T(n/4)T(n/4)
n/2
T(n/4)T(n/4)T(n/4)T(n/4)
n/2
T(n/4)T(n/4)T(n/4)T(n/4)
n/2
T(n/4)T(n/4)T(n/4)T(n/4)
算法总体思想
将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。
nT(n) =
n/2
T(n/4)T(n/4)T(n/4)T(n/4)
n/2
T(n/4)T(n/4)T(n/4)T(n/4)
n/2
T(n/4)T(n/4)T(n/4)T(n/4)
n/2
T(n/4)T(n/4)T(n/4)T(n/4)
分治法的设计思想是，将一个难以直接解决的大问题，
分割成一些规模较小的相同问题，以便各个击破，
分而治之。
凡治众如治寡，分数是也。
----孙子兵法
2.1 递归的概念
直接或间接地调用自身的算法称为 递归算法 。
用函数自身给出定义的函数称为 递归函数 。
由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。
分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。
下面来看几个实例。
2.1 递归的概念例 1 阶乘函数阶乘函数可递归地定义为：
0
0
)!1(
1
!
n
n
nn
n
边界条件递归方程边界条件与递归方程是递归函数的二个要素，递归函数只有具备了这两个要素，才能在有限次计算后得出结果。
2.1 递归的概念例 2 Fibonacci数列无穷数列 1,1,2,3,5,8,13,21,34,55,…,被称为 Fibonacci数列。它可以递归地定义为：
边界条件递归方程 1
1
0
)2()1(
1
1
)(
n
n
n
nFnF
nF
第 n个 Fibonacci数可递归地计算如下：
public static int fibonacci(int n)
{
if (n <= 1) return 1;
return fibonacci(n-1)+fibonacci(n-2);
}
1,
2
0
)1),,1((),(
2)0,(
1),0(
2)0,1(
mn
n
m
mmnAAmnA
nnA
mA
A
2.1 递归的概念例 3 Ackerman函数当一个函数及它的一个变量是由函数自身定义时，称这个函数是 双递归函数 。
Ackerman函数 A(n,m)定义如下：
1,
2
0
)1),,1((),(
2)0,(
1),0(
2)0,1(
mn
n
m
mmnAAmnA
nnA
mA
A
2.1 递归的概念例 3 Ackerman函数前 2例中的函数都可以找到相应的非递归方式定义：
nnn )1(321!?
11
2
51
2
51
5
1
)(
nn
nF
但本例中的 Ackerman函数却无法找到非递归的定义。
2.1 递归的概念例 3 Ackerman函数
A(n,m)的自变量 m的每一个值都定义了一个单变量函数：
M=0时,A(n,0)=n+2
M=1时,A(n,1)=A(A(n-1,1),0)=A(n-1,1)+2，和 A(1,1)=2故
A(n,1)=2*n
M=2时,A(n,2)=A(A(n-1,2),1)=2A(n-1,2)，和
A(1,2)=A(A(0,2),1)=A(1,1)=2，故 A(n,2)= 2^n 。
M=3时，类似的可以推出
M=4时,A(n,4)的增长速度非常快，以至于没有适当的数学式子来表示这一函数。
n
2
22
2
2.1 递归的概念例 3 Ackerman函数
定义单变量的 Ackerman函数 A(n)为,A(n)=A(n，
n)。
定义其拟逆函数 α(n) 为,α(n)=min{k ｜
A(k)≥n} 。即 α(n) 是使 n≤A(k) 成立的最小的
k值。
α(n) 在复杂度分析中常遇到。对于通常所见到的正整数 n，有 α(n)≤4 。但在理论上 α(n)
没有上界，随着 n的增加，它以难以想象的慢速度趋向正无穷大。
2.1 递归的概念例 4 排列问题设计一个递归算法生成 n个元素 {r1,r2,…,rn}的全排列。
设 R={r1,r2,…,rn}是要进行排列的 n个元素,Ri=R-{ri}。
集合 X中元素的全排列记为 perm(X)。
(ri)perm(X)表示在全排列 perm(X)的每一个排列前加上前缀得到的排列。 R的全排列可归纳定义如下：
当 n=1时,perm(R)=(r)，其中 r是集合 R中唯一的元素；
当 n>1时,perm(R)由 (r1)perm(R1),(r2)perm(R2),…,
(rn)perm(Rn)构成。
2.1 递归的概念例 5 整数划分问题将正整数 n表示成一系列正整数之和,n=n1+n2+… +nk，
其中 n1≥n 2≥ … ≥n k≥1,k≥1 。
正整数 n的这种表示称为正整数 n的划分。求正整数 n的不同划分个数。
例如正整数 6有如下 11种不同的划分：
6；
5+1；
4+2,4+1+1；
3+3,3+2+1,3+1+1+1；
2+2+2,2+2+1+1,2+1+1+1+1；
1+1+1+1+1+1。
(2) q(n,m)=q(n,n),m?n;
最大加数 n1实际上不能大于 n。因此,q(1,m)=1。
(1) q(n,1)=1,n?1;
当最大加数 n1不大于 1时，任何正整数 n只有一种划分形式，
即nn 111
(4) q(n,m)=q(n,m-1)+q(n-m,m),n>m>1;
正整数 n的最大加数 n1不大于 m的划分由 n1=m的划分和
n1≤n -1 的划分组成。
(3) q(n,n)=1+q(n,n-1);
正整数 n的划分由 n1=n的划分和 n1≤n -1的划分组成。
2.1 递归的概念例 5 整数划分问题前面的几个例子中，问题本身都具有比较明显的递归关系，因而容易用递归函数直接求解。
在本例中，如果设 p(n)为正整数 n的划分数，则难以找到递归关系，因此考虑增加一个自变量：将最大加数 n1不大于 m的划分个数记作 q(n,m)。可以建立 q(n,m)的如下递归关系。
1
1,1
),()1,(
)1,(1
),(
1
),(
mn
mn
mn
mn
mmnqmnq
nnq
nnq
mnq
2.1 递归的概念例 5 整数划分问题前面的几个例子中，问题本身都具有比较明显的递归关系，因而容易用递归函数直接求解。
在本例中，如果设 p(n)为正整数 n的划分数，则难以找到递归关系，因此考虑增加一个自变量：将最大加数 n1不大于 m的划分个数记作 q(n,m)。可以建立 q(n,m)的如下递归关系。
正整数 n的划分数 p(n)=q(n,n)。
2.1 递归的概念例 6 Hanoi塔问题设 a,b,c是 3个塔座。开始时，在塔座 a上有一叠共 n个圆盘，这些圆盘自下而上，由大到小地叠在一起。各圆盘从小到大编号为 1,2,…,n,现要求将塔座 a上的这一叠圆盘移到塔座 b上，并仍按同样顺序叠臵。在移动圆盘时应遵守以下移动规则：
规则 1：每次只能移动 1个圆盘；
规则 2：任何时刻都不允许将较大的圆盘压在较小的圆盘之上；
规则 3：在满足移动规则 1和 2的前提下，可将圆盘移至
a,b,c中任一塔座上。
在问题规模较大时，较难找到一般的方法，因此我们尝试用递归技术来解决这个问题。
当 n=1时，问题比较简单。此时，只要将编号为 1的圆盘从塔座 a直接移至塔座 b上即可。
当 n＞ 1时，需要利用塔座 c作为辅助塔座。此时若能设法将 n-1个较小的圆盘依照移动规则从塔座 a移至塔座 c，然后，将剩下的最大圆盘从塔座 a移至塔座 b，最后，再设法将 n-1个较小的圆盘依照移动规则从塔座 c移至塔座 b。
由此可见,n个圆盘的移动问题可分为 2次 n-1个圆盘的移动问题，
这又可以递归地用上述方法来做。由此可以设计出解 Hanoi塔问题的递归算法如下。
2.1 递归的概念例 6 Hanoi塔问题
public static void hanoi(int n,int a,int b,int c)
{
if (n > 0)
{
hanoi(n-1,a,c,b);
move(a,b);
hanoi(n-1,c,b,a);
}
}
思考题：如果塔的个数变为 a,b,c,d
四个，现要将 n个圆盘从 a全部移动到 d，移动规则不变，求移动步数最小的方案。
递归小结优点,结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、
调试程序带来很大方便。
缺点,递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。
递归小结解决方法,在递归算法中消除递归调用，使其转化为非递归算法。
1.采用一个用户定义的栈来模拟系统的递归调用工作栈。该方法通用性强，但本质上还是递归，
只不过人工做了本来由编译器做的事情，优化效果不明显。
2.用递推来实现递归函数。
3.通过 Cooper变换,反演变换能 将一些递归转化为尾递归，从而迭代求出结果。
后两种方法在时空复杂度上均有较大改善，
但其适用范围有限。
分治法的适用条件分治法所能解决的问题一般具有以下几个特征：
该问题的规模缩小到一定的程度就可以容易地解决；
该问题可以分解为若干个规模较小的相同问题，即该问题具有 最优子结构性质
利用该问题分解出的子问题的解可以合并为该问题的解；
该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。
因为问题的计算复杂性一般是随着问题规模的增加而增加，因此大部分问题满足这个特征。
这条特征是应用分治法的前提，它也是大多数问题可以满足的，此特征反映了递归思想的应用能否利用分治法完全取决于问题是否具有这条特征，
如果具备了前两条特征，而不具备第三条特征，则可以考虑 贪心算法 或 动态规划 。
这条特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然也可用分治法，但一般用 动态规划 较好。
分治法的基本步骤
divide-and-conquer(P)
{
if ( | P | <= n0) adhoc(P); //解决小规模的问题
divide P into smaller subinstances P1,P2,...,Pk； //分解问题
for (i=1,i<=k,i++)
yi=divide-and-conquer(Pi); //递归的解各子问题
return merge(y1,...,yk); //将各子问题的解合并为原问题的解
}
人们从大量实践中发现，在用分治法设计算法时，最好使子问题的规模大致相同。即将一个问题分成大小相等的 k个子问题的处理方法是行之有效的。这种使子问题规模大致相等的做法是出自一种 平衡 (balancing)子问题 的思想，它几乎总是比子问题规模不等的做法要好。
分治法的复杂性分析一个分治法将规模为 n的问题分成 k个规模为 n／ m的子问题去解。
设分解阀值 n0=1，且 adhoc解规模为 1的问题耗费 1个单位时间。
再设将原问题分解为 k个子问题以及用 merge将 k个子问题的解合并为原问题的解需用 f(n)个单位时间。用 T(n)表示该分治法解规模为 |P|=n的问题所需的计算时间，则有：
1
1
)()/(
)1(
)(
n
n
nfmnkT
O
nT
通过迭代法求得方程的解,
1l o g
0
l o g )/()(
nm
j
jjkm mnfknnT
注意,递归方程及其解只给出 n等于 m的方幂时 T(n)的值，但是如果认为 T(n)足够平滑，那么由 n等于 m的方幂时 T(n)的值可以估计 T(n)的增长速度。通常假定 T(n)是单调上升的，从而当 mi≤n<mi+1时,T(mi)≤T(n)<T(mi+1)。
二分搜索技术分析,如果 n=1即只有一个元素，则只要比较这个元素和 x就可以确定 x是否在表中。因此这个问题满足分治法的第一个适用条件分析,比较 x和 a的中间元素 a[mid]，若 x=a[mid]，则 x在 L中的位臵就是 mid；如果 x<a[mid]，由于 a是递增排序的，因此假如 x在 a中的话,x必然排在 a[mid]的前面，所以我们只要在
a[mid]的前面查找 x即可；如果 x>a[i]，同理我们只要在 a[mid]
的后面查找 x即可。无论是在前面还是后面查找 x，其方法都和在 a中查找 x一样，只不过是查找的规模缩小了。这就说明了此问题满足分治法的第二个和第三个适用条件。
分析,很显然此问题分解出的子问题相互独立，即在 a[i]的前面或后面查找 x是独立的子问题，因此满足分治法的第四个适用条件。
给定已按升序排好序的 n个元素 a[0:n-1]，现要在这 n个元素中找出一特定元素 x。
分析,? 该问题的规模缩小到一定的程度就可以容易地解决；
该问题可以分解为若干个规模较小的相同问题 ;
分解出的子问题的解可以合并为原问题的解；
分解出的各个子问题是相互独立的。
二分搜索技术给定已按升序排好序的 n个元素 a[0:n-1]，现要在这 n个元素中找出一特定元素 x。
据此容易设计出 二分搜索算法,
public static int binarySearch(int [] a,int x,int n)
{
// 在 a[0] <= a[1] <=,.,<= a[n-1] 中搜索 x
// 找到 x时返回其在数组中的位臵，否则返回 -1
int left = 0; int right = n - 1;
while (left <= right) {
int middle = (left + right)/2;
if (x == a[middle]) return middle;
if (x > a[middle]) left = middle + 1;
else right = middle - 1;
}
return -1; // 未找到 x
}
算法复杂度分析：
每执行一次算法的
while循环,待搜索数组的大小减少一半。因此，在最坏情况下，
while循环被执行了
O(logn) 次。循环体内运算需要 O(1) 时间，
因此整个算法在最坏情况下的计算时间复杂性为 O(logn) 。
思考题,给定 a，用二分法设计出求 an的算法。
大整数的乘法请设计一个有效的算法，可以进行两个 n位大整数的乘法运算
小学的方法,O(n2)?效率太低
分治法,
a b
c d
复杂度分析
T(n)=O(n2)?没有改进?
1
1
)()2/(4
)1()(
n
n
nOnT
OnT
X =
Y =
X = a 2n/2 + b Y = c 2n/2 + d
XY = ac 2n + (ad+bc) 2n/2 + bd
大整数的乘法请设计一个有效的算法，可以进行两个 n位大整数的乘法运算
小学的方法,O(n2)?效率太低
分治法,
XY = ac 2n + (ad+bc) 2n/2 + bd
为了降低时间复杂度，必须减少乘法的次数。
1,XY = ac 2n + ((a-c)(b-d)+ac+bd) 2n/2 + bd
2,XY = ac 2n + ((a+c)(b+d)-ac-bd) 2n/2 + bd
复杂度分析
T(n)=O(nlog3) =O(n1.59)?较大的改进?
1
1
)()2/(3
)1()(
n
n
nOnT
OnT
细节问题,两个 XY的复杂度都是 O(nlog3)，但考虑到 a+c,b+d可能得到 m+1位的结果，使问题的规模变大，故不选择第 2种方案。
大整数的乘法请设计一个有效的算法，可以进行两个 n位大整数的乘法运算
小学的方法,O(n2)?效率太低
分治法,O(n1.59)?较大的改进
更快的方法
如果将大整数分成更多段，用更复杂的方式把它们组合起来，
将有可能得到更优的算法。
最终的，这个思想导致了 快速傅利叶变换 (Fast Fourier
Transform)的产生。该方法也可以看作是一个复杂的分治算法，对于大整数乘法，它能在 O(nlogn)时间内解决。
是否能找到线性时间的算法？？？目前为止还没有结果。
Strassen矩阵乘法
A和 B的乘积矩阵 C中的元素 C[i,j]定义为,?
n
k
jkBkiAjiC
1
]][[]][[]][[
若依此定义来计算 A和 B的乘积矩阵 C，则每计算 C的一个元素 C[i][j]，需要做 n次乘法和 n-1次加法。因此，算出矩阵 C的 个元素所需的计算时间为 O(n3)
传统方法,O(n3)
Strassen矩阵乘法使用与上例类似的技术，将矩阵 A,B和 C中每一矩阵都分块成 4
个大小相等的子矩阵。由此可将方程 C=AB重写为：
传统方法,O(n3)
分治法,
2221
1211
2221
1211
2221
1211
BB
BB
AA
AA
CC
CC
由此可得：
2112111111 BABAC
2212121112 BABAC
2122112121 BABAC
2222122122 BABAC
复杂度分析
T(n)=O(n3)?没有改进?
2
2
)()2/(7
)1()(
2?
n
n
nOnT
OnT
Strassen矩阵乘法
传统方法,O(n3)
分治法,
为了降低时间复杂度，必须减少乘法的次数。
2221
1211
2221
1211
2221
1211
BB
BB
AA
AA
CC
CC
)( 2212111 BBAM
2212112 )( BAAM
1122213 )( BAAM
)( 1121224 BBAM
))(( 221122115 BBAAM
))(( 222122126 BBAAM
))(( 121121117 BBAAM
624511 MMMMC
2112 MMC
4321 MMC
731522 MMMMC
复杂度分析
T(n)=O(nlog7) =O(n2.81)?较大的改进?
2
2
)()2/(8
)1()(
2?
n
n
nOnT
OnT
Strassen矩阵乘法
传统方法,O(n3)
分治法,O(n2.81)
更快的方法
Hopcroft和 Kerr已经证明 (1971)，计算 2个２ × ２矩阵的乘积,7次乘法是必要的。因此，要想进一步改进矩阵乘法的时间复杂性，就不能再基于计算 2× 2矩阵的 7次乘法这样的方法了。或许应当研究３ × ３或５ × ５矩阵的更好算法。
在 Strassen之后又有许多算法改进了矩阵乘法的计算时间复杂性。目前最好的计算时间上界是 O(n2.376)
是否能找到 O(n2)的算法？？？目前为止还没有结果。
棋盘覆盖在一个 2k× 2k 个方格组成的棋盘中，恰有一个方格与其他方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的 4种不同形态的 L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何 2个 L型骨牌不得重叠覆盖。
棋盘覆盖当 k>0时，将 2k× 2k棋盘分割为 4个 2k-1× 2k-1 子棋盘 (a)所示。
特殊方格必位于 4个较小子棋盘之一中，其余 3个子棋盘中无特殊方格。为了将这 3个无特殊方格的子棋盘转化为特殊棋盘，可以用一个 L型骨牌覆盖这 3个较小棋盘的会合处，如 (b)所示，
从而将原问题转化为 4个较小规模的棋盘覆盖问题。递归地使用这种分割，直至棋盘简化为棋盘 1× 1。
棋盘覆盖
public void chessBoard(int tr,int tc,int dr,int dc,int size)
{
if (size == 1) return;
int t = tile++,// L型骨牌号
s = size/2; // 分割棋盘
// 覆盖左上角子棋盘
if (dr < tr + s && dc < tc + s)
// 特殊方格在此棋盘中
chessBoard(tr,tc,dr,dc,s);
else {// 此棋盘中无特殊方格
// 用 t 号 L型骨牌覆盖右下角
board[tr + s - 1][tc + s - 1] = t;
// 覆盖其余方格
chessBoard(tr,tc,tr+s-1,tc+s-1,s);}
// 覆盖右上角子棋盘
if (dr < tr + s && dc >= tc + s)
// 特殊方格在此棋盘中
chessBoard(tr,tc+s,dr,dc,s);
else {// 此棋盘中无特殊方格
// 用 t 号 L型骨牌覆盖左下角
board[tr + s - 1][tc + s] = t;
// 覆盖其余方格
chessBoard(tr,tc+s,tr+s-1,tc+s,s);}
// 覆盖左下角子棋盘
if (dr >= tr + s && dc < tc + s)
// 特殊方格在此棋盘中
chessBoard(tr+s,tc,dr,dc,s);
else {// 用 t 号 L型骨牌覆盖右上角
board[tr + s][tc + s - 1] = t;
// 覆盖其余方格
chessBoard(tr+s,tc,tr+s,tc+s-1,s);}
// 覆盖右下角子棋盘
if (dr >= tr + s && dc >= tc + s)
// 特殊方格在此棋盘中
chessBoard(tr+s,tc+s,dr,dc,s);
else {// 用 t 号 L型骨牌覆盖左上角
board[tr + s][tc + s] = t;
// 覆盖其余方格
chessBoard(tr+s,tc+s,tr+s,tc+s,s);}
}
复杂度分析
T(n)=O(4k) 渐进意义下的最优算法
0
0
)1()1(4
)1()(
k
k
OkT
OkT
合并排序基本思想,将待排序元素分成大小大致相同的 2个子集合，分别对 2个子集合进行排序，最终将排好序的子集合合并成为所要求的排好序的集合。
public static void mergeSort(Comparable a[],int left,int right)
{
if (left<right) {//至少有 2个元素
int i=(left+right)/2; //取中点
mergeSort(a,left,i);
mergeSort(a,i+1,right);
merge(a,b,left,i,right); //合并到数组 b
copy(a,b,left,right); //复制回数组 a
}
}
复杂度分析
T(n)=O(nlogn) 渐进意义下的最优算法
1
1
)()2/(2
)1()(
n
n
nOnT
OnT
合并排序算法 mergeSort的递归过程可以消去。
初始序列 [49] [38] [65] [97] [76] [13] [27]
[38 49] [65 97] [13 76] [27]第一步第二步 [38 49 65 97] [13 27 76]
第三步 [13 27 38 49 65 76 97]
合并排序
最坏时间复杂度,O(nlogn)
平均时间复杂度,O(nlogn)
辅助空间,O(n)
稳定性：稳定思考题,给定 有序表 A[1:n]，修改合并排序算法，求出该有序表的逆序对数。
快速排序在快速排序中，记录的比较和交换是从两端向中间进行的，关键字较大的记录一次就能交换到后面单元，关键字较小的记录一次就能交换到前面单元，
记录每次移动的距离较大，因而总的比较和移动次数较少。
private static void qSort(int p,int r)
{
if (p<r) {
int q=partition(p,r); //以 a[p]为基准元素将 a[p:r]划分成
3段 a[p:q-1],a[q]和 a[q+1:r]，使得 a[p:q-1]中任何元素小于等于 a[q],a[q+1:r]中任何元素大于等于 a[q]。下标 q在划分过程中确定。
qSort (p,q-1); //对左半段排序
qSort (q+1,r); //对右半段排序
}
}
快速排序是对气泡排序的一种改进方法它是由 C.A.R,Hoare于 1962
年提出的快速排序
private static int partition (int p,int r)
{
int i = p,
j = r + 1;
Comparable x = a[p];
// 将 >= x的元素交换到左边区域
// 将 <= x的元素交换到右边区域
while (true) {
while (a[++i].compareTo(x) < 0);
while (a[--j].compareTo(x) > 0);
if (i >= j) break;
MyMath.swap(a,i,j);
}
a[p] = a[j];
a[j] = x;
return j;
}
初始序列
{6,7,5,2,5,8} j--;
ji
{5,7,5,2,6,8} i++;
ji
{5,6,5,2,7,8} j--;
ji
{5,2,5,6,7,8} i++;
ji
完成快速排序具有 不稳定性 。
{6,7,5,2,5,8}
{5,2,5} 6 {7,8}
private static int randomizedPartition (int p,int r)
{
int i = random(p,r);
MyMath.swap(a,i,p);
return partition (p,r);
}
快速排序快速排序算法的性能取决于划分的对称性。通过修改算法 partition，可以设计出采用随机选择策略的快速排序算法。在快速排序算法的每一步中，当数组还没有被划分时，可以在 a[p:r]中随机选出一个元素作为划分基准，
这样可以使划分基准的选择是随机的，从而可以期望划分是较对称的。
最坏时间复杂度,O(n2)
平均时间复杂度,O(nlogn)
辅助空间,O(n)或 O(logn)
稳定性：不稳定线性时间选择给定线性序集中 n个元素和一个整数 k,1≤k≤n，要求找出这 n个元素中第 k小的元素
private static Comparable randomizedSelect(int p,int r,int k)
{
if (p==r) return a[p];
int i=randomizedpartition(p,r),
j=i-p+1;
if (k<=j) return randomizedSelect(p,i,k);
else return randomizedSelect(i+1,r,k-j);
}
在最坏情况下，算法 randomizedSelect需要 O(n2)计算时间但可以证明，算法 randomizedSelect可以在 O(n)平均时间内找出 n个输入元素中的第 k小元素。
线性时间选择如果能在线性时间内找到一个划分基准，使得按这个基准所划分出的 2个子数组的长度都至少为原数组长度的 ε倍 (0<ε<1是某个正常数 )，那么就可以 在最坏情况下 用 O(n)时间完成选择任务。
例如，若 ε=9/10，算法递归调用所产生的子数组的长度至少缩短 1/10。所以，在最坏情况下，算法所需的计算时间 T(n)满足递归式
T(n)≤T(9n/10)+O(n) 。由此可得 T(n)=O(n)。
将 n个输入元素划分成?n/5?个组，每组 5个元素，只可能有一个组不是 5个元素。用任意一种排序算法，将每组中的元素排好序，并取出每组的中位数，共?n/5?个。
递归调用 select来找出这?n/5?个元素的中位数。如果
n/5?是偶数，就找它的 2个中位数中较大的一个。以这个元素作为划分基准。
线性时间选择设所有元素互不相同。在这种情况下，
找出的基准 x至少比 3(n-5)/10个元素大，因为在每一组中有 2个元素小于本组的中位数，而 n/5个中位数中又有 (n-5)/10个小于基准 x。同理，基准
x也至少比 3(n-5)/10个元素小。而当
n≥75时,3(n-5)/10≥n/4所以按此基准划分所得的 2个子数组的长度都至少缩短 1/4。
private static Comparable select (int p,int r,int k)
{
if (r-p<5) {
//用某个简单排序算法对数组 a[p:r]排序 ;
bubbleSort(p,r);
return a[p+k-1];
}
//将 a[p+5*i]至 a[p+5*i+4]的第 3小元素
//与 a[p+i]交换位臵 ;
//找中位数的中位数,r-p-4即上面所说的 n-5
for ( int i = 0; i<=(r-p-4)/5; i++ )
{
int s=p+5*i,
t=s+4;
for (int j=0;j<3;j++) bubble(s,t-j);
MyMath.swap(a,p+i,s+2);
}
Comparable x = select(p,p+(r-p-4)/5,(r-p+6)/10);
int i=partition(p,r,x),
j=i-p+1;
if (k<=j) return select(p,i,k);
else return select(i+1,r,k-j);
}
复杂度分析
T(n)=O(n)
75
75
)4/3()5/()( 2
1
n
n
nTnTnC
CnT
上述算法将每一组的大小定为 5，并选取 75作为是否作递归调用的分界点。这 2点保证了 T(n)的递归式中 2个自变量之和
n/5+3n/4=19n/20=εn,0<ε<1。这是使 T(n)=O(n)的关键之处。当然，除了 5和 75之外，还有其他选择。
最接近点对问题给定平面上 n个点的集合 S，找其中的一对点，使得在 n个点组成的所有点对中，该点对间的距离最小。
为了使问题易于理解和分析，先来考虑 一维 的情形。此时，
S中的 n个点退化为 x轴上的 n个实数 x1,x2,…,xn 。最接近点对即为这 n个实数中相差最小的 2个实数。
假设我们用 x轴上某个点 m将 S划分为 2个子集 S1和 S2,基于 平衡子问题 的思想，用 S中各点坐标的中位数来作分割点。
递归地在 S1和 S2上找出其最接近点对 {p1,p2}和 {q1,q2}，并设 d=min{|p1-p2|,|q1-q2|},S中的最接近点对或者是 {p1,p2}，
或者是 {q1,q2}，或者是某个 {p3,q3}，其中 p3∈ S1且 q3∈ S2。
能否在线性时间内找到 p3,q3？
最接近点对问题
如果 S的最接近点对是 {p3,q3}，即 |p3-q3|<d，则 p3和 q3两者与 m的距离不超过 d,即 p3∈ (m-d,m],q3∈ (m,m+d]。
由于在 S1中，每个长度为 d的半闭区间至多包含一个点（否则必有两点距离小于 d），并且 m是 S1和 S2的分割点，因此
(m-d,m]中至多包含 S中的一个点。由图可以看出,如果 (m-
d,m]中有 S中的点，则此点就是 S1中最大点。
因此，我们用线性时间就能找到区间 (m-d,m]和 (m,m+d]中所有点，即 p3和 q3。 从而我们用线性时间就可以将 S1的解和 S2
的解合并成为 S的解 。
能否在线性时间内找到 p3,q3？
最接近点对问题
下面来考虑二维的情形。
选取一垂直线 l:x=m来作为分割直线。其中 m为 S中各点 x坐标的中位数。由此将 S分割为 S1和 S2。
递归地在 S1和 S2上找出其最小距离 d1和 d2，并设
d=min{d1,d2},S中的最接近点对或者是 d，或者是某个 {p,q}，
其中 p∈ P1且 q∈ P2。
能否在线性时间内找到 p,q？
最接近点对问题
考虑 P1中任意一点 p，它若与 P2中的点 q构成最接近点对的候选者，则必有 distance(p,q)＜ d。 满足这个条件的 P2中的点一定落在一个 d× 2d的矩形 R中
由 d的意义可知,P2中任何 2个 S中的点的距离都不小于 d。由此可以推出 矩形 R中最多只有 6个 S中的点 。
因此，在分治法的合并步骤中 最多只需要检查 6× n/2=3n个候选者能否在线性时间内找到 p3,q3？
证明,将矩形 R的长为 2d的边 3等分，将它的长为
d的边 2等分，由此导出 6个 (d/2)× (2d/3)的矩形。
若矩形 R中有多于 6个 S中的点，则由鸽舍原理易知至少有一个 (d/2)× (2d/3)的小矩形中有 2个以上 S中的点。设 u,v是位于同一小矩形中的 2个点，则
distance(u,v)<d。这与 d的意义相矛盾。
22222 3625)3/2()2/())()(())()(( dddvyuyvxux
为了 确切地知道要检查哪 6个点,可以将 p和
P2中所有 S2的点投影到垂直线 l上。由于能与
p点一起构成最接近点对候选者的 S2中点一定在矩形 R中，所以它们在直线 l上的投影点距 p
在 l上投影点的距离小于 d。由上面的分析可知，
这种投影点最多只有 6个。
因此，若将 P1和 P2中所有 S中点按其 y坐标排好序，则对 P1中所有点，对排好序的点列作一次扫描，就可以找出所有最接近点对的候选者。对 P1中每一点最多只要检查 P2中排好序的相继 6个点。
最接近点对问题最接近点对问题
public static double cpair2(S)
{
n=|S|;
if (n < 2) return ;
1,m=S中各点 x间坐标的中位数 ;
构造 S1和 S2；
//S1={p∈ S|x(p)<=m},
S2={p∈ S|x(p)>m}
2,d1=cpair2(S1);
d2=cpair2(S2);
3,dm=min(d1,d2);
4,设 P1是 S1中距垂直分割线 l的距离在 dm之内的所有点组成的集合；
P2是 S2中距分割线 l的距离在 dm之内所有点组成的集合；
将 P1和 P2中点依其 y坐标值排序；
并设 X和 Y是相应的已排好序的点列；
5,通过扫描 X以及对于 X中每个点检查 Y中与其距离在 dm之内的所有点 (最多 6个 )可以完成合并；
当 X中的扫描指针逐次向上移动时,Y中的扫描指针可在宽为 2dm的区间内移动；
设 dl是按这种扫描方式找到的点对间的最小距离；
6,d=min(dm,dl);
return d;
}
复杂度分析
T(n)=O(nlogn)
4
4
)()2/(2
)1()(
n
n
nOnT
OnT
设计一个满足以下要求的比赛日程表：
(1)每个选手必须与其他 n-1个选手各赛一次；
(2)每个选手一天只能赛一次；
(3)循环赛一共进行 n-1天。
按分治策略，将所有的选手分为两半,n个选手的比赛日程表就可以通过为 n/2个选手设计的比赛日程表来决定。递归地用对选手进行分割，直到只剩下 2个选手时，比赛日程表的制定就变得很简单。这时只要让这 2个选手进行比赛就可以了。
1 2 3 4 5 6 7 8
2 1 4 3 6 5 8 7
3 4 1 2 7 8 5 6
4 3 2 1 8 7 6 5
5 6 7 8 1 2 3 4
6 5 8 7 2 1 4 3
7 8 5 6 3 4 1 2
8 7 6 5 4 3 2 1
循环赛日程表设计一个满足以下要求的比赛日程表：
(1)每个选手必须与其他 n-1个选手各赛一次；
(2)每个选手一天只能赛一次；
(3)循环赛一共进行 n-1天。
按分治策略，将所有的选手分为两半,n个选手的比赛日程表就可以通过为 n/2个选手设计的比赛日程表来决定。递归地用对选手进行分割，直到只剩下 2个选手时，比赛日程表的制定就变得很简单。这时只要让这 2个选手进行比赛就可以了。
1 2 3 4 5 6 7 8
2 1 4 3 6 5 8 7
3 4 1 2 7 8 5 6
4 3 2 1 8 7 6 5
5 6 7 8 1 2 3 4
6 5 8 7 2 1 4 3
7 8 5 6 3 4 1 2
8 7 6 5 4 3 2 1
将要求解的较大规模的问题分割成 k个更小规模的子问题。
算法总体思想
n
T(n/2) T(n/2) T(n/2) T(n/2)
T(n) =
对这 k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为 k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。
算法总体思想
对这 k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为 k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。
nT(n) =
n/2
T(n/4)T(n/4)T(n/4)T(n/4)
n/2
T(n/4)T(n/4)T(n/4)T(n/4)
n/2
T(n/4)T(n/4)T(n/4)T(n/4)
n/2
T(n/4)T(n/4)T(n/4)T(n/4)
将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。
算法总体思想
将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。
nT(n) =
n/2
T(n/4)T(n/4)T(n/4)T(n/4)
n/2
T(n/4)T(n/4)T(n/4)T(n/4)
n/2
T(n/4)T(n/4)T(n/4)T(n/4)
n/2
T(n/4)T(n/4)T(n/4)T(n/4)
算法总体思想
将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。
nT(n) =
n/2
T(n/4)T(n/4)T(n/4)T(n/4)
n/2
T(n/4)T(n/4)T(n/4)T(n/4)
n/2
T(n/4)T(n/4)T(n/4)T(n/4)
n/2
T(n/4)T(n/4)T(n/4)T(n/4)
分治法的设计思想是，将一个难以直接解决的大问题，
分割成一些规模较小的相同问题，以便各个击破，
分而治之。
凡治众如治寡，分数是也。
----孙子兵法
2.1 递归的概念
直接或间接地调用自身的算法称为 递归算法 。
用函数自身给出定义的函数称为 递归函数 。
由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。
分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。
下面来看几个实例。
2.1 递归的概念例 1 阶乘函数阶乘函数可递归地定义为：
0
0
)!1(
1
!
n
n
nn
n
边界条件递归方程边界条件与递归方程是递归函数的二个要素，递归函数只有具备了这两个要素，才能在有限次计算后得出结果。
2.1 递归的概念例 2 Fibonacci数列无穷数列 1,1,2,3,5,8,13,21,34,55,…,被称为 Fibonacci数列。它可以递归地定义为：
边界条件递归方程 1
1
0
)2()1(
1
1
)(
n
n
n
nFnF
nF
第 n个 Fibonacci数可递归地计算如下：
public static int fibonacci(int n)
{
if (n <= 1) return 1;
return fibonacci(n-1)+fibonacci(n-2);
}
1,
2
0
)1),,1((),(
2)0,(
1),0(
2)0,1(
mn
n
m
mmnAAmnA
nnA
mA
A
2.1 递归的概念例 3 Ackerman函数当一个函数及它的一个变量是由函数自身定义时，称这个函数是 双递归函数 。
Ackerman函数 A(n,m)定义如下：
1,
2
0
)1),,1((),(
2)0,(
1),0(
2)0,1(
mn
n
m
mmnAAmnA
nnA
mA
A
2.1 递归的概念例 3 Ackerman函数前 2例中的函数都可以找到相应的非递归方式定义：
nnn )1(321!?
11
2
51
2
51
5
1
)(
nn
nF
但本例中的 Ackerman函数却无法找到非递归的定义。
2.1 递归的概念例 3 Ackerman函数
A(n,m)的自变量 m的每一个值都定义了一个单变量函数：
M=0时,A(n,0)=n+2
M=1时,A(n,1)=A(A(n-1,1),0)=A(n-1,1)+2，和 A(1,1)=2故
A(n,1)=2*n
M=2时,A(n,2)=A(A(n-1,2),1)=2A(n-1,2)，和
A(1,2)=A(A(0,2),1)=A(1,1)=2，故 A(n,2)= 2^n 。
M=3时，类似的可以推出
M=4时,A(n,4)的增长速度非常快，以至于没有适当的数学式子来表示这一函数。
n
2
22
2
2.1 递归的概念例 3 Ackerman函数
定义单变量的 Ackerman函数 A(n)为,A(n)=A(n，
n)。
定义其拟逆函数 α(n) 为,α(n)=min{k ｜
A(k)≥n} 。即 α(n) 是使 n≤A(k) 成立的最小的
k值。
α(n) 在复杂度分析中常遇到。对于通常所见到的正整数 n，有 α(n)≤4 。但在理论上 α(n)
没有上界，随着 n的增加，它以难以想象的慢速度趋向正无穷大。
2.1 递归的概念例 4 排列问题设计一个递归算法生成 n个元素 {r1,r2,…,rn}的全排列。
设 R={r1,r2,…,rn}是要进行排列的 n个元素,Ri=R-{ri}。
集合 X中元素的全排列记为 perm(X)。
(ri)perm(X)表示在全排列 perm(X)的每一个排列前加上前缀得到的排列。 R的全排列可归纳定义如下：
当 n=1时,perm(R)=(r)，其中 r是集合 R中唯一的元素；
当 n>1时,perm(R)由 (r1)perm(R1),(r2)perm(R2),…,
(rn)perm(Rn)构成。
2.1 递归的概念例 5 整数划分问题将正整数 n表示成一系列正整数之和,n=n1+n2+… +nk，
其中 n1≥n 2≥ … ≥n k≥1,k≥1 。
正整数 n的这种表示称为正整数 n的划分。求正整数 n的不同划分个数。
例如正整数 6有如下 11种不同的划分：
6；
5+1；
4+2,4+1+1；
3+3,3+2+1,3+1+1+1；
2+2+2,2+2+1+1,2+1+1+1+1；
1+1+1+1+1+1。
(2) q(n,m)=q(n,n),m?n;
最大加数 n1实际上不能大于 n。因此,q(1,m)=1。
(1) q(n,1)=1,n?1;
当最大加数 n1不大于 1时，任何正整数 n只有一种划分形式，
即nn 111
(4) q(n,m)=q(n,m-1)+q(n-m,m),n>m>1;
正整数 n的最大加数 n1不大于 m的划分由 n1=m的划分和
n1≤n -1 的划分组成。
(3) q(n,n)=1+q(n,n-1);
正整数 n的划分由 n1=n的划分和 n1≤n -1的划分组成。
2.1 递归的概念例 5 整数划分问题前面的几个例子中，问题本身都具有比较明显的递归关系，因而容易用递归函数直接求解。
在本例中，如果设 p(n)为正整数 n的划分数，则难以找到递归关系，因此考虑增加一个自变量：将最大加数 n1不大于 m的划分个数记作 q(n,m)。可以建立 q(n,m)的如下递归关系。
1
1,1
),()1,(
)1,(1
),(
1
),(
mn
mn
mn
mn
mmnqmnq
nnq
nnq
mnq
2.1 递归的概念例 5 整数划分问题前面的几个例子中，问题本身都具有比较明显的递归关系，因而容易用递归函数直接求解。
在本例中，如果设 p(n)为正整数 n的划分数，则难以找到递归关系，因此考虑增加一个自变量：将最大加数 n1不大于 m的划分个数记作 q(n,m)。可以建立 q(n,m)的如下递归关系。
正整数 n的划分数 p(n)=q(n,n)。
2.1 递归的概念例 6 Hanoi塔问题设 a,b,c是 3个塔座。开始时，在塔座 a上有一叠共 n个圆盘，这些圆盘自下而上，由大到小地叠在一起。各圆盘从小到大编号为 1,2,…,n,现要求将塔座 a上的这一叠圆盘移到塔座 b上，并仍按同样顺序叠臵。在移动圆盘时应遵守以下移动规则：
规则 1：每次只能移动 1个圆盘；
规则 2：任何时刻都不允许将较大的圆盘压在较小的圆盘之上；
规则 3：在满足移动规则 1和 2的前提下，可将圆盘移至
a,b,c中任一塔座上。
在问题规模较大时，较难找到一般的方法，因此我们尝试用递归技术来解决这个问题。
当 n=1时，问题比较简单。此时，只要将编号为 1的圆盘从塔座 a直接移至塔座 b上即可。
当 n＞ 1时，需要利用塔座 c作为辅助塔座。此时若能设法将 n-1个较小的圆盘依照移动规则从塔座 a移至塔座 c，然后，将剩下的最大圆盘从塔座 a移至塔座 b，最后，再设法将 n-1个较小的圆盘依照移动规则从塔座 c移至塔座 b。
由此可见,n个圆盘的移动问题可分为 2次 n-1个圆盘的移动问题，
这又可以递归地用上述方法来做。由此可以设计出解 Hanoi塔问题的递归算法如下。
2.1 递归的概念例 6 Hanoi塔问题
public static void hanoi(int n,int a,int b,int c)
{
if (n > 0)
{
hanoi(n-1,a,c,b);
move(a,b);
hanoi(n-1,c,b,a);
}
}
思考题：如果塔的个数变为 a,b,c,d
四个，现要将 n个圆盘从 a全部移动到 d，移动规则不变，求移动步数最小的方案。
递归小结优点,结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、
调试程序带来很大方便。
缺点,递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。
递归小结解决方法,在递归算法中消除递归调用，使其转化为非递归算法。
1.采用一个用户定义的栈来模拟系统的递归调用工作栈。该方法通用性强，但本质上还是递归，
只不过人工做了本来由编译器做的事情，优化效果不明显。
2.用递推来实现递归函数。
3.通过 Cooper变换,反演变换能 将一些递归转化为尾递归，从而迭代求出结果。
后两种方法在时空复杂度上均有较大改善，
但其适用范围有限。
分治法的适用条件分治法所能解决的问题一般具有以下几个特征：
该问题的规模缩小到一定的程度就可以容易地解决；
该问题可以分解为若干个规模较小的相同问题，即该问题具有 最优子结构性质
利用该问题分解出的子问题的解可以合并为该问题的解；
该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。
因为问题的计算复杂性一般是随着问题规模的增加而增加，因此大部分问题满足这个特征。
这条特征是应用分治法的前提，它也是大多数问题可以满足的，此特征反映了递归思想的应用能否利用分治法完全取决于问题是否具有这条特征，
如果具备了前两条特征，而不具备第三条特征，则可以考虑 贪心算法 或 动态规划 。
这条特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然也可用分治法，但一般用 动态规划 较好。
分治法的基本步骤
divide-and-conquer(P)
{
if ( | P | <= n0) adhoc(P); //解决小规模的问题
divide P into smaller subinstances P1,P2,...,Pk； //分解问题
for (i=1,i<=k,i++)
yi=divide-and-conquer(Pi); //递归的解各子问题
return merge(y1,...,yk); //将各子问题的解合并为原问题的解
}
人们从大量实践中发现，在用分治法设计算法时，最好使子问题的规模大致相同。即将一个问题分成大小相等的 k个子问题的处理方法是行之有效的。这种使子问题规模大致相等的做法是出自一种 平衡 (balancing)子问题 的思想，它几乎总是比子问题规模不等的做法要好。
分治法的复杂性分析一个分治法将规模为 n的问题分成 k个规模为 n／ m的子问题去解。
设分解阀值 n0=1，且 adhoc解规模为 1的问题耗费 1个单位时间。
再设将原问题分解为 k个子问题以及用 merge将 k个子问题的解合并为原问题的解需用 f(n)个单位时间。用 T(n)表示该分治法解规模为 |P|=n的问题所需的计算时间，则有：
1
1
)()/(
)1(
)(
n
n
nfmnkT
O
nT
通过迭代法求得方程的解,
1l o g
0
l o g )/()(
nm
j
jjkm mnfknnT
注意,递归方程及其解只给出 n等于 m的方幂时 T(n)的值，但是如果认为 T(n)足够平滑，那么由 n等于 m的方幂时 T(n)的值可以估计 T(n)的增长速度。通常假定 T(n)是单调上升的，从而当 mi≤n<mi+1时,T(mi)≤T(n)<T(mi+1)。
二分搜索技术分析,如果 n=1即只有一个元素，则只要比较这个元素和 x就可以确定 x是否在表中。因此这个问题满足分治法的第一个适用条件分析,比较 x和 a的中间元素 a[mid]，若 x=a[mid]，则 x在 L中的位臵就是 mid；如果 x<a[mid]，由于 a是递增排序的，因此假如 x在 a中的话,x必然排在 a[mid]的前面，所以我们只要在
a[mid]的前面查找 x即可；如果 x>a[i]，同理我们只要在 a[mid]
的后面查找 x即可。无论是在前面还是后面查找 x，其方法都和在 a中查找 x一样，只不过是查找的规模缩小了。这就说明了此问题满足分治法的第二个和第三个适用条件。
分析,很显然此问题分解出的子问题相互独立，即在 a[i]的前面或后面查找 x是独立的子问题，因此满足分治法的第四个适用条件。
给定已按升序排好序的 n个元素 a[0:n-1]，现要在这 n个元素中找出一特定元素 x。
分析,? 该问题的规模缩小到一定的程度就可以容易地解决；
该问题可以分解为若干个规模较小的相同问题 ;
分解出的子问题的解可以合并为原问题的解；
分解出的各个子问题是相互独立的。
二分搜索技术给定已按升序排好序的 n个元素 a[0:n-1]，现要在这 n个元素中找出一特定元素 x。
据此容易设计出 二分搜索算法,
public static int binarySearch(int [] a,int x,int n)
{
// 在 a[0] <= a[1] <=,.,<= a[n-1] 中搜索 x
// 找到 x时返回其在数组中的位臵，否则返回 -1
int left = 0; int right = n - 1;
while (left <= right) {
int middle = (left + right)/2;
if (x == a[middle]) return middle;
if (x > a[middle]) left = middle + 1;
else right = middle - 1;
}
return -1; // 未找到 x
}
算法复杂度分析：
每执行一次算法的
while循环,待搜索数组的大小减少一半。因此，在最坏情况下，
while循环被执行了
O(logn) 次。循环体内运算需要 O(1) 时间，
因此整个算法在最坏情况下的计算时间复杂性为 O(logn) 。
思考题,给定 a，用二分法设计出求 an的算法。
大整数的乘法请设计一个有效的算法，可以进行两个 n位大整数的乘法运算
小学的方法,O(n2)?效率太低
分治法,
a b
c d
复杂度分析
T(n)=O(n2)?没有改进?
1
1
)()2/(4
)1()(
n
n
nOnT
OnT
X =
Y =
X = a 2n/2 + b Y = c 2n/2 + d
XY = ac 2n + (ad+bc) 2n/2 + bd
大整数的乘法请设计一个有效的算法，可以进行两个 n位大整数的乘法运算
小学的方法,O(n2)?效率太低
分治法,
XY = ac 2n + (ad+bc) 2n/2 + bd
为了降低时间复杂度，必须减少乘法的次数。
1,XY = ac 2n + ((a-c)(b-d)+ac+bd) 2n/2 + bd
2,XY = ac 2n + ((a+c)(b+d)-ac-bd) 2n/2 + bd
复杂度分析
T(n)=O(nlog3) =O(n1.59)?较大的改进?
1
1
)()2/(3
)1()(
n
n
nOnT
OnT
细节问题,两个 XY的复杂度都是 O(nlog3)，但考虑到 a+c,b+d可能得到 m+1位的结果，使问题的规模变大，故不选择第 2种方案。
大整数的乘法请设计一个有效的算法，可以进行两个 n位大整数的乘法运算
小学的方法,O(n2)?效率太低
分治法,O(n1.59)?较大的改进
更快的方法
如果将大整数分成更多段，用更复杂的方式把它们组合起来，
将有可能得到更优的算法。
最终的，这个思想导致了 快速傅利叶变换 (Fast Fourier
Transform)的产生。该方法也可以看作是一个复杂的分治算法，对于大整数乘法，它能在 O(nlogn)时间内解决。
是否能找到线性时间的算法？？？目前为止还没有结果。
Strassen矩阵乘法
A和 B的乘积矩阵 C中的元素 C[i,j]定义为,?
n
k
jkBkiAjiC
1
]][[]][[]][[
若依此定义来计算 A和 B的乘积矩阵 C，则每计算 C的一个元素 C[i][j]，需要做 n次乘法和 n-1次加法。因此，算出矩阵 C的 个元素所需的计算时间为 O(n3)
传统方法,O(n3)
Strassen矩阵乘法使用与上例类似的技术，将矩阵 A,B和 C中每一矩阵都分块成 4
个大小相等的子矩阵。由此可将方程 C=AB重写为：
传统方法,O(n3)
分治法,
2221
1211
2221
1211
2221
1211
BB
BB
AA
AA
CC
CC
由此可得：
2112111111 BABAC
2212121112 BABAC
2122112121 BABAC
2222122122 BABAC
复杂度分析
T(n)=O(n3)?没有改进?
2
2
)()2/(7
)1()(
2?
n
n
nOnT
OnT
Strassen矩阵乘法
传统方法,O(n3)
分治法,
为了降低时间复杂度，必须减少乘法的次数。
2221
1211
2221
1211
2221
1211
BB
BB
AA
AA
CC
CC
)( 2212111 BBAM
2212112 )( BAAM
1122213 )( BAAM
)( 1121224 BBAM
))(( 221122115 BBAAM
))(( 222122126 BBAAM
))(( 121121117 BBAAM
624511 MMMMC
2112 MMC
4321 MMC
731522 MMMMC
复杂度分析
T(n)=O(nlog7) =O(n2.81)?较大的改进?
2
2
)()2/(8
)1()(
2?
n
n
nOnT
OnT
Strassen矩阵乘法
传统方法,O(n3)
分治法,O(n2.81)
更快的方法
Hopcroft和 Kerr已经证明 (1971)，计算 2个２ × ２矩阵的乘积,7次乘法是必要的。因此，要想进一步改进矩阵乘法的时间复杂性，就不能再基于计算 2× 2矩阵的 7次乘法这样的方法了。或许应当研究３ × ３或５ × ５矩阵的更好算法。
在 Strassen之后又有许多算法改进了矩阵乘法的计算时间复杂性。目前最好的计算时间上界是 O(n2.376)
是否能找到 O(n2)的算法？？？目前为止还没有结果。
棋盘覆盖在一个 2k× 2k 个方格组成的棋盘中，恰有一个方格与其他方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的 4种不同形态的 L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何 2个 L型骨牌不得重叠覆盖。
棋盘覆盖当 k>0时，将 2k× 2k棋盘分割为 4个 2k-1× 2k-1 子棋盘 (a)所示。
特殊方格必位于 4个较小子棋盘之一中，其余 3个子棋盘中无特殊方格。为了将这 3个无特殊方格的子棋盘转化为特殊棋盘，可以用一个 L型骨牌覆盖这 3个较小棋盘的会合处，如 (b)所示，
从而将原问题转化为 4个较小规模的棋盘覆盖问题。递归地使用这种分割，直至棋盘简化为棋盘 1× 1。
棋盘覆盖
public void chessBoard(int tr,int tc,int dr,int dc,int size)
{
if (size == 1) return;
int t = tile++,// L型骨牌号
s = size/2; // 分割棋盘
// 覆盖左上角子棋盘
if (dr < tr + s && dc < tc + s)
// 特殊方格在此棋盘中
chessBoard(tr,tc,dr,dc,s);
else {// 此棋盘中无特殊方格
// 用 t 号 L型骨牌覆盖右下角
board[tr + s - 1][tc + s - 1] = t;
// 覆盖其余方格
chessBoard(tr,tc,tr+s-1,tc+s-1,s);}
// 覆盖右上角子棋盘
if (dr < tr + s && dc >= tc + s)
// 特殊方格在此棋盘中
chessBoard(tr,tc+s,dr,dc,s);
else {// 此棋盘中无特殊方格
// 用 t 号 L型骨牌覆盖左下角
board[tr + s - 1][tc + s] = t;
// 覆盖其余方格
chessBoard(tr,tc+s,tr+s-1,tc+s,s);}
// 覆盖左下角子棋盘
if (dr >= tr + s && dc < tc + s)
// 特殊方格在此棋盘中
chessBoard(tr+s,tc,dr,dc,s);
else {// 用 t 号 L型骨牌覆盖右上角
board[tr + s][tc + s - 1] = t;
// 覆盖其余方格
chessBoard(tr+s,tc,tr+s,tc+s-1,s);}
// 覆盖右下角子棋盘
if (dr >= tr + s && dc >= tc + s)
// 特殊方格在此棋盘中
chessBoard(tr+s,tc+s,dr,dc,s);
else {// 用 t 号 L型骨牌覆盖左上角
board[tr + s][tc + s] = t;
// 覆盖其余方格
chessBoard(tr+s,tc+s,tr+s,tc+s,s);}
}
复杂度分析
T(n)=O(4k) 渐进意义下的最优算法
0
0
)1()1(4
)1()(
k
k
OkT
OkT
合并排序基本思想,将待排序元素分成大小大致相同的 2个子集合，分别对 2个子集合进行排序，最终将排好序的子集合合并成为所要求的排好序的集合。
public static void mergeSort(Comparable a[],int left,int right)
{
if (left<right) {//至少有 2个元素
int i=(left+right)/2; //取中点
mergeSort(a,left,i);
mergeSort(a,i+1,right);
merge(a,b,left,i,right); //合并到数组 b
copy(a,b,left,right); //复制回数组 a
}
}
复杂度分析
T(n)=O(nlogn) 渐进意义下的最优算法
1
1
)()2/(2
)1()(
n
n
nOnT
OnT
合并排序算法 mergeSort的递归过程可以消去。
初始序列 [49] [38] [65] [97] [76] [13] [27]
[38 49] [65 97] [13 76] [27]第一步第二步 [38 49 65 97] [13 27 76]
第三步 [13 27 38 49 65 76 97]
合并排序
最坏时间复杂度,O(nlogn)
平均时间复杂度,O(nlogn)
辅助空间,O(n)
稳定性：稳定思考题,给定 有序表 A[1:n]，修改合并排序算法，求出该有序表的逆序对数。
快速排序在快速排序中，记录的比较和交换是从两端向中间进行的，关键字较大的记录一次就能交换到后面单元，关键字较小的记录一次就能交换到前面单元，
记录每次移动的距离较大，因而总的比较和移动次数较少。
private static void qSort(int p,int r)
{
if (p<r) {
int q=partition(p,r); //以 a[p]为基准元素将 a[p:r]划分成
3段 a[p:q-1],a[q]和 a[q+1:r]，使得 a[p:q-1]中任何元素小于等于 a[q],a[q+1:r]中任何元素大于等于 a[q]。下标 q在划分过程中确定。
qSort (p,q-1); //对左半段排序
qSort (q+1,r); //对右半段排序
}
}
快速排序是对气泡排序的一种改进方法它是由 C.A.R,Hoare于 1962
年提出的快速排序
private static int partition (int p,int r)
{
int i = p,
j = r + 1;
Comparable x = a[p];
// 将 >= x的元素交换到左边区域
// 将 <= x的元素交换到右边区域
while (true) {
while (a[++i].compareTo(x) < 0);
while (a[--j].compareTo(x) > 0);
if (i >= j) break;
MyMath.swap(a,i,j);
}
a[p] = a[j];
a[j] = x;
return j;
}
初始序列
{6,7,5,2,5,8} j--;
ji
{5,7,5,2,6,8} i++;
ji
{5,6,5,2,7,8} j--;
ji
{5,2,5,6,7,8} i++;
ji
完成快速排序具有 不稳定性 。
{6,7,5,2,5,8}
{5,2,5} 6 {7,8}
private static int randomizedPartition (int p,int r)
{
int i = random(p,r);
MyMath.swap(a,i,p);
return partition (p,r);
}
快速排序快速排序算法的性能取决于划分的对称性。通过修改算法 partition，可以设计出采用随机选择策略的快速排序算法。在快速排序算法的每一步中，当数组还没有被划分时，可以在 a[p:r]中随机选出一个元素作为划分基准，
这样可以使划分基准的选择是随机的，从而可以期望划分是较对称的。
最坏时间复杂度,O(n2)
平均时间复杂度,O(nlogn)
辅助空间,O(n)或 O(logn)
稳定性：不稳定线性时间选择给定线性序集中 n个元素和一个整数 k,1≤k≤n，要求找出这 n个元素中第 k小的元素
private static Comparable randomizedSelect(int p,int r,int k)
{
if (p==r) return a[p];
int i=randomizedpartition(p,r),
j=i-p+1;
if (k<=j) return randomizedSelect(p,i,k);
else return randomizedSelect(i+1,r,k-j);
}
在最坏情况下，算法 randomizedSelect需要 O(n2)计算时间但可以证明，算法 randomizedSelect可以在 O(n)平均时间内找出 n个输入元素中的第 k小元素。
线性时间选择如果能在线性时间内找到一个划分基准，使得按这个基准所划分出的 2个子数组的长度都至少为原数组长度的 ε倍 (0<ε<1是某个正常数 )，那么就可以 在最坏情况下 用 O(n)时间完成选择任务。
例如，若 ε=9/10，算法递归调用所产生的子数组的长度至少缩短 1/10。所以，在最坏情况下，算法所需的计算时间 T(n)满足递归式
T(n)≤T(9n/10)+O(n) 。由此可得 T(n)=O(n)。
将 n个输入元素划分成?n/5?个组，每组 5个元素，只可能有一个组不是 5个元素。用任意一种排序算法，将每组中的元素排好序，并取出每组的中位数，共?n/5?个。
递归调用 select来找出这?n/5?个元素的中位数。如果
n/5?是偶数，就找它的 2个中位数中较大的一个。以这个元素作为划分基准。
线性时间选择设所有元素互不相同。在这种情况下，
找出的基准 x至少比 3(n-5)/10个元素大，因为在每一组中有 2个元素小于本组的中位数，而 n/5个中位数中又有 (n-5)/10个小于基准 x。同理，基准
x也至少比 3(n-5)/10个元素小。而当
n≥75时,3(n-5)/10≥n/4所以按此基准划分所得的 2个子数组的长度都至少缩短 1/4。
private static Comparable select (int p,int r,int k)
{
if (r-p<5) {
//用某个简单排序算法对数组 a[p:r]排序 ;
bubbleSort(p,r);
return a[p+k-1];
}
//将 a[p+5*i]至 a[p+5*i+4]的第 3小元素
//与 a[p+i]交换位臵 ;
//找中位数的中位数,r-p-4即上面所说的 n-5
for ( int i = 0; i<=(r-p-4)/5; i++ )
{
int s=p+5*i,
t=s+4;
for (int j=0;j<3;j++) bubble(s,t-j);
MyMath.swap(a,p+i,s+2);
}
Comparable x = select(p,p+(r-p-4)/5,(r-p+6)/10);
int i=partition(p,r,x),
j=i-p+1;
if (k<=j) return select(p,i,k);
else return select(i+1,r,k-j);
}
复杂度分析
T(n)=O(n)
75
75
)4/3()5/()( 2
1
n
n
nTnTnC
CnT
上述算法将每一组的大小定为 5，并选取 75作为是否作递归调用的分界点。这 2点保证了 T(n)的递归式中 2个自变量之和
n/5+3n/4=19n/20=εn,0<ε<1。这是使 T(n)=O(n)的关键之处。当然，除了 5和 75之外，还有其他选择。
最接近点对问题给定平面上 n个点的集合 S，找其中的一对点，使得在 n个点组成的所有点对中，该点对间的距离最小。
为了使问题易于理解和分析，先来考虑 一维 的情形。此时，
S中的 n个点退化为 x轴上的 n个实数 x1,x2,…,xn 。最接近点对即为这 n个实数中相差最小的 2个实数。
假设我们用 x轴上某个点 m将 S划分为 2个子集 S1和 S2,基于 平衡子问题 的思想，用 S中各点坐标的中位数来作分割点。
递归地在 S1和 S2上找出其最接近点对 {p1,p2}和 {q1,q2}，并设 d=min{|p1-p2|,|q1-q2|},S中的最接近点对或者是 {p1,p2}，
或者是 {q1,q2}，或者是某个 {p3,q3}，其中 p3∈ S1且 q3∈ S2。
能否在线性时间内找到 p3,q3？
最接近点对问题
如果 S的最接近点对是 {p3,q3}，即 |p3-q3|<d，则 p3和 q3两者与 m的距离不超过 d,即 p3∈ (m-d,m],q3∈ (m,m+d]。
由于在 S1中，每个长度为 d的半闭区间至多包含一个点（否则必有两点距离小于 d），并且 m是 S1和 S2的分割点，因此
(m-d,m]中至多包含 S中的一个点。由图可以看出,如果 (m-
d,m]中有 S中的点，则此点就是 S1中最大点。
因此，我们用线性时间就能找到区间 (m-d,m]和 (m,m+d]中所有点，即 p3和 q3。 从而我们用线性时间就可以将 S1的解和 S2
的解合并成为 S的解 。
能否在线性时间内找到 p3,q3？
最接近点对问题
下面来考虑二维的情形。
选取一垂直线 l:x=m来作为分割直线。其中 m为 S中各点 x坐标的中位数。由此将 S分割为 S1和 S2。
递归地在 S1和 S2上找出其最小距离 d1和 d2，并设
d=min{d1,d2},S中的最接近点对或者是 d，或者是某个 {p,q}，
其中 p∈ P1且 q∈ P2。
能否在线性时间内找到 p,q？
最接近点对问题
考虑 P1中任意一点 p，它若与 P2中的点 q构成最接近点对的候选者，则必有 distance(p,q)＜ d。 满足这个条件的 P2中的点一定落在一个 d× 2d的矩形 R中
由 d的意义可知,P2中任何 2个 S中的点的距离都不小于 d。由此可以推出 矩形 R中最多只有 6个 S中的点 。
因此，在分治法的合并步骤中 最多只需要检查 6× n/2=3n个候选者能否在线性时间内找到 p3,q3？
证明,将矩形 R的长为 2d的边 3等分，将它的长为
d的边 2等分，由此导出 6个 (d/2)× (2d/3)的矩形。
若矩形 R中有多于 6个 S中的点，则由鸽舍原理易知至少有一个 (d/2)× (2d/3)的小矩形中有 2个以上 S中的点。设 u,v是位于同一小矩形中的 2个点，则
distance(u,v)<d。这与 d的意义相矛盾。
22222 3625)3/2()2/())()(())()(( dddvyuyvxux
为了 确切地知道要检查哪 6个点,可以将 p和
P2中所有 S2的点投影到垂直线 l上。由于能与
p点一起构成最接近点对候选者的 S2中点一定在矩形 R中，所以它们在直线 l上的投影点距 p
在 l上投影点的距离小于 d。由上面的分析可知，
这种投影点最多只有 6个。
因此，若将 P1和 P2中所有 S中点按其 y坐标排好序，则对 P1中所有点，对排好序的点列作一次扫描，就可以找出所有最接近点对的候选者。对 P1中每一点最多只要检查 P2中排好序的相继 6个点。
最接近点对问题最接近点对问题
public static double cpair2(S)
{
n=|S|;
if (n < 2) return ;
1,m=S中各点 x间坐标的中位数 ;
构造 S1和 S2；
//S1={p∈ S|x(p)<=m},
S2={p∈ S|x(p)>m}
2,d1=cpair2(S1);
d2=cpair2(S2);
3,dm=min(d1,d2);
4,设 P1是 S1中距垂直分割线 l的距离在 dm之内的所有点组成的集合；
P2是 S2中距分割线 l的距离在 dm之内所有点组成的集合；
将 P1和 P2中点依其 y坐标值排序；
并设 X和 Y是相应的已排好序的点列；
5,通过扫描 X以及对于 X中每个点检查 Y中与其距离在 dm之内的所有点 (最多 6个 )可以完成合并；
当 X中的扫描指针逐次向上移动时,Y中的扫描指针可在宽为 2dm的区间内移动；
设 dl是按这种扫描方式找到的点对间的最小距离；
6,d=min(dm,dl);
return d;
}
复杂度分析
T(n)=O(nlogn)
4
4
)()2/(2
)1()(
n
n
nOnT
OnT
设计一个满足以下要求的比赛日程表：
(1)每个选手必须与其他 n-1个选手各赛一次；
(2)每个选手一天只能赛一次；
(3)循环赛一共进行 n-1天。
按分治策略，将所有的选手分为两半,n个选手的比赛日程表就可以通过为 n/2个选手设计的比赛日程表来决定。递归地用对选手进行分割，直到只剩下 2个选手时，比赛日程表的制定就变得很简单。这时只要让这 2个选手进行比赛就可以了。
1 2 3 4 5 6 7 8
2 1 4 3 6 5 8 7
3 4 1 2 7 8 5 6
4 3 2 1 8 7 6 5
5 6 7 8 1 2 3 4
6 5 8 7 2 1 4 3
7 8 5 6 3 4 1 2
8 7 6 5 4 3 2 1
循环赛日程表设计一个满足以下要求的比赛日程表：
(1)每个选手必须与其他 n-1个选手各赛一次；
(2)每个选手一天只能赛一次；
(3)循环赛一共进行 n-1天。
按分治策略，将所有的选手分为两半,n个选手的比赛日程表就可以通过为 n/2个选手设计的比赛日程表来决定。递归地用对选手进行分割，直到只剩下 2个选手时，比赛日程表的制定就变得很简单。这时只要让这 2个选手进行比赛就可以了。
1 2 3 4 5 6 7 8
2 1 4 3 6 5 8 7
3 4 1 2 7 8 5 6
4 3 2 1 8 7 6 5
5 6 7 8 1 2 3 4
6 5 8 7 2 1 4 3
7 8 5 6 3 4 1 2
8 7 6 5 4 3 2 1
