2/8 第2章 递归与分治策略

分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。

2.2 分治法的基本思想

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 个子问题的处理方法是行之有效的。

分治法所能解决的问题一般具有以下几个特征：

(1)该问题的规模缩小到一定的程度就可以容易地解决；

(2)该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质.

(3)利用该问题分解出的子问题的解可以合并为该问题的解；

(4)该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。

2.4 大整数的乘法

X = a2n/2 + b Y = c2n/2 + d

1. XY = ac2n + (ad+bc) 2n/2 + bd (O(n 2))

2. XY = ac2n + ((a-c)(b-d)+ac+bd) 2n/2 + bd

T(n)=O(n log3)

2.8 快速排序

基本思想：

template<class Type>

void QuickSort (Type a[], int p, int r)

{

if (p<r) {

int q=Partition(a,p,r);

QuickSort (a,p,q-1); //对左半段排序

QuickSort (a,q+1,r); //对右半段排序

}

1

1)()2/(3)1()(>=⎩⎨⎧+=n n n O n T O n T