第5章递推算法
递推算法是一种按照规律分步解决复杂问题的方法，利用计算机速度和不断重复的特点把复杂过程转化为简单过程的多次重复。递归是从小规模问题求解大规模问题的常用工具。本章介绍递推和递归、递推和倒推、递推方程的求解方法和常用问题的递推算法。


视频讲解


5.1递推算法概述
5.1.1递推


递推又叫正推，是从小规模的问题推解出大规模问题的一种方法，是迭代算法最基本的表现形式。
例1： 计算数列{an}的前n项和。
数列{an}的前n项和 Sn=a1+a2+…+an。又Sn-1=a1+a2+…+an-1。所以，递推公式Sn＝Sn-1+an 成立，在求出前n-1项和的基础上推出前n项和。
例2： 计算n！。
n!=1×2×…×n，又 (n-1)!=1×2×…×(n-1)。所以，递推公式n!＝n(n-1)!成立，在求出(n-1)!的基础上推出n!。
算法的控制结构有顺序、选择、循环和模块调用，模块调用又分为模块间的调用和模块自身的直接与间接调用(递归)。递推经常使用递归和迭代实现，本例的递归和循环实现如下。
递归实现F(n)=nF(n-1)=n!： 循环实现s=s*i： 
输入： n。输入： n。
输出： n!。输出： s。

F(n) {1.s=1

1.if(n<2) then2.for i=2 to n do 

2.return n3.s=s*i 

3.else return n*F(n-1)4.return s

4.}


递归的计算过程是F(n)=nF(n-1)=n(n-1)F(n-2)=…=n×(n-1)×…×2×F(1)。循环的计算过程是s=1×2,s=1×2×3,…,s=1×2×3×…×n，计算的时间复杂度都是O(n)。




5.1.2递推与递归
直接或间接调用自身的算法称为递归算法。用函数自身给出定义的函数称为递归函数。递归函数有两个要素，分别是边界条件与递归方程。具备这两个要素，才能在有限次计算后得出结果，这也是递归设计的要点。
递归算法的执行过程分递推和回归两个阶段。递推阶段将大规模问题分解为小规模问题求解； 回归阶段将小规模问题的解逐级返回，依次计算大规模问题的解，最后返回整个问题的解。
递归一般用于解决如下三类问题。
(1) 数据的定义是按递归定义的，如斐波那契函数、n的阶乘等。
(2) 问题的解法按递归实现，如回溯算法。
(3) 数据的结构形式是按递归定义的，如二叉树的遍历、图的搜索等。
例3： 一对兔子出生两个月后，每月生一对小兔子。小兔子两个月后又开始生下一代小兔子。假若兔子只生不死，一月初抱来一对刚出生的小兔子，一年中每个月各有多少对兔子？
问题分析： 每月的兔子对数如表51所示，小兔对数加成兔对数等于当月的总对数。从表51中分析可以得到，当月的兔子对数=本月成兔对数+本月小兔对数=上月的兔子对数+上上月的兔子对数。因为上月的兔子，不管是成兔还是小兔，当月都是成兔，所以本月成兔对数等于上月兔子对数。上上月的一对兔子，本月都会生一对小兔子，因此本月小兔对数等于上上月兔子对数。


表51每月的兔子对数



月份一月二月三月四月五月六月…十二月

对数111+1=22+1=33+2=55+3=8…？
递推1abcccc…c
递推2abcabc…c
递推3ababab…b


假设第n个月的兔子对数使用F(n)表示，则有F(n)=F(n-1)+F(n-2)。
F（n）构成的数列又称为斐波那契数列或兔子序列，该数列在兔子繁殖、上楼方式、树枝、蜂房、声音、花瓣等问题中得到广泛应用。
递推可以很容易使用递归实现，递推式转换为递归方程，边界条件为F(0)=0，F(1)=1。
斐波那契数列的递归实现： 
输入： n。
输出： F(n)。

F(n) {

1.if (n==0) then return 0

2.if (n==1) then return 1

3.else return F(n-1)+F(n-2)

}


F(5)的递归树如图51所示，节点旁的数字表示递归调用的次序，实箭头线表示递推过程的分解关系，虚箭头线表示回归过程的求值关系，虚箭头线上的数字表示求值结果。算法的实现类似于二叉树生成的过程，因此算法的时间复杂度为O(2n)。


