算法之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

21n-23()2(1)12[2(2)1]12(2)21...

2++2 (121)

n n n T n T n T n T n T ??=?+=?++=?++==++=?（1）2 ()(1)1((n-2)+11)1(2)(2)(1)

...

(1)12...(2)(1)

(1)/2

W n W n n W n n W n n n W n n n n =?+?=??+?=?+?+?==++++?+?=?

3、换元迭代：

(1)将对n 的递推式换成对其他变元k 的递推式 (2)对k 进行迭代

(3)将解（关于k 的函数）转换成关于n 的函数

4、举例：

---------------二分归并排序---------------

()2(/2)1W n W n n W =+?（1）=0

（1）换元：假设2k

n =，递推方程如下

()2(/2)1W n W n n W =+?（1）=0 → 1(2)2(2)21

k k k W W W

?=+?（0）=0

（2）迭代求解：

12122222321332133212()2(2)212(2(2)21)212(2)22212(2)2*221

2(2(2)21)2212(2)222212(2)3*2221...

2(0)*2(22...21)22k k k k k k k k k k k k k k k k k k k k k k k k W n W W W W W W W W k k ???????+?+???=+?=+?+?=+?+?=+??=+?+??=+?+??=+???==+?++++=?1log 1

n n n +=?+

（3）解的正确性—归纳验证： 证明递推方程的解是()(1)/2W n n n =?

()(1)1W n W n n W =?+?（1）=0

,(n 1)=n +n=n(n-1)/2+n =n[(n-1)/2+1]=n(n+1)/2

n W W +方法：数学归纳法证 n=1,W(1)=1*(1-1)/2=0假设对于解满足方程，则（）

---------------快速排序---------------------

>>>平均工作量：假设首元素排好序在每个位置是等概率的

1

1

2()()()(1)0n i T n T i O n n T ?==

+=∑ >>>对于高阶方程应该先化简，然后迭代

(1)差消化简：利用两个方程相减，将右边的项尽可能消去，以达到降阶的目的。

1

11

2

12

2

1

2()()()

()2()(1)(1)2()(1)

n i n i n i T n T i O n n nT n T i cn n T n T i c n ?=?=?==+=+??=+?∑∑∑ 1

2

221

1

()(1)(1)

2()(2()(1))

2(1)1()(1)(1)1()(1)1

11

n n i i nT n n T n T i cn T i c n T n c n

nT n n T n c n

T n T n c n n n ??==???=+?+?=?+=+?+?=+++∑∑

(2)迭代求解：

()(1)1

11

111(1)1(...)1321111(...)

13(log )()(log )

T n T n c n n n T c n n c n n n T n n n θθ?=+++=++++

+=++++==

三、递归树

1、概念

(1)递归树是迭代计算的模型

(2)递归树的生成过程与迭代过程一致

(3)递归树上所有项恰好是迭代之后产生和式中的项 (4)对递归树上的项求和就是迭代后方程的解 2、迭代在递归树中的表示

