第四章 递归和分治

1

第四章 递归和分治

4.1 基于归纳的递归算法

4.1.1 归纳法的思想方法

归纳法的思想方法：对规模为n 的问题)(n P ：

1. 基础步：1a 是问题)1(P 的解；

2. 归纳步：对所有的n k k <<1,，若k b 是问题)(k P 的解，则)(k b p 是问题)1(+k P 的解。其中，)(k b p 是对k b 的某种运算或处理。 例：1a 是问题)1(P 的解，

若)(12a p a =，则2a 是问题)2(P 的解；

以此类推，若1-n a 是问题)1(-n P 的解，且)(1-=n n a p a ，则n a 是问题)(n P 的解。 为求问题)(n P 的解n a ，先求问题)1(-n P 的解1-n a ，再对1-n a 进行p 运算或处理。 为求问题)1(-n P 的解，先求问题)2(-n P 的解2-n a ，再对2-n a 进行p 运算或处理 如此等等，不断地进行递归求解，直到)1(P 为止。

当得到)1(P 的解之后，再回过头来，不断地把所得到的解进行p 运算或处理，直到得到)(n P 的解为止。

4.1.2 递归算法的例子

例4.1 计算阶乘函数!n 阶乘函数可归纳定义为：

??

?>-==0

!

)1(01!n n n n n

这是最简单、也是最为人们所熟知的例子。实现它的递归算法如下：

算法4.1 计算阶乘函数!n 输入：n 输出：!n

1. int factorial(int n)

2. {

3. if (n==0)

4. return 1;

/* 基础步 */

2

5. else

6. return n * factorial(n-1); /* 归纳步 */

7. }

基本操作：第6行的乘法

递归方程：

??

?+-==1

)1()(0

)0(n f n f f

由(2.4.2)式容易得到，)()(n n n f Θ==。

时间复杂性：)(n Θ

例4.2 基于递归的插入排序。

1）基础步：当1=n 时，数组只有一个元素，它已经是排序的； 2）归纳步：如果前面1-k

个元素已经按递增顺序排序，只要对第k

个元素逐一与前面

1-k 个元素比较，把它插入适当的位置，即可完成k 个元素的排序。

算法4.2 基于递归的插入排序算法 输入：数组A[],数组的元素个数n 输出：按递增顺序排序的数组A[] 1. template

2. void insert_sort_rec(Type A[],int n)

3. {

4. int k;

5. Type a;

6. n = n – 1;

7. if (n>0) {

/* n<=0 仅一个元素,已排序 基础步 */ 8. insert_sort_rec(A,n-1); /* 否则,排序前面n-1个元素 归纳步 */ 9. a = A[n];

/* 把第n 元素插入合适位置 */

10. k = n – 1;

11. while ((k>=0)&&(A[k]>a)) { 12. A[k+1] = A[k]; 13. k = k - 1; 14. }

15. A[k+1] = a; 16. } 17. }

复杂性分析

基本操作的选取：元素比较

3

递归方程：

??

?-+-==)

1()1()(0)0(n n f n f f

由(2.4.2)式容易得到：

)1(21

)1()(1

1

1

-==-=

∑∑=-=n n i i n f n

i n i

时间复杂性：)(2n O 空间复杂性：

每一次递归，都分配常数个工作单元用于递归栈，递归深度为n 。 空间复杂性：)(n Θ 例4.3 整数羃的计算。

计算以x 为底的n 次羃（整数羃）。让x 乘以自身n 次，需)(n Θ个乘法。

算法4.3 计算整数羃 输入：整数x 和非负整数n 输出：x 的n 次羃

1. int power(int x,int n)

2. {

3. int y;

4. if (n=0) y = 1;

/* 基础步 */

5. else {

6. y = power(x,n/2); /* 归纳步 */

7. y = y * y; 8. if (n%2==1) 9. y = y * x; 10. }

11. return y; 12. }

基本操作：乘法

??

?+==1

)2/()(1

)1(n f n f f 设k n 2=，)2()(k f k g =，把上式改写成：

??

?+-==1

)1()(1

)0(k g k g g 得到：

4

)

log (1log 1)()(n n k k g n f Θ=+=+==

时间复杂性：)