图51斐波那契数列递归计算过程


斐波那契数列的递推实现： 
输入： n。
输出： F。

1.F［0］=0

2.F［1］=1

3.for i=2 to n do   

4.F［i］=F［i-1］+F［i-2］

5.print(F［i］)


算法的时间复杂度为O(n)。实际上，斐波那契数列可以直接推导出结果，即

F(n)=151+52n-1-52n

递推与递归的比较如下。
(1) 递归是从问题的最终目标出发，逐渐将复杂问题化为简单问题，先解决简单问题，然后回溯求得问题的解。递推是从简单问题出发，一步一步向前发展，最终求得问题解。
(2) 递归是逆向的，递推是正向的。
(3) 递归表现为自己调用自己，递推则没有这样的形式。
(4) 一般来说，递推的效率高于递归，因此一般将递归转化为递推。
(5) 每个迭代算法原则上总可以转换为与它等价的递归算法； 反之不然。
5.1.3递推与循环
循环用于重复性的工作。循环体的特点是“以不变应万变”。所谓“不变”是指循环体内运算的表现形式(变量表示的循环条件、循环体)是不变的，而数据变化用变量表示，变量取值不同则每次具体的执行内容不尽相同。循环设计主要是从建好的数据模型中选择合适的变量，构造不变的循环条件和循环体——循环不变式。例如，例2中 s=s×i 就是循环不变式。变量i表示循环次数，也表示当次循环的乘数； 变量s保存前次和当次循环的累乘结果。初始s=1，第1次循环后 s=s×2=1×2，第2次循环后s=s×3=1×2×3,……，第n-1次循环后s=s×n=1×2×…×n。
例4： 可以有不同的循环不变式，如表51所示。如果一月用a表示，二月用b表示，三月及以上用c表示，则有c=a+b，其实现如下。
输入： n。
输出： F(n)。

1.a=1

2.b=1

3.for i=1 to n-2 do   

4.c=a+b

5.print(c)

6.a=b

7.b=c

8.return c



算法每次循环递推1步，使用3个变量，其时间复杂度为O(4n)。当n=12时，算法需要10次循环。
如果一月用a表示，二月用b表示，三月用c表示，四月又用a表示，五月又用b表示，则有c=a+b，a=c+b，b=c+a，其实现如下。
输入： n。
输出： F(n)。


1.a=1

2.b=1

3.for i=1 to n/3  do   

4.c=a+b  

5.a=b+c  

6.b=c+a  

7.print(c,a,b)


算法每次循环递推3步，使用3个变量，其时间复杂度为O(4n/3)。当n=12时，算法需要4次循环，算法最后输出的并不是12项，而是2+3×4=14项。 
如果一月用a表示，二月用b表示，三月又用a表示，则有a=a+b，b=b+a，其实现如下。
输入： n。
输出： F(n)。


1.a=1

2.b=1

3.for i=1 to n/2 do   

4.a=a+b  

5.b=a+b  

6.print(a,b)


算法每次循环递推2步，使用2个变量，其时间复杂度为O(3n/2)。当n=12时，算法需要5次循环。
上述算法都是递推算法，循环不变式就是递推公式，利用计算机计算速度快和递推算法不断重复的特点把复杂过程转化为简单过程的多次重复。
5.1.4递归与非递归
递归与循环都是解决“重复操作”的机制。递归代码简洁，结构清晰，容易理解，容易用归纳法证明，而设计循环不变式则比较困难。递归实现耗费更多的时间(调用和返回需要额外的时间)与存储空间(栈保存递归调用的变量值)，这也限制了递归的深度。因此一般将递归算法转变为非递归算法。递归与非递归算法的比较如表52所示。


表52递归与非递归算法的比较



算法可读性代码量时间空间适用范围设计难度

递归易小长大广易
非递归难大短小窄难

递归算法转变为非递归算法的常用方法如下。
(1)  采用一个用户定义的栈来模拟系统的递归调用工作栈。该方法通用性强，但本质上还是递归，只不过人工做了本来由编译器做的事情，优化效果不明显。
(2) 用递推来实现递归函数。
(3) 通过变换将递归转化为尾递归，从而迭代求出结果。
后两种方法在时空复杂度上均有较大改善，但其适用范围有限。尾递归中递归调用是整个函数体中最后执行的语句并且它的返回值不属于表达式的一部分，其特点是回归过程中不用做任何操作。这个特性很重要，因为大多数现代编译器会利用这个特点自动生成优化的代码。
例2的尾递归实现： 
输入： n。
输出： F(n,1)。