111(()...()()...(),....()...()t t t W m W m W m f m g m m m m

W m W m =+++++<++）其中称为函数项

注意：每个叶结点是一个函数项

3、二层子树的例子

二分归并排序：(2(/2)1W n W n n =+?） →

4、递归树的生成规则 ·初始：递归树只有根节点，其值为W(m) ·不断继续下述过程：

将函数项叶节点的迭代式W(m)表示成二层子树 用该子树替换该叶节点

·继续递归树的生成，直到树中无函数项（只有初值）为止 5、递归树生成实例

(2(/2)1W n W n n =+?）

>>>对递归树上的量求和：

11(2(/2)1,2,(1)0

()12...2(2)log 1

k k k W n W n n n W W n n n n kn n n n ??=+?===?+?++?=?=?+）

四、Master 定理（主定理）

--------------它提供了一种通过渐近符号表示递推关系式的方法。 1、应用背景：

T （n ）=aT(n/b)+f(n)

a ：规约后的子问题个数 n/

b ：规约后子问题的规模

f(n):归约过程及组合子问题的解的工作量

T 二分检索：（n ）=T(n/2）+1二分归并排序：T(n)=2T(n/2)+n-1

2、定理：

1,1a b T ≥>定理：设为常数，f(n)为函数，T(n)为非负整数，且（n ）=aT(n/b)+f(n)，则

log log log log log +1.logn .c<1n (/)(),n =a b a

b

a

b a

b

a

b af n b cf n T ε

εεθθθεθ??Ω?≤若f(n)=O(n ),>0,那么

T(n)=(n )

2.若f(n)=(n )，那么

T(n)=(n

)

3若f(n)=(n ),>0,且对于某个常数和充分大的有那么（）（f(n)）

3、应用：

993

3log log 1

2

a ?例1：求解递推方程：T(n)=9T(n/3)+n 解 上述递推方程中的=9,b=3,f(n)=n n

=n ,f(n)=O(n

)

2=1 T(n)=(n )

εθ相当于主定理的第一种情况，其中根据定理得到

13/2

log 0a 例2：求解递推方程：T(n)=T(2n/3)+1解 上述递推方程中的=1,b=3/2,f(n)=1n

=n =1,

T(n)=(logn)θ相当于主定理的第二种情况，根据定理得到

1

2log n =W(n/2)+1,W(1)=1a=1,b=2,n 1,()1n =logn W f n W θ==递归算法分析

二分检索：（）属于主定理第二种情况，（）（）

2

2log n =2W(n/2)+n-1,W(1)=0a=2,b=2,n n,()n-1n =nlogn W f n W θ==二分归并排序：（）属于主定理第二种情况，（）（）

不能使用主定理的例子：

22

log 1n =0nlogn=()

T n εε+>Ω求解（）2T(n/2)+nlogn a=2,b=2,n

=n,f(n)=nlogn

不存在使下式成立c<1af(n/b)cf(n)≤≤不存在使对所有充分大的n 成立2(n/2)log(n/2)=n(logn-1)cnlogn

五、分治法

1、基本思想：

将一个规模为n 的问题分解为k 个规模较小的子问题，这些子问题互相独立且与原问题相同。递归地求解这些子问题，然后将各子问题的解合并得到原问题的解。

2、设计过程：

–Divide ：整个问题划分为多个子问题

–Conquer ：求解各子问题(递归调用正设计的算法) –Combine ：合并子问题的解, 形成原始问题的解 注意：

(1)子问题与原问题性质完全一样 (2)子问题之间可彼此独立的求解 (3)递归停止时子问题可直接求解 3、算法分析:

设输入大小为n ，T(n)为时间复杂性 – Divide 阶段的时间复杂性 ? 划分问题为a 个子问题 ? 每个子问题大小为n/b ? 划分时间可直接得到=D(n) – Conquer 阶段的时间复杂性 ? 递归调用

? 求解时间= a T(n/b)

– Combine 阶段的时间复杂性 ? 时间可以直接得到=C(n) T(n)=θ(1) if n

T(n)=a T(n/b) + D(n)+C(n) otherwise 4、分治算法的特点：

(1)将原问题归约为规模小的子问题(子问题与原问题具有相同的性质)

(2)子问题规模足够小时可直接求解 (3)算法可以递归也可以迭代实现 (4)算法的分析方法：递推方程 5、分治法的一般描述

分治算法 divide-and-conquer(P)

1. if | P | <= c then S(P) //

2.

divide P into P1, P2, ..., Pk //3. for i←1 to k

4. yi=divide-and-conquer(Pi) //

5. 6、设计要点

(1)原问题可以划分或者归约为规模较小的子问题 注意：子问题与原问题具有相同的性质

子问题的求解彼此独立

划分时子问题的规模尽可能均衡 (2)子问题的规模足够小时可直接求解 (3)子问题的解综合得到原问题的解 (4)算法的实现：递归或迭代 7、分治算法时间分析

(1)时间复杂度函数的递推方程：

12()(||)(||)...(||)()

()k W n W P W P W P f n W c C

=++++= >>>P1,P2,…P k 为划分后产生的子问题

>>>f(n)为划分子问题以及将子问题综合得到原问题解的总工作量 >>>规模为c 的最小子问题的工作量为C

(2)两类常见的递推方程:

11()()()

2()()()

k

i i T n a T n i f n n

T n aT f n b

==?+=+∑方程：方程：

求解方法：方程1：迭代法，差消化简，递归树

方程2：迭代法，换元法，递归树，主定理

2()()()

n

T n aT f n b =+方程：

log log ()() a 1()O(logn) a=1()() a

O() a>b a

b a b

f n O n T n f n cn

O n T n n ?≠?=?

??=??

=???为常数

六、分治法的应用

1、二分搜索技术

问题描述：给定已按升序排好序的n 个元素a[1:n]，现要在这n 个元素中找出一特定元素x 分析：

? 该问题分解出的各个子问题是相互独立的，可以分解为若干个规模较小的相同问题；

? 该问题的规模缩小到一定的程度就可以容易地解决； ? 分解出的子问题的解可以合并为原问题的解； 算法设计思想：

? 通过x 与中位数T(m)比较，将原问题归结为规模减半的子问题，如果x 小于中位数，则子问题由小于T(m)的数构成，否则由大于T(m)的数构成。 ? 对于子问题进行二分搜索。

? 当子问题规模是1的时候，直接比较x 与T(m)，若相等则返回m ，否则返回0 算法伪代码：

BinarySearch(T, l, r, x)

输入：数组T ，下标从l 到r ；数x

输出：j //如果 x 在 T 中，j 为下标；否则为0 1. l←1; r←n 2. while l≤ r do 3. m←?(l+r)/2?

4. if T[m]=x then return m // x 恰好等于中位元素

5. else if T[m]>x then r ← m?1

6. else l←m+1

7. return 0

时间复杂度分析：

()(/2)1(1)1

W n W n W =+????= → ()log 1W n n =+可以解出

2、大整数乘法

问题描述：A 、B 两个十进制整数，A 有n 位（123456……n ），B 有n 位（123456……n ），求出A 和B 的乘积

分析：利用分治法，把每个大整数分成高位和低位两部分，转化成四个较小的乘积。这个思路的时间复杂度同样是O （n2）。

那么，有什么样的优化方案，可以使时间复杂度优于O （n2）呢？

这样一来，原本的4次乘法和3次加法，转变成了3次乘法和6次加法。

这样一来，时间复杂度是多少呢？

假设两个长度为n 的大整数相乘，整体运算规模是T(n) 。

刚才我们说过，两个大整数相乘可以被拆分成三个较小的乘积， 所以在第一次分治时，T(n)和T(n/2)有如下关系： T(n) = 3T(n/2) + f(n)

其中f(n)是6次加法的运算规模，f(n)的渐进时间复杂度很明显是O(n)。

此时让我们回顾一下master定理：

设常数a >= 1，b > 1，如果一个算法的整体计算规模T(n) = a T(n / b) + f(n)，那么则有如下规律：

对于T(n) = 3T(n/2) + f(n)这个关系式来说，a=3，b=2。

把a和b的值，以及f(n)的时间复杂度带入到master定理的第一个规律，也就是下面的规律：

发现正好符合条件。

怎么符合条件呢？推导过程如下：

所以我们的平均时间复杂度是：2 和 1.59 之间的差距看似不大，但是当整数长度非常大的时候，两种方法的性能将是天壤之别。

为了降低时间复杂度，必须减少乘法的次数。

如果将大整数分成更多段，用更复杂的方式把它们组合起来，将有可能得到更优的算法。最终地，这个思想导致了快速傅利叶变换(Fast Fourier Transform)的产生。该方法也可以看作是一个复杂的分治算法，对于大整数乘法，它能在O(nlogn)时间内解决。

3、Strassen矩阵乘法

n=）

问题描述：输入：两个n× n矩阵A和B（2k

输出：A和B的积,记作C

分析：矩阵运算在做科学运算时是必不可少的，用c/c++写代码，一般而言，需要做3次循环，其时间复杂度就是O(n3)。

上图给出了我们一般会采用的方法，就是对应元素相乘和相加。如果把C=A*B进行分解，可以看出，这里需要进行8次的乘法运算：

分别是：

r = a * e + b * g ;

s = a * f + b * h ;

t = c * e + d * g;

u = c * f + d * h;

本次介绍的算法就是Strassen提出的，可以将8次乘法降为7次乘法，虽然只是一次乘法，但是其实一次算法耗时要比加减法多很多。处理的方法是写成：p1 = a * ( f - h )

p2 = ( a + b ) * h

p3 = ( c +d ) * e

p4 = d * ( g - e )

p5 = ( a + d ) * ( e + h ) p6 = ( b - d ) * ( g + h ) p7 = ( a - c ) * ( e + f )

那么只需要计算p1,p2,p3,p4,p5,p6,p7，然后 r = p5 + p4 + p6 - p2 s = p1 + p2 t = p3 + p4

u = p5 + p1 - p3 - p7

这样，8次的乘法就变成了7次乘法和1次加减法 最终达到降低复杂度为O( n^lg7 ) ≈ O( n^2.81 )

2()7(/2)18(/2)(2)(1)

W n W n n W O =+=

log7 2.8075

()()()W n O n O n ==解： 4、合并排序

(1)二分归并排序基本思想

当n=1时终止划分，否则将待排序元素分成大致相同的两个集合，分别对两个集合进行排序，最终将排好序的子集合合并为所要求的排好序的集合。

(,,)[...]

1. p

2. then q ()/2

3. (,,)

4. (,1,)

5. (,,,)

MergeSort A p r A p r A if p r MergeSort A p q MergeSort A q r Merge A p q r ←+????+算法 输入：数组输出：元素按从小到大排序的数组

(2)二分归并排序设计思想 ·划分：将原问题归结为规模为n/2的2个子问题 ·继续划分，将原问题归结为规模为n/4的4个子问题，继续…,当子问题规模为1时，划分结束。 ·从规模1到n/2，陆续归并被排好序的两个子数组，每归并一次，数组规模扩大一倍，直到原始数组。 (3)算法伪代码

算法Merge(A,p,q,r) // 将排序数组A[p..q]与A[q+1,r]合并 1. x←q?p+1, y←r?q // x, y 分别为两个子数组的元素数 2. 将A[p..q]复制到B[1..x], 将A[q+1..r]复制到C[1..y] 3. i←1, j←1, k←p 4. while i≤x and j≤y do

5. if B[i]≤C[j] // B 的首元素不大于C 的首元素

6. A[k]←B[i] //将B 的首元素放到A 中

7. i←i+1

8. else

9. A[k]←C[j] 10. j←j+1 11. k←k+1

12. if i >x then 将C[j..y]复制到A[k..r] // B 已经是空数组 13. else 将B[i..x]复制到A[k..r] // C 已经是空数组

(3)二分归并排序时间复杂度分析

()2(/2)1(1)0

W n W n n W =+?= n W

可以解出

（）=nlogn-n+1 2W(n/2）： 把规模为n 的问题分成规模为 n/2的子问题。这是两个子问题的工作量。

n-1：两个排好序的子数组合并成整体的工作量。 W(1)=0：规模为1的工作量是0。 (4)算法图解

(5)自然合并排序 ·自然合并排序是合并排序算法的一种改进. ·对于初始给定的数组，通常存在多个长度大于1的已自然排好序的子数组段. 例如,若数组a 中元素为{4,8,3,7,1,5,6,2}，则自然排好序的子数组段有{4,8},{3,7},{1,5,6},{2}. ·构成更大的排好序的子数组段({3,4,7,8},{1,2,5,6}).继续合并相邻排好序的子数组段，直至整个数组已排好序. 图解：

5、快速排序

(1)快速排序基本思想：

? 用首元素x 作划分标准，将输入数组A 划分成不超过x 的元素构成的数组A L,大于x 的元素构成的数组A R ，其中A L ， A R 从左到右存放在数组A 的位置。

? 递归的对子问题A L ，A R 进行排序，直到子问题的规模为1时停止 (2)算法伪代码

(3) 快速排序时间复杂度分析

最坏的情况就是每一次取到的元素就是数组中最小/最大的，这种情况其实就是冒泡排序了(每一次都排好一个元素的顺序)

()(-1)1 (1)0

W n W n n W =+?=最坏情况： → ()(1)/2W n n n =?可以解出

最坏情况下时间复杂度O(n2)

最好的情况就是每一次取到的元素都刚好平分整个数组

()2(/2)1 (1)0

W n W n n W =+?=最好情况： → ()(log )W n n n θ=可以解出

平均时间复杂度：O(nlogn)

6、线性时间选择

问题描述：从给定的集合L 中选择第i 小的元素

输入：数组S, S 的长度n, 正整数k, 1≤ k≤ n. 输出：第 k 小的数.

(1)选最大问题 算法伪代码：

算法Findmax

输入：n 个数的数组L 输出：max 1. max←L[1]； 2. for i←2 to n do 3. if max

6. return max

算法最坏情况下的时间复杂度W(n)=n ?1 (2)选最大最小问题 算法伪代码：

算法FindMaxMin(通常算法) 输入：n 个数的数组L 输出：max ，min

1．将n 个元素两两一组分成 ?n/2? 组

2．每组比较，得到?n/2? 个较小和?n/2? 个较大 3．在 ?n/2? 个较大(含轮空元素)中找最小max 4．在?n/2? 个较小(含轮空元素)中找最小min 最坏情况下时间复杂度分析：

W(n) = ?n/2? +2 ?n/2? ?2 = n+?n/2? ?2 = ?3n/2? ?2

k

n=n =(2)1

W W =假设2（）2W(n/2)+2 解 =3n/2-2

(3)选第二大问题 通常算法：顺序比较

1．顺序比较找到最大max;

2．从剩下的n ?1个数中找最大，就是第二大second; 时间复杂性度：W(n)=n ?1+n ?2=2n ?3

提高效率的方法：

?成为第二大数的条件：仅在与最大数的比较中被淘汰

?要确定第二大数，必须知道最大数

?在确定最大数的过程中记录下被最大数直接淘汰的元素

>>>两两分组比较，大者进入下一轮，知道剩下一个元素max为止

>>>在每次比较中淘汰较小元素，将被淘汰元素记录在淘汰它的元素的链表上>>>检查max的链表，从中找到最大元素，即second

算法FindSecond

输入：n个数的数组L

输出：Second

1．k ←n

2．将k 个元素两两一组，分成?k/2?组

3．每组的2个数比较，找到较大的数

4．将被淘汰的较小的数在淘汰它的数所指向的链表中做记录

5．if k 为奇数then k ← ?k/2? +1

6．else k ← ?k/2?

7．if k>1 then goto 2

8．max ←最大数

9．second ← max 的链表中的最大

图解：

(4)应用：m*的选择与划分过程

问题引入：

假设元素彼此不等，设计思想：

1、用某个元素m*作为标准将S划分成S1与S2，其中S1的元素小于m*，

S2的元素大于等于m*

2、如果k<=|S1|，则在S1中找第k小

如果k=|S1|+1，则m*是第k小

如果k>|S1|+1，则在S2中找第k- |S1|-1小

(算法效率取决于子问题规模，如何通过m*控制子问题规模)

图解：

算法伪代码：

算法Select(S,k)

输入：数组S，正整数k

输出：S中的第k 小元素

1．将S划分成5 个一组，共nM = ? n/5?个组

2．每组找中位数，nM 个中位数放到集合M

4．把A和D的每个元素与m*比较，小的构成S1, 大的构成S2

5．S1←S1∪C; S2←S2∪B 划分

7．else if k≤|S1|

8．then Select(S1,k) //递归计算子问题

9．else Select(S2,k－|S1|－1)

算法设计要点：

（1）选第k的算法

（2）分治策略

（3）确定m*

（4）用m*划分数组归约为子问题

（5）递归实现

子问题规模估计：

n=5(2r+1)

|A|=|D|=2r

子问题规模至多：2r+2r+3r+2=7r+2 不妨设：n=5(2r+1) |A|=|D|=2r

/511

2102

17377r 27()210210210n n r n n n

?=

=?+=?+=?<

划分后子问题规模至多

算法工作量：W (n ) ≤W (n/5)+W (7n/10) + O (n )

递归树：W (n) ≤W(n/5)+W (7n/10) + tn

W(n) ≤tn(1+0.9+0.92+…)=O(n)

*分5个元素为一组的原因：

分析：递归调用

1、求m*的工作量与|M|=n/t 相关，t 为每组元素数，t 大，|M|小

2、归约后子问题大小与分组数t 有关，t 大，子问题规模大

算法之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