log (n Θ

工作单元：)

log

(n Θ

每一次递归，都需分配常数个工作单元用于递归栈，递归深度为n log

4.1.3 多项式求值的递归算法 4.1.4 排列问题的递归算法

存放于数组A 的n 个元素，生成其排列：

1. 第一个元素不动，生成后面1-n 个元素的排列；

2. 第一、第二个元素互换，生成后面1-n 个元素的排列；

3. 最后，第一个、第n 个元素互换，生成后面1-n 个元素的排列； 为生成后面1-n 个元素的排列，继续采取下面的步骤： 1. 第二个元素不动，生成后面2-n 个元素的排列； 2. 第二、第三个元素互换，生成后面2-n 个元素的排列； 3. 最后，第二个、第n 个元素互换，生成后面2-n 个元素的排列； 当排列的前2-n 个元素已确定后，为生成后面2个元素的排列，可以：

1. 第1-n 个元素不动，生成后面1个元素的排列，此时，n 个元素已构成排列；

2. 第1-n 、第n 个元素互换，生成后面1个元素的排列，此时，n 个元素已构成排列； 令排列算法perm (A ,k ,n )表示生成数组后面k 个元素的排列。有：

1. 基础步：1=k ，只有一个元素，已构成一个排列；

2. 归纳步：对任意的k ，n k ≤<1，为完成perm （A ，k ，n ），逐一对第k n -、第n

k

n ~-元素进行互换，每互换一次，就执行一次perm (A ,k -1,n )操作，产生一个排列。

算法4.5 排列的生成

输入：数组A[],数组的元素个数n 输出：数组A[]的所有排列 1. template

2. void perm(Type A[],int k,int n)

3. {

4. int i;

5. if (k==1)

6. for (i=0;i

/* 已构成一个排列,输出它 */

7. cout << A[i]; 8. else {

9. for (i=n-k;i

5

11. perm(A,k-1,n); 12. swap(A[i],A[n-k]); 13. } 14. } 15. }

基本操作：元素输出 递归方程：

??

?>-==1

)

1()()1(n n f n n f n f

得到!)(n n n f =。

算法的运行时间：)!(n n Θ。

每一次递归需常数个工作单元，递归深度为n ，递归栈的空间为)(n Θ。 例：对数组}3,2,1{=A ，算法的执行过程和递归栈的变化情况：

i

k

n A 的内容 输出结果 i n – k = 1 k n A 的内容 i n – k = 0 k n A 的内容

4.1.5 递归算法的讨论

结构清晰明了、容易阅读、容易用数学归纳法证明它的正确性。程序调试很方便 递归深度加深，工作栈所需空间增大，递归调用时所花辅助操作增多。运行效率较低。可修改为相应的循环迭代的算法。

4.2 分治法

4.2.1 分治法引言

例4.4最大最小问题。

算法4.6解最大最小问题的一般算法

输入：n个元素的数组A[]

输出：最大元素e_max和最小的元素e_min

1. void max_min(int A[],int &e_max,int &e_min，int n)

2. {

3. int i;

4. e_max = A[0]; e_min = A[0];

5. for (i=2;i<=n;i++) {

6. if (A[i]

7. if (A[i]>e_max) e_max = A[i];

8. }

9. }

输入规模为n时，元素比较次数是2

n。

2

算法4.7分治法解最大最小问题

输入：整数数组A[],数组的起始和结束边界low和high

输出：最大元素e_max和最小的元素e_min

1. void maxmin(int A[],int &e_max,int &e_min,int low,int high)

2. {

3. int mid,x1,y1,x2,y2;

4. if ((high-low <= 1)) {

5. if (A[high]>A[low]) {

6. e_max = A[high];

7. e_min = A[low];

8. }

9. else {

10. e_max = A[low];

11. e_min = A[high];

12. }

13. }

6

7

14. else {

15. mid = (low + high) / 2; 16. maxmin(A,&x1,&y1,low,mid); 17. maxmin(A,&x2,&y2,mid+1,high); 18. e_max = max(x1,x2); 19. e_min = min(y1,y2); 20. } 21. }

用分治法寻找最大最小元素的工作过程如图4.1所示：

图4.1 寻找最大最小元素的工作过程

时间复杂性分析：

令)(n C 表示对n 个元素的数组所执行的比较次数，其中，假定n 是2的羃。 递归方程：

??

?>+==2

2

)2/(2)(1)2(n n C n C C

令k n 2=，)()2()(k h C n C k ==，把上面方程改写成：

??

?>+-==1

2

)1(2)(1)1(k k h k h h

解上述递归方程，有：

2)2)2(2(2)(++-=k h k h

2

2)2(22

2

++-=k h

=

2

22

2

)1(22

2

1

1

+++++=--- k k k h

∑-=-+

=1

1

1

2

2

k i i

k

8

2

2

2

21-+=

k

k

2

2

3-=n

元素比较次数从原来的22-n ，减少为2)2/3(-n 。

递归深度为n k log =，每递归调用一次，分配常数个工作单元。 工作空间为)log (n Θ。

4.2.2 分治法的设计原理

思想方法：把规模为n 的问题)(n P ，分解为k 个规模较小、互相独立、结构与原来问题结构相同的子问题，又进一步的分解每个子问题，直到某个阀值0n 为止。递归地解这些子问题，再把子问题的解合并起来，得到原问题的解。

4.2.2.1 分治法的设计步骤

一般来说，可以把这种设计方法描述为：

divide_and_conquer()

(n P )

{

if (n <=0n ) return adhoc()

(n P );

else {

divide P into smaller subinstances 1P ,2

P

, ,k P ;

for (i=1;i<=k;i++)

i y = divide_and_conquer(i

P

);

return merge(1

y ,

2

y , ,k y );

} }

adhoc ：直接求解规模较小的问题P

merge ：把子问题1P ,2P , ,k P 的解1y ,2y , ,k y ，合并为问题P 的解 三个步骤组成：

1. 划分步：把输入的问题实例划分为k 个子问题。

尽量使k 个子问题的规模大致相同。 在很多情况下，使2=k

，例如，上面的最大最小问题那样。

取其中的一部分，而丢弃另一部分，如二叉检索问题用分治法处理

2. 治理步：当问题的规模大于某个预定义的阀值0n 时，治理步由k 个递归调用组成。

阀值0n 的选取：阀值可为任何正常数，大小与算法的性能有关

取决于算法中的adhoc 对阀值0n 的敏感程度，以及merge 的处理情况

9

3. 组合步：把子问题的解组合起来，对分治算法的实际性能至关重要 例：令m k n =，10=n

adhoc 解规模为1的问题，花费1个单位时间

merge 把k 个子问题的解合并成原问题的解，需花费n b 个单位时间，其中，0

>b

有递归方程

??

?>+==1

)/()(1)1(n n

b k n f k n f f

因为m k n =，所以，有：

m

m m

k

b k

f k k

f +=-)()(1

令)()(m h k f m =，上面的递归方程可以改写为：

??

?+-==m

k

b m h k m h h )1()(1)0(

解这个递归方程，得到

m

m k

b k

b m h k k m h n f ++-==-))2(()()(1

m

k

b m h k 2)2(2

+-=

=

m

m

k

b m h k

+=)0(

n n b n k

log

+=

整个运行时间中，adhoc 花费n 个单位时间，组合步花费n n b k log 时间。

当1>b ，n 很大时，它确定了算法的实际性能。

4.2.2.2 adhoc 、merge 、子问题个数与时间复杂性的关系

引理4.1 令a 、c 是非负整数，b 、d 和x 是非负常数，对某个非负整数k ，有k c n =，则递归方程：

???≥+==2

)/(1)(n n

b c n f a n d

n f x

的解是：

x

x

c

x

c

a n

d n n b n f =+=log

)(

（4.2.1） x

x

x x

a x x c

a n c a bc n c a bc

d n f c ≠???

?

??--????

??-+

=log )(（4.2.2）

证明 因为k c n =，有n k c log =，令)()()(n f c f k h k ==，原递归方程重新写成：

???≥+-==1

)1(0

)(k c

b k h a k d

k h x

k

解这个方程，有：

10

x

k x k c b c

b k h a a k h ++-=-))2(()()1(

x

k x

k c

b c

b a k h a ++-=-)1(2

)2(

=

x

k x

k x

k k c

b a c

b a

c

b a h a 0

22

1

)0(++++=--

x

i k k i i

k

c

b a

h a )(1

)0(--=∑+

=

i

k i x

x

k k

c

a bc

h a )

/()0(1

0∑-=+=

i

k i x

x

n

c

a n

b a

d c

)

/(1

log

∑-=+=

下面分两种情况讨论：

1. x c a =，在这种情况下，有：

n

k c

a c

i

k i x

log

)/(1

==∑-=

因为x c a x c c ==log log ，由(2.1.7)有，x

a

n

n

n

a c

c

==log

log

，由此得到：

i

k i x

x

n

c

a n

b a

d k h n f c

)

/()()(1

log

∑-=+==

n

n b n d c

x

x

log

+=

2. x c a ≠，在这种情况下，由(2.1.19)及k c n =，有：

1

)/()

/()/(1

--=

∑-=x

x

k

x x i

k i x

x

c a n

b c a n b c

a n

b

1)/(--=

x

x

k

c a n

b a b

x

x

x

n

x

c

a n

c b a

c b c

--=

log

x

x x

a

x c

a n

c b n

c b c

--=log

因此，

i

k i x

x

n

c

a n

b a

d k h n f c

)

/()()(1

log

∑-=+==

11

i

k i x

x

a

c

a n

b n

d c

)

/(1

0log

∑-=+=

x

x

x

a

x a

c

a n

c b n

c b n

d c

c

--+

=log

log

x x x a x x n c a c b n c a c

b d

c ???

? ?

?--???? ?

?-+

=log

定理证毕。

推论4.1 令a 、c 是非负整数，b 、d 和x 是非负常数，对某个非负整数k ，有k c n =，

则递归方程：

???≥+==2

)/(1)(n n

b c n f a n d

n f x

的解满足：

x

x

c

x

c

a n

d n n b n f =+=log )(

（4.2.3）

??

?

?

?-<

?

?

?--≥<≤)

/(,)

/(,)(a c c b d c a n a c c b a c

c b

d c a n

d n f x

x

x

x x x x

x

x

x

（4.2.4）

x

a x x c

a n c a c

b d n f

c >???

? ??-+

≤log )( （4.2.5）

证明（4.2.3）式直接由引理4.1得出。下面证明（4.2.4）式。 1.（4.2.4）式的证明：因为x c a <，有x c a x c c =

a

n

n c

；由引理

4.1，有：

x

x x

a x x n c a bc n c a bc

d n f c ???

?

??--????

?

?-+

=log )(

a

x x x x

x c n a c bc

d n a c bc log ???

?

??--

+???? ??-=

因此，当)(/a c c b d x x -≥时，有：

x

x x x x

x

n a c bc

d n a

c bc n f ???

?

?

?--

+????

??-≤)(

x

n

d =

当)(/a c c b d x x -<时，立即有：

12

x x x

n a c c b n f ???

?

??-≤)(

（4.2.4）式证毕。

2. （4.2.5）式的证明类似，留作练习。

推论 4.2 令a 、c 是非负整数，b 、d 是非负常数，对某个非负整数k ，有k c n =，则递归方程：

??

?≥+==2

)/(1)(n n

b c n f a n d

n f

的解是：

c a n

d n n b n f c

=+=log

)( （4.2.6） c

a n

c a bc n c a bc

d n f a c ≠??

? ??--??? ??

-+=log )(

（4.2.7）

证明 可从引理4.1得出。

定理4.1 令a 、c 是非负整数，b 、d 和x 是非负常数，对某个非负整数k ，有k c n =，则递归方程：

???≥+==2

)/(1)(n n

b c n f a n d n f x

的解是：

??

???>Θ=Θ<Θ=x

a x x

x x c

a n c a n n c a n n f c )()

log ()()(log （4.2.8）

如果令1=x ，则有：

??

?

??>Θ=Θ<Θ=c

a n c a n n c a n n f a c )()

log ()()(log （4.2.9）

证明 从引理4.1和推论4.1得出。

4.2.2.3 子问题规模与时间复杂性的关系

子问题规模各不相同。归纳法求解时间复杂性有困难

若递归方程B 的解预知，递归方程A 类似B 。令A 与B 的解存在常数因子c 的关系；然后证明并推导c 的大小，从而从侧面证明A 的解的上界或下界。

定理4.2 令b 、d 和1c 、2c 是大于0的常数，则下面递归方程：

??????

?≥++==2

)()(1)(21n n

b n

c f n c f n b

n f （4.2.10）

13

的解是：

??

?<+Θ=+Θ=1

)

(1)

log ()(2121c c n c c n n n f （4.2.11）

特别地，当121<+c c 时，有：

)()1(/)(21n O c c n b n f =--≤

（4.2.12）

证明：1）考虑121=+c c 的情况： 如果2/121==c c ，上述方程相当于：

??

?≥+==2

)2/(2)(1n n

b n f n f n b

由（4.2.6）式知，这个方程的解是n b n n b +log 。因此，假定存在一个待定常数0

>c ，使得

对所有的??n c 1、??n c 2，2≥n

，

n

b n n b

c n f +≤log )( （4.2.13）

成立。把上式代入所求解递归方程（4.2.11）的右边，有：

????n b n c f n c f n f ++

=)(

)(

)(21

????????????n b n c b n c n c b c n c b n c n c b c ++++≤222111log log

n b n c b n c n c b c n c b n c n c b c ++++≤222111log log

n

b c c c c n b c n b n n b c ++++=)log log (log 2211

要使（4.2.13）成立，必须有：

)log log (2211≤++n b c c c c n b c

因为121=+c c ，所以：

log log 2211<+c c c c

因此，有：

)log log (/12211c c c c c +-≥

则c 是一非负常数。因此：

)

log (log log log )(2

211n n O n b c c c c n n b n f =++-

≤

可以用类似的方法证明)log ()(n n n f Ω=，因此，)log ()(n n n f Θ=。

2）考虑121<+c c 的情况：

如果4/121==c c ，上述方程相当于：

??

?≥+==2

)4/(2)(1n n

b n f n f n b

14

由（4.2.7）式知，这个方程的解是n

b n b -2。因此，假定存在一个待定常数0

>c

，使得

对所有的??n c 1、??n c 2，2≥n ，

n

b c n f ≤)(

（4.2.14）

成立。把上式代入所求解递归方程的右边，有：

????n b n c f n c f n f ++

=)(

)(

)(21

????n b n c b c n c b c ++≤21

n b n c b c n c b c ++≤21 n

b n b

c c c ++=)(21

要使（4.2.14）成立，必须有：

n

b c n b n b c c c ≤++)(21

即有：

)1(/121c c c --≥

因此，有：

)()1(/)(21n O c c n b n f =--≤

（4.2.15）

4.2.3 快速排序

4.2.3.1 序列的划分

定义 4.1 给定序列n a a a ,,,21 ，如果存在元素k a ，使得对所有的k i i <≤1,，都有k i a a ≤，对所有的n j k j ≤<,，都有k j a a ≥，就称k a 是这个序列的枢点（pivot ）元素。

把序列的第一个元素作为枢点元素，重新排列这个序列

算法4.8 按枢点元素划分序列

输入：数组A[],序列的起始位置low,终止位置high 输出：按枢点元素划分的序列A[],枢点元素位置k 1. template

2. int split(Type A[],int low,int high)

3. {

4. int k,i = low;

5. Type x = A[low];

6. for (k=low+1;k<=high;k++) {

7. if (A[k]<=x) {

8. i = i + 1;

9. if (i!=k)

10. swap(A[i],A[k]); 11. }

15

12. }

13. swap(A[low],A[i]); 14. return i; 15. }

（a ） 在for 循环的每一轮循环之后

（b ） 在算法结束之后 图4.2 算法split 的工作情况

所有元素都与][low A 进行比较，需执行1-n 次元素比较，时间复杂性是)(n Θ。

4.2.3.2 快速排序算法的实现

算法4.9 快速排序算法

输入：数组A[],数组元素的的起始位置low,终止位置high 输出：按递增顺序排序的数组A[] 1. template

2. void quick_sort(Type A[],int low,int high)

3. {

4. int k;

5. if (low

6. k = split(A,low,high);

7. quick_sort(A,low,k-1);

8. quick_sort(A,k+1,high);

9. } 10. }

例4.5

16

初始数据

第1次划分 第2次划分 第3次划分 第4次划分 第5次划分 第6次划分 第7次划分 第8次划分

图4.3 quick_sort 算法的执行过程

4.2.3.3 最坏情况分析

元素已按递增或递减顺序排列，就处于最坏的情况。 算法quick_sort 所执行的元素比较的总次数是：

)

()1(2

101)2()1(2

n n n n n Θ=-=

+++-+-

在上述最坏情况下，算法的递归深度为n ，工作单元为)(n Θ。

可以用线性时间)(n Θ在n 个元素的序列中，选取中值元素作为枢点元素。 算法所执行的元素比较次数，就有如下的递归方程：

??

?>Θ+===1

)

()2/(2)(10)1(n n n f n f n f

可以得到)log ()(n n n f Θ=。

递归深度接近于n log 。工作单元为)log (n Θ。

4.2.3.4 平均情况分析

所有元素的关键字的值都不相同，被选取作为枢点元素的可能性都为n /1。 枢点元素，经split 重新排列后，位于序列的第k 位置，其中，n k ≤≤1， 则枢点元素左边的元素个数有1-k 个，右边的元素个数有k n -个。有：

??

?

??-+-+-==∑

=n k n k n f k f n

f n f 1)

)1()()1(((1

)0()(

17

??

?

?

?-+

-+-==∑=n

k k n f k f n n f n f 1

)

)()1(((1)1(0)0()(

因为：

∑

∑

∑

-====

-=

-+++=-1

1

1

)

()()1()1()0()1(n k n

k n

k k f k n f n f f f k f

所以：

∑

-=+

-=1

)

(2)1()(n k k f n

n n f

把上式两边乘以n ，得到：

∑

-=+-=1

)(2

)1()(n k k f n n n f n （4.2.13）

用1-n 取代上式中的n ，有：

∑

-=+--=--2

)

(2

)2()1()1()1(n k k f n n n f n （4.2.14）

令（4.2.13）-（4.2.14），得到：

)1(2)1()1()(-+-+=n n f n n f n

两边除以)1(+n n ，得到：

)

1()1(2)

1(1

)(+-+

-=

+n n n n

n f n n f

令)1(/)()(+=n n f n h ，代入上式，得到：

??

?

??>+-+-===0

)1()1(2)1()(00)0(n n n n n h n h n h

解此递归方程，得：

∑

∑

∑

===-+=+-=

n

k n

k n

k k

k k k k n h 1

1

1

12

1

22

)

1()1(2)(

∑

∑

=+=-=n

k n k k

k

1

1

2

12

14

18

∑

∑

==-????

?

?-++=n

k n

k k

n k 1

1

12

11

11

4

1

412

1

+-

=∑

=n n k

n

k

由（2.1.26）及（2.1.8），有：

)1(ln 2)(Θ-=n n h

)1(log /log 2Θ-=e n

n log 44.1≈

所以有：

n

n n h n n f log 44.1)()1()(≈+=

quick_sort 算法所执行的元素比较的平均次数是)log (n n Θ。

4.2.4 多项式乘积的分治算法

计算两个n 阶多项式)(x p 、)(x q 的乘积

n

n x

a x a a x p +++= 10)(

n

n x

b x b b x q +++= 10)(

得到12+n 项系数的n 2阶多项式，需2)1(+n 次乘法运算、及)1(+n n 次加法运算。

例:如，两个2阶多项式的乘积，得到5项系数的4阶多项式：

4

3

2

2

2

12572)432()31(x

x x x x x x x ++++=+++-

将需要9次乘法运算和6次加法运算。

4.2.4.1 多项式的划分原理

2

/10)()()(n x

x P x p x p +=

2

/10)()()(n x

x q x q x q += （4.2.15）

则有：

n

n x

x q x P x

x q x p x q x p x q x p x q x p )()())()()()(()()()()(112

/011000+++=（4.2.16）

因为：

)

)()(())()((1010x q x q x P x p ++

)()()()()()()()(01101100x q x P x q x P x q x P x q x P +++=

所以，

)

)()()()(0110x q x P x q x P +

)()()()())()(())()((11001010x q x P x q x P x q x q x p x P --++=

令：

19

)()()(000x q x p x r =

（4.2.17） )()()(111x q x p x r =

（4.2.18） )

)()(())()(()(10102x q x q x p x P x r ++=

（4.2.19）

则有：

n

n x

x r x

x r x r x r x r x q x p )())()()((()()()(12

/1020+--+= （4.2.20）

4.2.4.2 多项式乘积分治算法的实现

算法4.10 多项式乘积的分治算法

输入：存放多项式系数的数组p[]、q[],系数的项数n 输出：存放两个多项式乘积结果的系数的数组r0[]

1. void poly_product(float p[],float q[],float r0[],int n)

2. {

3. int m,i;

4. float *r1,*r2,*r3;

5. r1 = new float[2*n-1];

/* 多项式乘积的缓冲区*/

6. r2 = new float[2*n-1];

7. r3 = new float[2*n-1];

8. for (i=0;i<2*n-1;i++) /* 缓冲区清0 */

9. r0[i] = r1[i] = r2[i] = r3[i] = 0; 10. if (n==2)

/* 只有两项系数，直接计算 */

11. product(p,q,c);

12. else {

13. m = n / 2;

/* 项数划分为原来的一半 */ 14. poly_product (p,q,r0,m); /* 递归计算r0 */ 15. poly_product (p+m,q+m,r1+2*m,m); /* 递归计算r1 */

16. plus(p,p+m,r2+m,m); /* 计算 p0 + p1 */ 17. plus(q,q+m,r3,m);

/* 计算 q0 + q1 */ 18. poly_product (r2+m,r3,r2+m,m); /* 递归计算r2 */

19. mins(r2+m,r0,2*m-1);

/* 计算r2 – r0 – r1 */ 20. mins(r2+m,r1+2*m,2*m-1); 21. plus(r0+m,r2+m,r0+m,2*m-1); /* 合并结果 */

22. plus(r0+2*m,r1+2*m,r0+2*m,2*m-1); 23. } 24. delete r1; 25. delete r2; 26. delete r3; 27. }

20

系数只有两项时，直接用product 函数计算：

1. void product(float p[],float q[],float c[])

2. {

3. c[0] = p[0] * q[0];

4. c[2] = p[1] * q[1];

5. c[1] =(p[0] + p[1]) * (q[0] + q[1]) – c[0] – c[2];

6. }

两个具有n 项系数的多项式相加：

1. void plus(float p[],float q[],float c[],int n)

2. {

3. int i;

4. for (i=0;i

5. c[i] = p[i] + q[i];

6. }

两个具有n 项系数的多项式相减：

1. void mins(float p[],float q[],int n)

2. {

3. int i;

4. for (i=0;i

5. p[i] = p[i] - q[i];

6. }

0 2k-2

r 0 k 3k-2 2k 4k-2 0 4k-2 r 0 图4.4 合并三个多项式系数的情况

算法之2章递归与分治

算法分析(第二章)：递归与分治法 一、递归的概念 知识再现：等比数列求和公式： 1、定义：直接或间接地调用自身的算法称为递归算法。 用函数自身给出定义的函数称为递归函数。 2、与分治法的关系： 由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归经常同时应用在算法设计之中，并由此产生许多高效算法。 3、递推方程： (1)定义：设序列01,....n a a a简记为{ n a}，把n a与某些个() i a i n <联系起来的等式叫做关于该序列的递推方程。 (2)求解：给定关于序列{n a}的递推方程和若干初值，计算n a。 4、应用：阶乘函数、Fibonacci数列、Hanoi塔问题、插入排序 5、优缺点： 优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。 缺点：递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。 二、递归算法改进： 1、迭代法： (1)不断用递推方程的右部替代左部 (2)每一次替换，随着n的降低在和式中多出一项 (3)直到出现初值以后停止迭代 (4)将初值代入并对和式求和 (5)可用数学归纳法验证解的正确性 2、举例： -----------Hanoi塔算法----------- ---------------插入排序算法----------- ()2(1)1 (1)1 T n T n T =?+ = ()(1)1 W n W n n W =?+? （1）=0