F(n,a) { 

1.if(n==0) then return 0

2.else if(n==1) then 

3.return a

4.else return F(n-1,n*a)

}


时间复杂度为O(n)。第1次调用返回的结果是F(n-1,n)，第2次调用返回的结果是F(n-2,n(n-1)),……,第n次返回的结果是F(1，n(n-1)…2)。当前的运算结果(路径)作为参数传给下层函数，函数在递归调用前完成所有计算并把结果交给子函数，子函数不需要再去创建一个栈帧，直接就用当前栈帧把原先的数据覆盖即可。一是防止栈溢出，二是节省了调用函数时创建栈帧的开销。
例4的尾递归实现： 
输入： n。
输出： F(n,1,1)。

1.F(n,ret1,ret2) {   

2.if(n==1) then return 1

3.else if(n==2) then return rect2

4.return F(n-1,ret2,ret1+ret2)  

}


时间复杂度为O(n)。第1次调用返回的结果是F(n-1,1,2)，第2次调用返回的结果是F(n-2,2,3)，第3次调用返回的结果是F(n-3,3,5)……
前面两个例子中的函数都可以找到相应的非递归方式定义，但有些函数找不到相应的非递归方式定义，如Ackerman函数。
例5：  Ackerman函数。

A(1,0)=2

A(0,m)=1m≥0

A(n,0)=n+2n≥2

A(n,m)=A(A(n-1,m),m-1)n,m≥1

Ackerman函数是双递归函数，函数和它的一个变量都由函数自身定义。
m=1时，A(n,1)=A(A(n-1,1),0)=A(n-1,1)+2，又 A(1,1)=2，故A(n,1)=2n，n≥1。
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)=2n。
m=3时，类似地可以推出A(n,3)=22…2，其中2的层数为n。
m=4时，A(n,4)的增长速度非常快，以至于没有适当的数学式子来表示这一函数，因此不能转为非递归。
5.1.5切分问题
王小二自夸刀工不错，有人放一张大的煎饼在砧板上，问他： “饼不许离开砧板，切n刀最多能分成多少块？”
问题分析：  切分块数统计如表53所示。切一次分成两块(2=1+1)，切两次分成4块(4=2+2)，切3次分成7块(7=3+4)……


表53切分块数统计



切分次数012345
切分块数12471116

设第n次切分块数为F(n)，根据表53，有F(n)=F(n-1)+n，F(0)=1。
切分问题的递推算法： 
输入： n。
输出： F(n)。

1.F［0］=1

2.for i=1 to n do

3.F［i］=F［i-1］+i

4.return F［n］


实际上由F(n)=F(n-1)+n，可得F(n-1)=F(n-2)+n-1，这样可以直接推出结果。


F(n)=F(n-1)+n

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



=F(0)+1+…+n

=1+n(n+1)/2
5.1.6狱吏问题
狱吏问题： 国王对囚犯大赦，让狱吏n次通过一排锁着的n间牢房，每通过1次，按规则转动某些门锁，进行开关转换，最后门锁开着的牢房中的犯人获释。转动门锁的规则如下：  第1次转动所有门锁； 第2次从第2间牢房开始每隔1间转动1次；  ……； 第k次从第k间牢房开始，每隔k-1间转动1次。转动n次后哪些牢房的门锁是开的？
问题分析1： 设置长度为n的数组进行模拟。第1轮次转动1、2、…、n号牢房，第2轮次转动2、4、…号牢房,……,第k轮次转动k、2k、…号牢房。
输入： n。
输出： A。

1.for i=1 to n do

2.A［i］=1//初始化门锁关

3.for i=1 to n do

4.for j=i to n do

5.A［j］=1-A［j］ //转动门锁

6.j=j+i

7.return A


算法的时间复杂度为 n+n/2+n/3+…+n/n=O(nlnn)。
问题分析2： 设d(n)表示n的不重复因子个数，如4的因子是1、2和4，正好是门锁的开关次数。牢房开始是锁的，因此因子个数为奇数的房间，就是最后门锁开的房间。
输入： n。
输出： 最后门锁开的房间号。

1.for i=1 to n do

2.d=1

3.for j=2 to i do

4.if (i mod j==0) then d=d+1

5.if (d mod 2==1) print i


算法的时间复杂度为 1+2+3+…+n=O(n2)。
问题分析3： 设d(n)表示n的不重复因子个数，d(n)为奇数的就是最后门锁开的房间。d(n)为奇数的房间号为1,4,9,…，正好是完全平方数。因为因子是成对出现的，只有完全平方数的两个因子相同，计数为1个，因此d(n)为奇数。
输入： n。
输出： 最后门锁开的房间号。

1.for i=1 to n do

2.if (i*i<=n) print i*i


算法的时间复杂度为O(n)。
本节思考题
划分问题： n个大小不等的圆饼，分给m个人。要求每个人分得的大小相等，每个人只能有一块。那么最大的分隔方案是什么?


视频讲解




5.2倒推算法
5.2.1倒推与应用

正推是从小规模问题推解出大规模问题的方法。倒推是从后向前推解问题的方法，是对某些特殊问题所采用的违反通常习惯的方法。倒推一般使用情况如下。
(1)  不知前提条件时，从后向前递推，从而求解问题。即由结果倒过来推解它的前提条件。
(2) 由于存储的要求，必须从后向前进行推算。
(3) 一些问题从前向后分析问题比较棘手，而采用倒推则容易理解和解决。
例6： 猴子偷桃。一只小猴子摘了若干桃子，每天吃现有桃子的一半多1个，到第10天时就只有1个桃子了，求原有多少个桃子？
问题分析： 第10天剩余1个桃子，第9天的桃子数=2(1+1)=4，第8天的桃子数=2(4+1)=10，……
设第i天的桃子数为F［i］，则有F［i］=2(F［i+1］+1)，F［10］=1，i=9,8,…,1。 
猴子偷桃的递推算法： 

1.s=1

2.for i=9 to 1 do

3.s=(s+1)*2

4.return s


例7： 输出如图52(a)所示的杨辉三角形(限定用1个一维数组)。


图52杨辉三角形


问题分析： 上下行规律明显，中间的数等于上行左上、右上两数之和。如果使用二维数组存储，对于第i行，A［i,1］=A［i,i］=1，A［i,j］=A［i-1,j］+A［i-1,j-1］，如图52(b)所示。
题目中要求用1个一维数组完成。若求n层，则数组最多存储n个数据。对于第i行，A［1］=1，A［i］=1，A［j］=A［j］+A［j-1］。如果从左到右计算，A［i,j］=A［i-1,j］+A［i-1,j-1］中的A［i-1,j-1］已经变为A［i,j-1］，等式不一定成立。如果从右向左计算，A［i,j］=A［i-1,j］+A［i-1,j-1］中的A［i-1,j］和A［i-1,j-1］没有发生变化，等式仍然成立。
依照上面分析，采取从右向左计算，计算公式为A［1］=1，A［i］=1，A［j］=A［j］+A［j-1］。
杨辉三角递推算法： 

1.print("1")

2.print("＼n")

3.a［1］=a［2］=1

4.print(a［1］,a［2］)  

5.print("＼n")

6.for i=3 to n do

7.a［1］=a［i］=1

8.for j=i-1 to 2 do 

9.a［j］=a［j］+a［j-1］

10.for j=1 to i do

11.print(a［j］)

12.print("＼n")


例8： 穿越沙漠。用一辆吉普车穿越1000千米的沙漠。吉普车的总装油量为500加仑，耗油率为1加仑/千米。沙漠中没有油库，必须先用这辆车在沙漠中建立临时油库。该吉普车以最少的耗油量穿越沙漠，应在什么地方建油库，各油库的储油量是多少？
问题分析： 问题要求以最少的耗油量穿越沙漠，那么到达终点时，沙漠中的各临时油库和车的装油量均为0加仑。这样只能从终点开始向前倒推储油点和储油量。设下一个油库距离为x千米，运油次数为y。
最后一段长度为500千米且最后一个加油点储油为500加仑。
倒数第二段中为了储备油，吉普车在这段的行程必须有来回。
(1) 首先不计方向，这段应走奇数次(保证最后向前走)，即2y-1次，相应的消耗油量为(2y-1)x加仑。
(2) 每次向前行进时吉普车是满载，即500y加仑。
(3) 储存够下一个加油点500加仑油量。
根据上述分析有500y=500+(2y-1)x，则 ymin=2，x=500(y-1)/(2y-1)=500/3，储油500y=1000。
同样，倒数第三段有500y=1000+(2y-1)x，则 ymin=3，x=500(y-2)/(2y-1)=500/5，储油500y=1500。
因此从终点倒推起点，倒数第一个油库距离终点为500千米，储油量为500加仑。设倒数第k个油库距离上一个油库的距离为x千米，运油次数为y。根据上述分析有x=500/(2k-1)千米，储油量为500k加仑。
穿越沙漠递推算法： 

1.dis=500  

2.oil=500

3.k=1  

4.do

5.print(k,1000dis,oil)

6.k=k+1

7.dis=dis+500/(2k-1)

8.oil=500k

9.while (dis < 1000)

10.oil=500(k-1)+(1000-dis)(2k-1) //第一个储油点

11.print(k,0，oil)


5.2.2约瑟夫问题
n个人围成一圈，从第一个人开始顺序报数，报数m的将被杀掉，最后剩下一个人胜出。例如n=6，m=5，被杀掉的顺序是： 5、4、6、2、3，1胜出。
问题分析： n个人(编号0~n-1)，从0开始报数，报到m-1的退出，剩下的人继续从0开始报数。
第1个出局的人编号： m-1。
剩余人员： mm+1…n-101…m-2
剩余人员报数： 01…n-1-mn-mn-m+1…
第2个出局人报数m-1，原编号是 (m-1+m)%n。
设F［i］表示i个人游戏报数m时最后胜利者的编号，则有F(1)=0。根据上述分析，有F(i)=(F(i-1)+m)%i，F(n)=(F(n-1)+m)%n。
约瑟夫递推算法： 
输入： n，m。
输出： 胜利者编号。

1.f=0

2.for i=2 to  n do

3.f=(f+m) % i

4.print f+1


本节思考题
1. 约瑟夫问题： 一个监狱有k个好人和k个坏人。监狱长接到命令，杀掉k个人。监狱长比较正义，想杀掉k个坏人，留下k个好人。 他让k个好人和k个坏人顺序围成一圈，从第一个人开始顺序报数，报数m的将被杀掉，最后剩下k个好人，最小的m是多少？
2. NIM游戏： 有一堆石子和两个玩家。每个玩家每次可以从该堆剩余石子中拿走至少1个、至多m个石子。拿走最后一个剩余石子者获胜。获胜策略是什么？
如果有n堆石子，给定每堆石子数和两个玩家。每个玩家每次可以从任意一堆石子中拿走任意数量的石子(最少一个，最多整堆石子)，每次拿的石子数可以不同。拿走最后一个剩余石子者获胜。获胜策略是什么？
如果NIM游戏中，每次最多只能取k个，怎么处理?


视频讲解



5.3递推求解
5.3.1快速排序

C.A.R.Hoare于1962年提出快速排序并于1980年获得图灵奖。快速排序算法思想如下： 选择一个基准数，通过一次排序将要排序的数据分割成独立的两部分； 其中一部分的所有数据都比另外一部分的所有数据小。然后，再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
快速排序算法： 
输入： 数组A。
输出： 数组A，使i<j时 ai≤aj，1≤i<j≤n。


Call quickSort(A,1,n)

quickSort(A,p,r) {

1.if (p < r) then 

2.q=partion(A,p,r)

3.quickSort(A,p,q-1)

4.quickSort(A,q+1,r)

5.}

partion(A,p,r) {

1.x=A［p］

2.i=p

3.j=r+1

4.while(true) do

5.repeat j=j-1until A［j］ <= x

6.repeat i=i+1until A［i］ > x

7.if (i < j) then Swap(A［i］，A［j］)

8.else Swap(A［j］,A［p］)break

9.return j

10}


partion(A,p,r) 的操作过程如表54所示。


表54partion操作示例



675258初始序列
675258j=j-1
675258i=i+1
655278交换
655278j=j-1
655278i=i+1
255678交换并划分

j=j-1和i=i+1的操作次数不超过数组长度，因此划分操作的时间复杂度为O(n)。记录的比较和交换是从两端向中间进行的，关键字较大的记录一次就能交换到后面单元，关键字较小的记录一次只能交换到前面单元，记录每次移动的距离较大，因而总的比较和移动次数较少。
设快速排序的时间复杂度是T(n)。当n=1时，T(1)=0。partion(A,1,n)划分成的2个子数组大小不一，影响快速排序的时间复杂度。
最坏情况下，序列已经排好序，partion操作后分成的两个子数组，一个为空，一个有n-1个元素，则T(n)=T(0)+T(n-1)+n-1。
最好情况下，划分的两个子数组包含的元素数相等，则T(n)=2T(n/2)+n-1。
平均情况下，假设划分的子数组长度的概率相同，则


T(n)=T(0)+T(n-1)+T(1)+T(n-2)+…+T(n-1)+T(0)n+n-1

=2(T(0)+T(1)+…+T(n-1))n+n-1

=2n∑n-1i=1T(i)+n-1
5.3.2递推方程求解
递推方程求解的常用方法有： 迭代法、递归树、归纳法和主定理法。
1. 迭代法 
迭代法又分为直接迭代、差消迭代和换元迭代。
(1) 直接迭代： 直接迭代从原始递推方程出发，反复将对应方程左边的函数用右边等式代入，直至得到初值，然后将所得的结果化简。
最坏情况下，快速排序的时间复杂度为T(n)=T(n-1)+n-1，T(1)=0。则有T(n-1)=T(n-2)+n-2，代入原式，有

T(n)=T(n-1)+n-1

=［T(n-2)+n-2］+n-1

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

=［T(n-3)+n-3］+(n-2)+(n-1)

…

=T(1)+1+2+…+(n-2)+(n-1)

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

=n(n-1)2

为保证正确性，需要代入递推方程验证。
当n=1时，T(1)=1×(1-1)/2=0成立。假设n=k时,T(k)=k(k-1)/2成立，则当n=k+1时，有T(k+1)=T(k)+k=k(k-1)/2+k=k(k+1)/2，故公式成立。
(2) 差消迭代： 迭代一般用于一阶递推方程，高阶方程需要使用差消法化简为一阶方程求解。
平均情况下，快速排序的时间复杂度为


T(n)=2n∑n-1I=1T(i)+n-1,T(1)=0
则有


nT(n)=2∑n-1i=1T(i)+n2-n，(n-1)T(n-1)=2∑n-2i=1T(i)+(n-1)2-(n-1)

两边加2T(n-1)，得


(n+1)T(n-1)=2∑n-2i=1T(i)+2T(n-1)+(n-1)2-(n-1)

=2∑n-1i=1T(i)+(n-1)2-(n-1)

nT(n)=2∑n-1i=1T(i)+n2-n

=(n+1)T(n-1)-(n-1)2+(n-1)+n2-n

=(n+1)T(n-1)+2n-2
等式两边均除以n(n+1)，得


T(n)n+1=T(n-1)n+2n-2n(n+1)=…=21n+1+1n+…+13+T(1)2-1-O1n

=θ(logn)
所以，T(n)=Θ(nlogn)。
(3) 换元迭代： 将n的递推式换成其他变元k的递推式，对k直接迭代，最后将解变换为n的函数。
最好情况下，快速排序的时间复杂度为T(n)=2T(n/2)+n-1，T(1)=0。
假设n=2k，则k=logn，代入上式有T(2k)=2T(2k-1)+2k-1，T(2k-1)=2T(2k-2)+2k-1-1。


T(2k)=2T(2k-1)+2k-1

=2［2T(2k-2)+2k-1-1］+2k-1

=22T(2k-2)+2(2k)-2-1

=23T(2k-3)+3(2k)-22-2-1

…

=2kT(20)+k(2k)-2k-1-…-22-2-1

=k(2k)-2k
所以T(n)=nlogn-n=Θ(nlogn)。
2. 递归树
最好情况下，快速排序的时间复杂度为T(n)=2T(n/2)+O(n)，T(1)=0。其中，O(n)为长度为n的数组划分为2个n/2个元素的数组的时间复杂度。
使用递归树表示，如图53所示，节点是划分的子问题。右边是分解和合并的代价=每层子问题数×(分解和合并该层一个子问题的代价)。


图53快速排序的递归树表示


根据公式T(n)=2T(n/2)+O(n)，有T(n/2)=2T(n/4)+O(n/2)，T(n/4)=2T(n/8)+O(n/4)，…，T(2)=2T(1)+O(2)。如图53所示，T(2)层一共有n/2组，每组划分的时间复杂度为2，因此该层划分的时间为2(n/2)=n。T(n/2)层一共有2组，每组划分的时间复杂度为n/2，因此该层划分的时间同样为2(n/2)=n。T(n)层一共有1组，划分的时间复杂度为n，因此该层划分的时间同样为n。设n=2x，则x=logn。递归树一共有x层，每次划分的时间为n，因此总的时间复杂度为nx=nlogn。
递归树法求解过程使用部分近似，如n=2x，为保证正确性，需要代入递推方程进行验证。
当n=1时，T(1)=log1=0成立。假设n=k时，T(k)=klog2k成立，则当n=2k时，有T(2k)=2T(k)+2k=2klog2k+2k=2k(log2k+1)=2klog2k，故公式成立。
3. 归纳法
最好情况下，快速排序的时间复杂度为T(n)=2T(n/2)+O(n)，T(1)=0。使用归纳法证明T(n)=n log2n。
证明： 
当n=1时，T(1)=1×log21=0成立。假定n=k时，T(k)=klog2k成立，则当n=2k时，有T(2k)=2T(k)+2k=2klog2(k)+2k=2k［log2(2k)-1］+2k=2klog2(2k),故公式成立。
4. 主定理法
设a≥1，b>1为常数，f(n)为函数，T(n)为非负整数，且T(n)=aT(n/b)+f(n)，则有


T(n)=Θ(nlogba)ε，使f(n)=O(nlogba-ε)

Θ(nlogbalogn)f(n)=Θ(nlogba)

Θ(f(n))ε，使f(n)=Ω(nlogba+ε),且常数c和充分大的n，

使af(n/b)≤cf(n)ε>0
c<1

例9：  T(n)=9T(n/3)+n。
nlogba=nlog39=n2，f(n)=n=n2-ε=O(nlogba-ε)。依据主定理，有T(n)=Θ(n2)。
例10：  T(n)=T(2n/3)+1。
nlogba=nlog3/21=n0=1，f(n)=1=θ(nlogba)。依据主定理，有T(n)=Θ(logn)。
例11：  T(n)=3T(n/4)+nlogn。
nlogba=nlog43=n0.793，f(n)=nlogn，f(n)=Ω(nlogba+ε)。
又af(n/b)=3f(n/4)=（3nlog(n/4)）/4=（3n(logn-2)）/4<cnlogn，3/4≤c<1。依据主定理，T(n)=Θ(nlogn)。
例12： T(n)=2T(n/2)+nlogn。
nlogba=nlog22=n，f(n)=nlogn，不存在ε，使f(n)=Ω(nlogba+ε)。
又不存在c<1，使2f(n/2)=2(n/2)log(n/2)=n(logn-1)<cnlogn，因此不能使用主定理。
使用迭代求解，有


T(n)=2T(n/2)+nlogn

=2［2T(n/4)+(n/2)(logn/2)］+nlogn

=22T(n/4)+n(logn-1)+nlogn

…

=2kT(n/2k)+n(logn-k)+…+n(logn-1)+nlogn

设n=2k，则T(n)=n(k+1)logn-（k(k+1)）/2=n(logn+1)logn-（logn(logn+1)）/2=O(nlog2n)。
主定理推导过程如下。
T(n)=aT(n/b)+f(n)则T(n/b)=aT(n/b2)+f(n/b)，T(n/b2)=aT(n/b3)+f(n/b2)，故有


T(n)=aTnb+f(n)=a2Tnb2+afnb+f(n)

=a3Tnb3+a2fnb2+afnb+f(n)

设n=bx，则x=logbn，又ax=alogbn=nlogba，因此有


T(n)=aTnb+f(n)=…=axTnbx+ax-1fnbx-1+…+afnb+f(n)

=axTnbx+∑x-1j=0ajfnbj

=nlogba+∑logbn-1j=0ajfnbj

(1) 若f(n)=O(nlogba-ε)，则

fnbj=Onbjlogba-ε

∑logbn-1j=0ajfnbj=O∑logbn-1j=0ajnbjlogba-ε=Onlogba-ε∑logbn-1j=0abεblogbaj

=Onlogba-ε∑logbn-1j=0(bε)j=Onlogba-εbεlogbn-1bε-1=Onlogba-εnε-1bε-1

=O(nlogba-ε(nε))=O(nlogba)

因此，ε>0,若f(n)=O(nlogba-ε)，则T(n)=nlogba+∑logbn-1j=0ajf(n/bj)=Θ(nlogba)。
(2) 若f(n)=Θ(nlogba)，则

fnbj=Θnbjlogba

∑logbn-1j=0ajfnbj=Θ∑logbn-1j=0ajnbjlogba=Θnlogba∑logbn-1j=0ablogbaj

=Θnlogba∑logbn-1j=0(1)j=Θ(nlogba(logbn))

因此，若f(n)=Θ(nlogba-ε)，则T(n)=nlogba+∑logbn-1j=0ajf(n/bj)=Θ(nlogbalogn)。
(3) 若f(n)=(nlogba+ε)，c<1。则有


afnb≤cf(n),fnb≤caf(n),fnbj≤cajf(n)

∑logbn-1j=0ajfnbj≤∑logbn-1j=0ajcajf(n)+O(1)≤∑logbn-1j=0(c)jf(n)+O(1)

=f(n)1-c+O(1)=Θ(f(n))

因此，ε>0,c<1，若f(n)=Ω(nlogba+ε)，则T(n)=nlogba+∑logbn-1j=0ajf(n/bj)=Θ(f(n))。
本节思考题
1. 设算法A的时间复杂度递推方程为T(n)=7T(n/2)+n2，算法B的时间复杂度递推方程为T(n)=λT(n/4)+n2，确定最大的正整数λ，使算法B的阶不高于A的阶。
2. 设原问题的规模为n，从下面算法中选择复杂度最低的算法，并简要说明原因。
算法A： 将原问题划分为规模减半的5个子问题，递归求解每个子问题，然后在线性时间内合并子问题的解并得到原问题的解。
算法B： 先递归求解两个规模为n-1的子问题，然后在常量时间内将子问题的解合并得到原问题的解。
算法C： 将原问题划分为规模为n/3的9个子问题，递归求解每个子问题，然后在O(n3)时间内将子问题的解合并得到原问题的解。
本章习题
1. 编程实现划分问题算法(POJ 3122、POJ 1664)。
2. 编程实现递推算法(POJ 1942)。
3. 编程实现递归算法(POJ 2083)。
4. 编程实现约瑟夫问题算法(POJ 2244、POJ 3517)。
5. 编程实现快速排序算法(POJ 2388、POJ 2263、 POJ 1974)。
6. 编程实现线性方程组算法(POJ 2345)。
7. 编程实现牛顿迭代解方程算法(POJ 3111)。
8. 编程实现石子游戏算法(POJ 1067、POJ 3688)。
9. 简述递推方程的求解方法。
10. 简述递推与递归、循环的关系。
11. 求解下列递推方程。
(1) T(n)=T(n-1)+n2

T(1)=1。
(2) T(n)=8T(n/2)+n2

T(1)=1。
(3) T(n)=T(n/2)+T(n/4)+n

T(1)=1。
(4) T(n)=T(n/2)+log3n

T(1)=1。
(5) T(n)=2T(n/2)+n2logn

T(1)=1。
(6) T(n)=T(n-1)+1/n

T(1)=1。

12. 一群猴子编号是1，2，3，…，m，这群猴子按照1~m的顺序围坐一圈，从第1开始数，每数到第n个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。大王的编号是多少？
13. 集合划分问题： 给定正整数n(1≤n≤20)，计算出n个元素的集合{1,2,…,n}可以化为多少个不同的非空子集。
14. 集合划分问题： 给定正整数n 和m，计算出n 个元素的集合{1,2,…,n}可以划分为多少个不同的由m 个非空子集组成的集合。
15. 给定n个物品的重量，给定常数k，编写算法，选择部分物品，使其重量之和正好等于k。
16. 请给出汉诺塔问题的递推公式和时间复杂度、汉诺塔问题递归与非递归算法。
17. 冯·诺依曼邻居问题： 从1×1的方格开始，每次在上次图形周围增加一圈方格，第1次只有1个方格，第2次增加4个方格，第3次增加8个方格,……，第n次生成多少方格？请给出递推关系和时间复杂度。