第3章〓必备技能——基本算法设计方法




















为了设计出解决问题的好算法，除了需要掌握常用的数据结构工具以外，还需要掌握算法设计方法，算法设计与分析课程主要讨论分治法、回溯法、分支限界法、贪心法和动态规划，称为五大算法策略，在学习这些算法策略之前读者必须具有一定的算法设计基础，本章讨论穷举法、归纳法、迭代法和递归法等基本算法设计方法及其递推式的计算。本章的学习要点和学习目标如下： 

(1) 掌握穷举法的原理和穷举法算法的框架。

(2) 掌握归纳法的原理和从求解问题找出递推关系的方法。

(3) 掌握迭代法的原理和实现迭代法算法的方法。

(4) 掌握递归法的原理和实现递归法算法的方法。

(5) 掌握递推式的各种计算方法。

(6) 综合运用穷举法、归纳法、迭代法和递归法解决一些复杂的实际问题。


3．1穷举法
3．1．1穷举法概述

1. 什么是穷举法
穷举法又称枚举法或者列举法，是一种简单、直接地解决问题的方法。其基本思想是先确定有哪些穷举对象和穷举对象的顺序，按穷举对象的顺序逐一列举每个穷举对象的所有情况，再根据问题提出的约束条件检验哪些是问题的解，哪些应予排除。

在用穷举法解题时，针对穷举对象的数据类型和解的特性可以采用不同的列举方法，常用以下几种列举方法。

① 顺序列举： 指答案范围内的各种情况很容易与自然数对应甚至就是自然数，可以按自然数的变化顺序去列举。

② 排列列举： 有时答案的数据形式是一组数的排列，列举出所有答案所在范围内的排列为排列列举。排列中的元素是有顺序的。

③ 组合列举： 当答案的数据形式为一些元素的组合时往往需要用组合列举。组合中的元素是无顺序的。

穷举法的主要作用如下。

① 从理论上讲穷举法可以解决可计算领域中的各种问题，尤其是处在计算机的计算速度非常高的今天，穷举法的应用领域是非常广阔的。 

② 在实际应用中通常要解决的问题的规模不大，用穷举法设计的算法的运算速度是可以接受的，此时设计一个更高效率的算法不值得。 

③ 穷举法算法一般逻辑清晰，编写的程序简洁明了。

④ 穷举法算法一般不需要特别证明算法的正确性。

⑤ 穷举法可以作为某类问题时间性能的底线，用来衡量同样问题的更高效率的算法。

穷举法的缺点主要是设计的大多数算法的效率都不高，主要适合规模比较小的问题的求解，为此在采用穷举法求解时应根据问题的具体情况进行分析和归纳，寻找简化规律，精简穷举循环，优化穷举策略，以提高算法性能。

2. 穷举法算法的框架
穷举法算法一般使用循环语句和选择语句实现，其中循环语句用于枚举穷举对象的所有可能的情况，而选择语句判断当前的条件是否为所求的解。其基本流程如下。

① 根据问题的具体情况确定穷举变量(简单变量或数组)。

② 根据确定的范围设置穷举循环。

③ 根据问题的具体要求确定解满足的约束条件。

④ 设计穷举法算法，编写相应的程序，执行和调试穷举法程序，对执行结果进行分析与讨论。

假设某个问题的穷举变量是x和y，穷举顺序是先x后y，均为顺序列举，它们的取值范围分别是x∈(x1，x2，…，xn)，y∈(y1，y2，…，ym)，约束条件为p(xi，yj)，对应的穷举法算法的基本框架如下： 


def Exhaustive(x,n,y,m):							#穷举法算法的框架

for i in range(1,n+1):							#枚举x的所有可能的值

for j in range(1,m+1):						#枚举y的所有可能的值

…

if p(x［i］,y［j］):#检测约束条件是否成立

…



从中看出，x和y的所有可能的搜索范围是笛卡儿积，即(［x1，y1］，［x1，y2］，…，［x1，ym］，…，［xn，y1］，［xn，y2］，…，［xn，ym］)，这样的搜索范围可以用一棵树表示，称为解空间树，它包含求解问题的所有解，求解过程就是在整个解空间树中搜索满足约束条件p(xi，yj)的解，可能解对应于某些叶子结点。在第5章中将更详细地讨论解空间树的相关概念。


扫一扫



视频讲解


【例31】鸡兔同笼问题。现有一个笼子，里面有鸡和兔若干只，数一数共有a个头、b条腿，设计一个算法求鸡和兔各有多少只？


解由于有鸡和兔两种动物，每只鸡有两条腿，每只兔有4条腿，设置两个循环变量，x表示鸡的只数，y表示兔的只数，那么穷举对象就是x和y，假设穷举对象的顺序是先x后y(在本问题中也可以是先y后x)。

显然，x和y的取值范围都是0~a，约束条件p(x，y)为(x+y==b)和(2x+4y=b)。以a=3、b=8为例，对应的解空间树如图3．1所示，根结点的分支对应x的各种取值，第二层结点的分支为y的各种取值，其中“×”结点是不满足约束条件的结点，带阴影的结点是满足约束条件的结点，所以结果是x=2，y=1。对应的算法如下： 


1def solve1(a,b):

2for x in range(0,a+1):

3for y in range(0,a+1):

4if x+y==a and 2*x+4*y==b:

5print("x=%d,y=%d"%(x,y))






图3．1a=3、b=8的解空间树


从图3．1看到，解空间树中共有21个结点，显然结点个数越多时间性能越差，可以稍做优化，鸡的只数最多为min(a，b/2)，兔的只数最多为min(a，b/4)，仍以a=3、b=8为例，x的取值范围是0~3，y的取值范围是0~2。对应的解空间树如图3．2所示，共17个结点。



图3．2a=3、b=8的优化解空间树


对应的优化算法如下： 


1def solve2(a,b):

2for x in range(0,min(a,b//2)+1):

3for y in range(0,min(a,b//4)+1):

4if x+y==a and 2*x+4*y==b:

5print("x=%d,y=%d"%(x,y))



所以尽管穷举法算法通常性能较差，但能够以它为基础进行优化继而得到高性能的算法，优化的关键是可以找出求解问题的优化点，不同的问题的优化点是不同的，这就需要大家通过大量实训掌握一些基本算法设计技巧。后面通过两个应用讨论穷举法算法的设计方法，以及穷举法算法的优化过程。


扫一扫



视频讲解


3．1．2最大连续子序列和

1. 问题描述

给定一个含n(n≥1)个整数的序列，要求求出其中最大连续子序列的和。例如序列(-2，11，-4，13，-5，-2)的最大连续子序列和为20，序列(-6，2，4，-7，5，3，2，-1，6，-9，10，-2)的最大连续子序列和为16。规定一个序列的最大连续子序列和至少是0，如果小于0，其结果为0。

2. 问题求解1
设有含n个整数的序列a［0．．n-1］，其连续子序列为a［i．．j］(i≤j，0≤i≤n-1，i≤j≤n-1)，求出它的所有元素之和cursum，并通过比较将最大值存放到maxsum中，最后返回maxsum。这种解法是穷举所有连续子序列(一个连续子序列由起始下标i和终止下标j确定)，是典型的穷举法思想。

例如，对于a［0．．5］={-2，11，-4，13，-5，-2}，求出的a［i．．j］(0≤i≤j≤5)的所有元素和如图3．3所示(行号为i，列号为j)，其过程如下： 

(1) i=0，依次求出j=0，1，2，3，4，5的子序列和分别为-2、9、5、18、13、11。

(2) i=1，依次求出j=1，2，3，4，5的子序列和分别为11、7、20、15、13。

(3) i=2，依次求出j=2，3，4，5的子序列和分别为-4、9、4、2。

(4) i=3，依次求出j=3，4，5的子序列和分别为13、8、6。

(5) i=4，依次求出j=4，5的子序列和分别为-5、-7。

(6) i=5，求出j=5的子序列和为-2。

其中20是最大值，即最大连续子序列和为20。



图3．3a［i．．j］(0≤i≤j≤5)的所有元素和


对应的算法如下： 


1def maxSubSum1(a):								#解法1

2n,maxsum=len(a),0

3for i in range(0,n):								#用三重循环穷举所有的连续子序列

4for j in range(i,n):

5cursum=0

6for k in range(i,j+1):cursum+=a［k］

7maxsum=max(maxsum,cursum)	#通过比较求最大maxsum

8return maxsum



【算法分析】在maxSubSum1(a)算法中用了三重循环，所以有： 
T(n)=∑n-1i=0∑n-1j=i∑jk=i1=∑n-1i=0∑n-1j=i(j-i+1)=12∑n-1i=0(n-i)(n-i+1)=O(n3)
3. 问题求解2
采用前缀和方法，用presum［i］表示子序列a［0．．i-1］的元素和，即a中前i个元素的和，显然有如下递推关系： 

presum［0］=0

presum［i］=presum［i-1］+a［i-1］当i>0时

假设j≥i，则有： 

presum［i］=a［0］+a［1］+…+a［i-1］

presum［j］=a［0］+a［1］+…+a［i-1］+a［i］+…+a［j-1］

两式相减得到presum［j］-presum［i］=a［i］ +…+a［j-1］，这样i从0到n-1、j-1从i到n-1(即j从i+1到n)循环可以求出所有连续子序列a［i．．j］之和，通过比较求出最大maxsum即可。对应的算法如下： 


1def maxSubSum2(a):							#解法2

2n=len(a)

3presum=［0］*(n+1)

4presum［0］=0

5for i in range(1,n+1):





6presum［i］=presum［i-1］+a［i-1］

7maxsum=0

8for i in range(0,n):

9for j in range(i+1,n+1):

10cursum=presum［j］-presum［i］

11maxsum=max(maxsum,cursum)#通过比较求最大maxsum

12return maxsum



【算法分析】在maxSubSum2(a)算法中主要用了两重循环，所以有： 
T(n)=∑n-1i=0∑nj=i+11=∑n-1i=0(n-i)=n(n+1)2=O(n2)

4. 问题求解3
对前面的解法1进行优化。当i取某个起始下标时，依次求j=i，i+1，…，n-1对应的子序列和，实际上这些子序列是相关的。用Sum(a［i．．j］)表示子序列a［i．．j］的元素和，显然有如下递推关系： 

Sum(a［i．．j］)=0当j<i时

Sum(a［i．．j］)=Sum(a［i．．j-1］)+a［j］当j≥i时

这样在连续求以a［i］开始的a［i．．j］子序列和(j=i，i+1，…，n-1)时没有必要使用循环变量为k的第3重循环，优化后的算法如下： 


1def maxSubSum3(a):							#解法3

2n,maxsum=len(a),0

3for i in range(0,n):

4cursum=0

5for j in range(i,n):

6cursum+=a［j］

7maxsum=max(maxsum,cursum)#通过比较求最大maxsum

8return maxsum



【算法分析】在maxSubSum3(a)算法中只有两重循环，所以有： 
T(n)=∑n-1i=0∑n-1j=i1=∑n-1i=0(n-i)=n(n+1)2=O(n2)

5. 问题求解4
对前面的解法3继续优化。将maxsum和cursum初始化为0，用i遍历a，置cursum+=a［i］，也就是说cursum累计到a［i］时的元素和，分为两种情况： 

① 若cursum≥maxsum，说明cursum是一个更大的连续子序列和，将其存放到maxsum中，即置maxsum=cursum。

② 若cursum<0，说明cursum不可能是一个更大的连续子序列和，从下一个i开始继续遍历，所以置cursum=0。

在上述过程中先置cursum+=a［i］，后判断cursum的两种情况。在a遍历完后返回maxsum即可。对应的算法如下： 


1def maxSubSum4(a):						#解法4

2n,maxsum,cursum=len(a),0,0





3for i in range(0,n):

4cursum+=a［i］

5maxsum=max(maxsum,cursum)#通过比较求最大maxsum

6if cursum<0:cursum=0        #若cursum<0，最大连续子序列从下一个位置开始

7return maxsum



【算法分析】在maxSubSum4(a)算法中只有一重循环，所以时间复杂度为O(n)。

从中看出，尽管仍采用穷举法思路，但可以通过各种优化手段降低算法的时间复杂度。解法2的优化点是采用前缀和数组，解法3的优化点是找出a［i．．j-1］和a［i．．j］子序列的相关性，解法4的优化点是进一步判断cursum的两种情况。

思考题： 对于给定的整数序列a，不仅要求出其中最大连续子序列的和，还需要求出这个具有最大连续子序列和的子序列(给出其起始和终止下标)，如果有多个具有最大连续子序列和的子序列，求其中任意一个子序列。

3．1．3实战——最大子序列和(LeetCode53★)

1. 问题描述

扫一扫



视频讲解


给定一个含n(1≤n≤105)个整数的数组 nums，设计一个算法找到一个具有最大和的连续子数组(子数组中至少包含一个元素)，返回其最大和。例如，nums={-2，1，-3，4，-1，2，1，-5，4}，答案为6，对应的连续子数组是{4，-1，2，1}。

2. 问题求解
本题是求nums的最大连续子序列和，但该序列中至少包含一个元素，也就是说最大连续子序列和可能为负数。例如nums={-1，-2}，结果为-2，因此需要在3．1．2节中解法4的基础上将答案maxsum初始化为nums［0］而不是0。对应的算法如下： 


1class Solution:

2def maxSubArray(self, nums: List［int］) > int:

3n,maxsum,cursum=len(nums),nums［0］,0

4for i in range(0,n):

5cursum+=nums［i］

6maxsum=max(maxsum,cursum)       	#通过比较求最大maxsum

7if cursum<0:cursum=0            	#若cursum<0，最大连续子序列从下一个位置开始

8return maxsum



上述程序提交时通过，运行时间为128ms，内存消耗为29．8MB。

3．2归纳法
3．2．1归纳法概述

1. 什么是数学归纳法
谈到归纳法，大家很容易会想到数学归纳法，数学归纳法是一种数学证明方法，用于确定一个表达式在所有自然数范围内是成立的，分为第一数学归纳法和第二数学归纳法两种。

第一数学归纳法的原理： 若{P(1)，P(2)，P(3)，P(4)，…}是命题序列且满足以下两个性质，则所有命题均为真。

① P(1)为真。

② 任何命题均可以从它的前一个命题推导得出。

例如，采用第一数学归纳法证明1+2+…+n=n(n+1)/2成立的过程如下： 

当n=1时，左式=1，右式=(1×2)/2=1，左、右两式相等，等式成立。

假设当n=k-1时等式成立，有1+2+…+(k-1)=k(k-1)/2。

当n=k时，左式=1+2+…+(k-1)+k=k(k-1)/2+k=k(k+1)/2，等式成立，问题即证。

第二数学归纳法的原理： 若{P(1)，P(2)，P(3)，P(4)，…}是满足以下两个性质的命题序列，则对于其他自然数，该命题序列均为真。

① P(1)为真。

② 任何命题均可以从它的前面所有命题推导得出。

用数学归纳法进行证明主要有两个步骤： 

① 证明当取第一个值时命题成立。

② 假设当前命题成立，证明后续命题也成立。

数学归纳法的独到之处是运用有限个步骤就能证明无限多个对象，而实现这一目的的工具就是递推思想。第①步是证明归纳基础成立，归纳基础成为后面递推的出发点，没有它递推成了无源之水； 第②步是证明归纳递推成立，借助该递推关系，命题成立的范围就能从开始向后面一个数一个数地无限传递到以后的每个正整数，从而完成证明，因此递推是实现从有限到无限飞跃的关键。

【例32】给定一棵非空二叉树，采用数学归纳法证明如果其中有n个叶子结点，则双分支结点的个数恰好为n-1，即P(n)=n-1。

证明： 当n=1时，这样的二叉树只有一个结点，该结点既是根结点又是叶子结点，没有分支结点，则P(1)=0成立。

假设叶子结点的个数为k-1时成立，即P(k-1)=(k-1)-1=k-2。由二叉树的结构可知，想要在当前的二叉树中增加一个叶子结点，对其中某种类型的结点的操作如下。

① 双分支结点： 无法增加孩子结点，不能达到目的。

② 单分支结点： 可以增加一个孩子结点(为叶子结点)，此时该单分支结点变为双分支结点，也就是说叶子结点和双分支结点均增加一个，这样P(k)=P(k-1)+1=k-2+1=k-1，结论成立。

③ 叶子结点： 增加一个孩子结点，总的叶子结点个数没有增加，不能达到目的。

④ 叶子结点： 增加两个孩子结点(均为叶子结点)，此时该叶子结点变为双分支结点。

也就是说叶子结点和双分支结点均增加一个，这样P(k)=P(k-1)+1=k-2+1=k-1，结论成立。从中看出凡是能够达到目的的操作都会使结论成立，因此根据第一数学归纳法的原理，问题即证。

2. 什么是归纳法
从广义上讲，归纳法是人们在认识事物的过程中所使用的一种思维方法，通过列举少量的特殊情况，经过分析和归纳推理寻找出基本规律。归纳法比枚举法更能反映问题的本质，但是从一个实际问题中总结归纳出基本规律并不是一件容易的事情，而且归纳过程通常也没有一定的规则可以遵循。归纳法包含不完全归纳法和完全归纳法，不完全归纳法是根据事物的部分特殊事例得出一般结论的推理方法，即从特殊出发，通过实验、观察、分析、综合和抽象概括出一般性结论的一种重要方法。完全归纳法是根据事物的所有特殊事例得出一般结论的推理方法。

在算法设计中归纳法常用于建立数学模型，通过归纳推理得到求解问题的递推关系，也就是采用递推关系表达寻找出的基本规律，从而将复杂的运算化解为若干重复的简单运算，以充分发挥计算机擅长重复处理的特点。在应用归纳法时一般用n表示问题的规模(n为自然数)，并且具有这样的递推性质——能从已求得的问题规模为1~n-1或者n/2等的一系列解构造出问题规模为n的解，前者均称为“小问题”，后者称为“大问题”，而大、小问题的解法相似，只是问题规模不同。利用归纳法产生递推关系的基本流程如下。

① 按推导问题的方向研究最初、最原始的若干问题。

② 按推导问题的方向寻求问题间的转换规律，即递推关系，使问题逐渐转化成较低层级或简单的且能解决的问题或已解决的问题。



图3．4顺推法和逆推法

根据推导问题的方向分为顺推法和逆推法两种。所谓顺推法是从已知条件出发逐步推算出要解决问题的结果，如图3．4(a)所示。所谓逆推法是从已知问题的结果出发逐步推算出问题的开始条件，如图3．4(b)所示。

前面讨论的数学归纳法和归纳法有什么关系呢？数学归纳法虽然不是归纳法，但是它与归纳法有着一定程度的关联，在结论的发现过程中往往先对大量个别事实进行观察，通过不完全归纳法归纳形成一般性结论，最终利用数学归纳法对结论的正确性予以证明。

3．2．2直接插入排序

1. 问题描述
有一个整数序列a［0．．n-1］，采用直接插入排序实现a的递增有序排序。直接插入排序的过程是i从1到n-1循环，每次循环时将a［i］有序插入a［0．．i-1］中。

2. 问题求解
采用不完全归纳法产生直接插入排序的递推关系。例如a=(2，5，4，1，3)，这里n=5，用［］表示有序区，各趟的排序结果如下。

初始： (［2］，5，4，1，3)

i=1： (［2，5］，4，1，3)

i=2： (［2，4，5］，1，3)

i=3： (［1，2，4，5］，3)

i=4： (［1，2，3，4，5］)

设f(a，i)用于实现a［0．．i］(共i+1个元素)的递增排序，它是一个大问题，则f(a，i-1)实现a［0．．i-1］(共i个元素)的排序，它是一个小问题。对应的递推关系如下： 


f(a，i) ≡ 不做任何事情当i=0时

f(a，i) ≡ f(a，i-1); 将a［i］有序插入a［0．．i-1］中其他

显然f(a，n-1)用于实现a［0．．n-1］的递增排序。这样采用不完全归纳法得到的结论(直接插入排序的递推关系)是否正确呢？采用数学归纳法证明如下： 

① 证明归纳基础成立。当n=1时直接返回，由于此时a中只有一个元素，它是递增有序的，所以结论成立。

② 证明归纳递推成立。假设n=k时成立，也就是说f(a，k-1)用于实现a［0．．k-1］的递增排序。当n=k+1时对应f(a，k)，先调用f(a，k-1)将a［0．．k-1］排序，再将a［k］有序插入a［0．．k-1］中，这样a［0．．k］变成递增有序序列，所以f(a，k)实现a［0．．k］的递增排序，结论成立。

根据第一数学归纳法的原理，问题即证。按照上述直接插入排序的递推关系得到对应的算法如下： 


1def Insert(a,i):        				#将a［i］有序插入a［0..i-1］中

2tmp=a［i］

3j=i-1

4while True:             		#找a［i］的插入位置

5a［j+1］=a［j］   					#将关键字大于a［i］的元素后移

6j-=1

7if not (j>=0 and a［j］>tmp):

8break           			#循环到a［j］<=tmp为止

9a［j+1］=tmp      					#在j+1处插入a［i］

10

11def InsertSort1(a): 					#迭代算法：直接插入排序

12n=len(a)

13for i in range(1,n):

14if a［i］<a［i-1］:Insert(a,i)  		#反序时调用Insert



在实际中有些采用不完全归纳法得到的结论明显是正确的，或者已经被人们证明是正确的，可以在算法设计中直接使用这些结论。

3．2．3实战——不同路径(LeetCode62★★)

1. 问题描述

扫一扫



视频讲解


一个机器人位于一个m×n(1≤m，n≤100)网格的左上角(起始点标记为“Start”)，机器人每次只能向下或者向右移动一步，设计一个算法求机器人到达网格的右下角(标记为“Finish”)共有多少条不同的路径。例如，m=3，n=3，对应的网格如图3．5所示，答案为6。



图3．53×3的网格

2. 问题求解
在从左上角到右下角的任意路径中，一定是向下走m-1步、向右走n-1步，不妨置x=m-1，y=n-1，路径长度为x+y。例如对于图3．5，这里x=2，y=2，所有路径长度为4，6条不同的路径如下： 

① 右右下下； 

② 右下右下； 

③ 右下下右； 

④ 下右右下； 

⑤ 下右下右； 

⑥ 下下右右。

归纳起来，不同路径条数等于从x+y个选择中挑选x个“下”或者y个“右”的组合数，即Cxx+y或者Cyx+y(实际上从数学上推导有Cxx+y=Cyx+y)，为了方便，假设x≤y，结果取Cxx+y。
Cxx+y=(x+y)!x!y!=(x+y)(x+y-1)…(y-1)y!x!y!=(x+y)×…×(y-1)x×(x-1)×…×2×1
在上式中分子、分母均为x个连乘，可以进一步转换为
x+yx×x+y-1x-1×…×y-11
由于除法的结果是实数，而不同的路径数一定是整数，所以最后需要将计算的结果四舍五入得到整数答案。对应的算法如下： 


1class Solution:

2def uniquePaths(self, m: int, n: int) > int:

3return self.comp(m-1,n-1)

4

5def comp(self,x,y):

6a,b=x+y,min(x,y)

7ans=1.0

8while b>0:

9ans*=1.0*a/b

10a-=1;b-=1

11return round(ans)



上述程序提交时通过，执行时间为40ms，内存消耗为14．9MB。

说明： 在求Cxx+y时，如果先计算(x+y)!，再计算x!y!，最后求两者相除的结果，当x、y较大时会发生溢出。

3．2．4猴子摘桃子问题

1. 问题描述
猴子第1天摘下若干桃子，当即吃了一半又一个。第2天又把剩下的桃子吃了一半又一个，以后每天都吃前一天剩下的桃子的一半又一个，到第10天猴子想吃的时候只剩下一个桃子。求猴子第1天一共摘了多少个桃子。

2. 问题求解
采用归纳法中的逆推法。设f(i)表示第i天的桃子数，假设第n(题目中n=10)天只剩下一个桃子，即 f(n)=1。另外，题目中隐含了前一天的桃子数等于后一天桃子数加1的两倍： 

f(10)=1

f(9)=2(f(10)+1)

f(8)=2(f(9)+1)

…

即f(i)=2(f(i+1)+1)。这样得到递推关系如下： 


f(i)=1当i=n时

f(i)=2(f(i+1)+1)其他

其中f(i)是大问题，f(i+1)是小问题。最终结果是求f(1)。对应的算法如下： 


1def peaches(n):			#第n天的桃子数为1，求第1天的桃子数

2ans=1

3for i in range(n-1,0,-1):

4ans=2*(ans+1)

5return ans



用上述算法求出f(1)为1534。

3．3迭代法
3．3．1迭代法概述

迭代法也称辗转法，是一种不断用变量的旧值推出新值的过程。通过让计算机对一组指令(或一定步骤)进行重复执行，在每次执行这组指令(或这些步骤)时都从变量的原值推出它的一个新值。

如果说归纳法是一种建立求解问题数学模型的方法，则迭代法是一种算法实现技术。一般先采用归纳法产生递推关系，在此基础上确定迭代变量，再对迭代过程进行控制，基本的迭代法算法框架如下： 


def Iterative():							#迭代法算法的框架

为迭代变量赋初值

while (迭代条件成立:

根据递推关系式由旧值计算出新值

新值取代旧值，为下一次迭代做准备）



实际上3．2节中所有的算法均是采用迭代法实现的。

如果一个算法已经采用迭代法实现，那么如何证明算法的正确性呢？由于迭代法算法包含循环，对循环的证明引入循环不变量的概念。所谓循环不变量，是指在每轮迭代开始前后要操作的数据必须保持的某种特性(例如在直接插入排序中，排序表的前面部分必须是有序的)。循环不变量是进行循环的必备条件，因为它保证了循环进行的有效性，有助于大家理解算法的正确性。如图3．6所示，对于循环不变量必须证明它的3个性质。

初始化： 在循环的第一轮迭代开始之前应该是正确的。

保持： 如果在循环的第一次迭代开始之前正确，那么在下一次迭代开始之前它也应该保持正确。

终止： 当循环结束时，循环不变量给了用户一个有用的性质，它有助于表明算法是正确的。



图3．6利用循环不变量证明算法的正确性


这里的推理与数学归纳法相似，在数学归纳法中要证明某一性质是成立的，必须首先证明归纳基础成立，这里就是证明循环不变量在第一轮迭代开始之前是成立的。证明循环不变量在各次迭代之间保持成立，类似于在数学归纳法中证明归纳递推成立。循环不变量的第三项性质必须成立，与数学归纳法不同，在归纳法中归纳步骤是无穷地使用，在循环结束时才终止“归纳”。

【例33】采用循环不变量证明3．2．2节中直接插入排序算法的正确性。

证明： 在直接插入排序算法中循环不变量为“a［0．．i-1］是递增有序的”。

初始化： 在循环时i从1开始，循环之前a［0．．0］中只有一个元素，显然是有序的，所以循环不变量在循环开始之前是成立的。

保持： 需要证明每一轮循环都能使循环不变量保持成立。对于a［i］排序的这一趟，之前a［0．．i-1］是递增有序的： 

① 如果a［i］≥a［i-1］，即正序，则该趟结束，结束后循环不变量a［0．．i］显然是递增有序的。

② 如果a［i］<a［i-1］，即反序，则在a［0．．i-1］中从后向前找到第一个a［j］≤a［i］，将a［j+1．．i-1］均后移一个位置，并且将原a［i］放在a［j+1］位置，这样结束后循环不变量a［0．．i］显然也是递增有序的。

终止： 循环结束时i=n，在循环不变量中用i替换n，就有a［0．．n-1］包含原来的全部元素，但现在已经排好序了，也就是说循环不变量也是成立的。

这样就证明了3.2.2节中直接插入排序算法的正确性。

后面的重点放在迭代法算法的设计上而不是算法的正确性证明上，通过几个经典应用予以讨论。

3．3．2简单选择排序

1. 问题描述
有一个整数序列a［0．．n-1］，采用简单选择排序实现a的递增有序排序。简单选择排序的过程是，i从0到n-2循环，a［0．．i-1］是有序区，a［i．．n-1］是无序区，并且前者的所有元素均小于或等于后者的任意元素，每次循环在a［i．．n-1］无序区采用简单比较找到最小元素a［minj］，通过交换将其放到a［i］位置。

2. 问题求解
采用不完全归纳法产生简单选择排序的递推关系。例如a=(2，5，4，1，3)，这里n=5，用［］表示有序区，各趟的排序结果如下。

初始： (［］2，5，4，1，3)

i=0： (［1］，5，4，2，3)

i=1： (［1，2］，4，5，3)

i=2： (［1，2，3］，5，4)

i=3： (［1，2，3，4］，5)

设f(a，i)用于实现a［i．．n-1］(共n-i个元素)的递增排序，它是一个大问题，则f(a，i-1) 实现a［i-1．．n-1］(共n-i-1个元素)的排序，它是一个小问题。对应的递推关系如下： 


f(a，i) ≡ 不做任何事情当i=n-1时

f(a，i) ≡ 在a［i．．n-1］中选择最小元素交换到a［i］位置； f(a，i+1)否则

显然f(a，0)用于实现a［0．．n-1］的递增排序。对应的算法如下： 


1def Select(a,i):								#一趟排序：在a［i..n-1］中选择最小元素交换到a［i］位置

2n,minj=len(a),i							#minj表示a［i..n-1］中最小元素的下标

3for j in range(i+1,n):					#在a［i..n-1］中找最小元素

4if a［j］<a［minj］:minj=j

5if minj!=i:									#若最小元素不是a［i］

6a［minj］,a［i］=a［i］,a［minj］			#交换

7

8def SelectSort1(a):							#迭代法：简单选择排序

9for i in range(0,len(a)):					#进行n-1趟排序

10Select(a,i)



3．3．3实战——多数元素(LeetCode169★)

1. 问题描述

扫一扫



视频讲解


见2．12．3节，这里采用迭代法求解。

2. 问题求解
依题意nums中一定存在多数元素。通过观察可以归纳出这样的结论，删除nums中任意两个不同的元素，则删除后多数元素依然存在且不变。假设nums中的多数元素为c，即c出现的次数cnt大于n/2，现在删除nums中任意两个不同的元素得到nums1(含n-2个元素)： 

① 若删除的两个元素均不是c，则c在nums1中出现的次数仍然为cnt，由于cnt>n/2>(n-2)/2，所以c是nums1中的多数元素。

② 若删除的两个元素中有一个是c，则c在nums1中出现的次数为cnt-1，由于(cnt-1)/(n-2)>(n/2-1)/(n-2)=1/2，也就是说c在nums1中出现的次数超过一半，所以c是nums1中的多数元素。

既然上述结论成立，设候选多数元素为c=nums［0］，计数器cnt表示c出现的次数(初始为1)，i从1开始遍历nums，若两个元素(nums［i］，c)相同，cnt增1，否则cnt减1，相当于删除这两个元素(nums［i］删除一次，c也只删除一次)，如果cnt为0，说明前面没有找到多数元素，从nums［i+1］开始重复查找，即重置c=nums［i+1］，cnt=1。遍历结束后c就是nums中的多数元素。对应的迭代算法如下： 


1class Solution:

2def majorityElement(self, nums: List［int］) > int:





3n=len(nums)

4if n==1:return nums［0］

5c,cnt=nums［0］,1

6i=1

7while i<n:

8if nums［i］==c:                   #选择两个元素(R［i］,c)

9cnt+=1                       	#相同时累加次数

10else:

11cnt-=1                  		#不相同时递减cnt，相当于删除这两个元素

12if cnt==0:            			#cnt为0时对剩余元素从头开始查找

13i+=1

14c=nums［i］;cnt+=1

15i+=1

16return c



上述程序提交时通过，运行时间为44ms，内存消耗为16．8MB。对应算法的时间复杂度为O(n)，空间复杂度为O(1)。


扫一扫



视频讲解


3．3．4求幂集

1. 问题描述

给定一个正整数n(n≥1)，给出求{1，2，…，n}的幂集的递推关系和迭代算法。例如，当n=3时，{1，2，3}的幂集合为{{}，{1}，{2}，{1，2}，{3}，{1，3}，{2，3}，{1，2，3}}(子集的顺序任意)。

2. 问题求解
以n=3为例，求{1，2，3}的幂集的过程如图3．7所示，其中M1、M2和M3分别表示{1}、{1，2}和{1，2，3}的幂集。



图3．7求{1，2，3}的幂集的过程


对应的步骤如下。

① {1}的幂集M1={{}，{1}}。

② 在M1的每个集合元素的末尾添加2得到A2={{2}，{1，2}}，将M1和A2的全部元素合并起来得到M2={{}，{1}，{2}，{1，2}}。

③ 在M2的每个集合元素的末尾添加3得到A3={{3}，{1，3}，{2，3}，{1，2，3}}，将M2和A3的全部元素合并起来得到M3={{}，{1}，{2}，{1，2}，{3}，{1，3}，{2，3}，{1，2，3}}。

归纳起来，设Mi表示{1，2，…，i}(i≥1，共i个元素)的幂集(是一个两层集合)，为大问题，则Mi-1为{1，2，…，i-1}(共i-1个元素)的幂集，为小问题，显然有M1={{}，{1}}。

考虑i>1的情况，假设Mi-1已经求出，定义运算appendi(Mi-1，i)返回在Mi-1中每个集合元素的末尾插入整数i的结果，即 
appendi(Mi-1,i)=∪s∈Mi-1append(s,i)
则

Mi=Mi-1∪Ai，其中Ai=appendi(Mi-1，i)。

这样求{1，2，…，n}的幂集的递推关系如下： 


M1={{}，{1}}

Mi=Mi-1∪Ai当i>1时

幂集是一个两层集合，采用双层表存放，其中每个列表元素表示幂集中的一个集合。大问题即求{1，2，…，i}的幂集，用Mi变量表示，小问题即求{1，2，…，i-1}的幂集，用Mi_1变量表示，首先置Mi_1={{}，{1}}表示M1。迭代变量i从2到n循环，每次迭代将完成的问题规模由i增加为i+1。对应的迭代法算法如下： 


1import copy

2def appendi(Mi_1,e):						#向Mi_1中每个集合元素的末尾添加e

3Ai=Mi_1

4for x in Ai:x.append(e)

5return Ai

6

7def subsets(n): 								#迭代法：求{1，2，…，n}的幂集

8Mi_1=［［］,［1］］            			#Mi_1初始化为{1}的幂集

9if n==1:return Mi_1					#处理特殊情况

10for i in range(2,n+1):

11Mi=copy.deepcopy(Mi_1)

12Ai=appendi(Mi_1,i)

13for x in Ai:Mi.append(x)    #将Ai中的所有集合元素添加到Mi中

14Mi_1=copy.deepcopy(Mi)

15return Mi



3．3．5实战——子集(LeetCode78★★)

1. 问题描述

扫一扫



视频讲解


给定一个含n(1≤n≤10)个整数的数组 nums，其中所有元素互不相同。设计一个算法求该数组中所有可能的子集(幂集)，结果中不能包含重复的子集，但可以按任意顺序返回幂集。例如，nums={1，2，3}，结果为{{}，{1}，{2}，{1，2}，{3}，{1，3}，{2，3}，{1，2，3}}。

2. 问题求解
将数组nums看成一个集合(所有元素互不相同)，求nums的所有可能的子集就是求nums的幂集，与3．3．4节的思路完全相同，仅需要将求{1，2，…，n}的幂集改为求nums［0．．n-1］的幂集，即设Mi为nums［0．．i］的幂集。定义运算appendi(Mi-1，nums［i］)返回在Mi-1中每个集合元素的末尾插入元素nums［i］的结果，即
appendi(Mi-1,nums［i］)=∪s∈Mi-1append(s,nums［i］)
则

Mi=Mi-1∪Ai，其中Ai=appendi(Mi-1，nums［i］)。

这样求nums的幂集的递推关系如下： 


M0={{}，{nums［0］}}

Mi=Mi-1∪Ai当i>0时

对应的迭代法算法如下： 


1class Solution:

2def subsets(self, nums: List［int］) > List［List［int］］:

3Mi=［］                      						#存放幂集

4Mi_1=［［］,［nums［0］］］

5n=len(nums)

6if n==1:return Mi_1                 		#处理特殊情况

7for i in range(1,n):

8Mi=copy.deepcopy(Mi_1)

9Ai=self.appendi(Mi_1,nums［i］)

10for x in Ai:Mi.append(x)        	#将Ai中的所有集合元素添加到Mi中

11Mi_1=copy.deepcopy(Mi)          #用新值替换旧值

12return Mi

13

14def appendi(self,Mi_1,e):               	#向Mi_1中每个集合元素的末尾添加e

15Ai=Mi_1                            			#浅复制

16for x in Ai:x.append(e)

17return Ai



上述程序提交时通过，执行用时为44ms，内存消耗为15．3MB。

3．4递归法
3．4．1递归法概述

1. 什么是递归
递归算法是指在算法定义中又调用自身的算法。若在p算法定义中调用p算法，称为直接递归算法； 若在p算法定义中调用q算法，而在q算法定义中又调用p算法，称为间接递归算法。任何间接递归算法都可以等价地转换为直接递归算法，所以下面主要讨论直接递归算法。

递归算法通常把一个大的复杂问题层层转换为一个或多个与原问题相似的规模较小的问题来求解，具有思路清晰和代码少的优点。目前主流的计算机语言（例如C/C++、Java和Python等）都支持递归，在内部通过系统栈实现递归调用。一般来说，能够用递归解决的问题应该满足以下3个条件。

① 需要解决的问题可以转化为一个或多个子问题来求解，而这些子问题的求解方法与原问题完全相同，只是在数量规模上不同。

② 递归调用的次数必须是有限的。

③ 必须有结束递归的条件来终止递归。

与迭代法类似，递归法也是一种算法实现技术，在设计递归法算法时首先用归纳法建立递推关系，这里称为递归模型，在此基础上直接转换为递归法算法。

2. 递归模型的一般格式
递归模型总是由递归出口和递归体两部分组成。递归出口表示递归到何时结束(对应最初、最原始的问题)，递归体表示求解时的递推关系。一个简化的递归模型如下： 


f(s1)=m

f(sn)=g(f(sn-1)，c)

其中g是一个非递归函数，m和c为常量。例如，为了求n!，设f(n)表示n!，对应的递归模型如下： 

f(1)=1

f(n)=n×f(n-1)当n>1时

3. 提取求解问题的递归模型
结合算法设计的特点，提取求解问题的递归模型的一般步骤如下。

① 对大问题f(s)(即f(s)用于求解大问题)进行分析，假设出合理的小问题f(s′)(即f(s′)用于求解小问题)。

② 假设小问题f(s′)是可解的，在此基础上确定大问题f(s)的解，即给出f(s)与f(s′)之间的递推关系，也就是提取递归体(与数学归纳法中假设i=n-1时等式成立，再求证i=n时等式成立的过程相似)。

③ 确定一个特定情况(例如f(1)或f(0))的解，由此作为递归出口(与数学归纳法中求证i=1或i=0时等式成立相似)。

4. 递归法算法的框架
在递归模型中递归体是核心，用于将小问题的解通过合并操作产生大问题的解，通常递归框架分为两种。

(1) 先求小问题的解后做合并操作，即先递后合，也就是在归来的过程中解决问题，其框架如下： 


def recursion1(n):							#先递后合的递归框架

if 满足出口条件:

直接解决

else:

recursion1(m)						#递去，递到最深处

merge()									#归来时执行合并操作



(2) 先做合并操作再求小问题的解，即先合后递，也就是在递去的过程中解决问题，其框架如下： 


def recursion2(n):							#先合后递的递归框架

if 满足出口条件:





直接解决

else:

merge()									#合并

recursion2(m)						#递到最深处后，再不断地归来



对于复杂的递归问题，例如在递去和归来过程中都包含合并操作，一个大问题分解为多个子问题等，其求解框架一般是上述基本框架的叠加。


扫一扫



视频讲解


【例34】假设二叉树采用二叉链存储，设计一个算法判断两棵二叉树r1和r2是否相同，所谓相同是指它们的形态相同并且对应的结点值相同。


解像树和二叉树等递归数据结构特别适合采用递归算法求解。对于本例，设f(r1，r2)表示二叉树r1和r2是否相同，它们的左、右子树的判断是两个小问题，如图3．8所示。依题意，对应的递归模型如下： 


f(r1，r2)=True当r1和r2均为空时

f(r1，r2)=False当r1和r2中一个为空另一个非空时

f(r1，r2)=False当r1和r2均不空但是结点值不相同时

f(r1，r2)=f(r1．left,r2．left) && f(r1．right,r2．right)其他

对应的递归算法如下： 



图3．8二叉树的两个小问题




1def same(r1,r2):								#递归算法：判断r1和r2是否相同

2if r1==None and r2==None:

3return True

4elif r1==None or r2==None:

5return False

6if r1.val!=r2.val:

7return False

8leftans=same(r1.left,r2.left)			#递归调用1

9rightans=same(r1.right,r2.right)		#递归调用2

10return leftans and rightans



后面通过几个应用进一步讨论递归法算法的设计过程。

3．4．2冒泡排序

1. 问题描述
有一个整数序列a［0．．n-1］，采用冒泡排序实现a的递增有序排序。冒泡排序的过程是，i从0到n-2循环，a［0．．i-1］是有序区，a［i．．n-1］是无序区，并且前者的所有元素均小于或等于后者的任意元素，每次循环在a［i．．n-1］无序区采用冒泡方式将最小元素放在a［i］位置。其迭代算法如下： 


1def Bubble(a,i):	                	#一趟排序:在a［i..n-1］中冒泡最小元素到a［i］中

2exchange=False

3for j in range(len(a)-1,i,-1):      	#无序区中的元素比较,找出最小元素

4if a［j-1］>a［j］:							#当相邻元素反序时

5a［j］,a［j-1］=a［j-1］,a［j］        #a［j］与a［j-1］进行交换

6exchange=True			     #本趟排序发生交换置exchange为真

7return exchange                #返回是否存在交换

8

9def BubbleSort1(a):	              	#迭代算法：冒泡排序

10for i in range(0,len(a)-1): 			#进行n-1趟排序

11if not Bubble(a,i):return       #本趟未发生交换时结束算法



现在要求采用递归实现冒泡排序算法。

2. 问题求解
采用不完全归纳法产生冒泡排序的递推关系。例如a=(2，5，4，1，3)，这里n=5，用［］表示有序区，各趟的排序结果如下： 

初始： (［］2，5，4，1，3)#初始有序区为空

i=0： (［1］，2，5，4，3)#调用Bubble从a［0．．4］中冒泡最小元素到a［0］

i=1： (［1，2］，3，5，4)#调用Bubble从a［1．．4］中冒泡最小元素到a［1］

i=2： (［1，2，3］，4，5)#调用Bubble从a［2．．4］中冒泡最小元素到a［2］

i=3： (［1，2，3，4］，5)#调用Bubble从a［3．．4］中冒泡最小元素到a［3］



图3．9大、小问题的表示及其

递推分析1

解法1： 采用先递后合的递归算法。设f(a，i)用于实现a［0．．i］(共i+1个元素)的递增排序，为大问题，则f(a，i-1) 实现a［0．．i-1］(共i个元素)的排序，为小问题，如图3．9所示。


当执行f(a，i-1)求解小问题后，a［0．．i-1］变为全局有序区，在a［i．．n-1］中冒泡最小元素到a［i］位置(调用前面的Bubble算法实现)，则a［0．．i］变为更大的全局有序区，这就是大问题的解，即f(a，i)。其递推方向是从后向前。当i=-1时，a［0．．i］为空，看成有序的。对应的递推模型如下： 


f(a，i) ≡ 不做任何事情当i=-1时

f(a，i) ≡ f(a，i-1); Bubble(a,i); 否则

显然f(a，n-1)用于实现a［0．．n-1］递增排序，由于这样排序后最后一个元素a［n-1］一定是最大元素，所以调用f(a，n-2)就可以实现a［0．．n-1］的递增排序。对应的递归算法(未考虑一趟没有发生交换时提前结束的情况)如下： 


1def BubbleSort21(a,i):			    				#递归冒泡排序1

2if i==-1:return			        				#满足递归出口条件

3BubbleSort21(a,i-1)			    			#递归调用

4Bubble(a,i)

5





6def BubbleSort2(a):				    			#冒泡排序

7BubbleSort21(a,len(a)-2)





图3．10大、小问题的表示及其

递推分析2

解法2： 采用先合后递的递归算法。设f(a，i)用于实现a［i．．n-1］(共n-i个元素)的递增排序，它是大问题，则f(a，i+1) 实现a［i+1．．n-1］(共n-i-1个元素)的排序，它是小问题，如图3．10所示。

当执行f(a，i+1)求解小问题后，a［i+1．．n-1］变为全局有序区，在a［i．．n-1］中冒泡最小元素到a［i］位置(调用前面的Bubble算法实现)，则a［i．．n-1］变为更大的全局有序区，这就是大问题的解，即f(a，i)。其递推方向是从前向后。当i=n-1时，a［n-1．．n-1］中仅包含最后一个元素，它一定是最大元素，排序结束。对应的递推关系如下： 

f(a，i) ≡ 不做任何事情当i=n-1时

f(a，i) ≡ Bubble(a,i); f(a，i+1); 否则


显然f(R，0)用于实现R［0．．n-1］的递增排序。对应的递归算法如下： 


1def BubbleSort31(a,i):							#递归冒泡排序2

2if i==len(a)-1:return							#满足递归出口条件

3if Bubble(a,i):BubbleSort31(a,i+1)		  	#一趟中发生交换时递归调用

4

5def BubbleSort3(a):							#冒泡排序

6BubbleSort31(a,0)



3．4．3求全排列

1. 问题描述

扫一扫



视频讲解


给定正整数n(n≥1)，给出求1~n的全排序的递归模型和递归算法。例如，n=3时，全排列是{{1，2，3}，{1，3，2}，{3，1，2}，{2，1，3}，{2，3，1}，{3，2，1}}。

2. 问题求解
以n=3为例，求1~3的全排列的过程如图3．11所示，步骤如下： 

① 1的全排列是{{1}}。

② {{1}}中只有一个元素{1}，在{1}前后位置分别插入2得到{1，2}，{2，1}，合并起来得到1~2的全排列{{1，2}，{2，1}}。

③ {{1，2}，{2，1}}中有两个元素，在{1，2}中的3个位置插入3得到{1，2，3}，{1，3，2}，{3，1，2}，在{2，1}中的3个位置插入3得到{2，1，3}，{2，3，1}，{3，2，1}，合并起来得到1~3的全排列{{1，2，3}，{1，3，2}，{3，1，2}，{2，1，3}，{2，3，1}，{3，2，1} }。

归纳起来，设Pi表示1~i(i≥1，共i个元素)的全排列(是一个两层集合，其中每个集合元素表示1~i的某个排列)，为大问题，则Pi-1为1~i-1(共i-1个元素)的全排列，为小问题。显然有P1={{1}}。



图3．11求1~3的全排列的过程


考虑i>1的情况，假设Pi-1已经求出，对于Pi-1中的任意一个集合元素s，s表示为s0s1…si-2(长度为i-1，下标从0开始)，其中有i个插入位置(即位置i-1，位置i-2，…，位置0)，定义Insert(s，i，j)返回s的序号为j(0≤j≤i-1)的位置上插入元素i后的集合元素，定义CreatePi(s，i)返回s中每个位置插入i的结果，即 
CreatePi(s,i)=∪0≤j≤len(s)Insert(s,i,j)
则
Pi=∪s∈Pi-1CreatePi(s,i)

求1~n的全排序的递归模型如下： 

P1={{1}}

Pi=∪s∈Pi-1CreatePi(s,i)当i>1时

用双层表存放1~n的全排列。对应的递归算法如下： 


1import copy

2def Insert(s,i,j):								#在s的位置j插入i

3tmp=copy.deepcopy(s)

4tmp.insert(j,i)                    	#位置j插入整数i

5return tmp

6

7def CreatePi(s,i):							#在s集合中的i-1到0位置插入i

8tmp=［］

9for j in range(len(s),-1,-1):          	#在s(含i-1个整数)的每个位置插入i

10s1=Insert(s,i,j)

11tmp.append(s1)               #将s1添加到Pi中

12return tmp

13

14def perm11(n,i): 	      				#递归算法

15if i==1:

16return ［［1］］

17else:

18Pi=［］										#存放1~i的全排列

19Pi_1=perm11(n,i-1)			  	#求出Pi_1

20for x in Pi_1:

21tmp1=CreatePi(x,i)  			#在x集合中插入i得到tmp1

22for y in tmp1:Pi.append(y)	   	#将tmp1的全部元素添加到Pi中

23return Pi

24

25def perm1(n): 						  		#用递归法求1~n的全排列

26return perm11(n,n)




扫一扫



视频讲解


3．4．4实战——字符串解码(LeetCode394★★)

1. 问题描述
给定一个经过编码的有效字符串s，设计一个算法返回s解码后的字符串，编码规则是用“k［encoded_string］”表示方括号内的 encoded_string (仅包含小写字母)正好重复k(k保证为正整数) 次。例如，s="3［a］2［bc］"，答案为"aaabcbc"，若s="abc3［cd］xyz"，答案为"abccdcdcdxyz"。

2. 问题求解
用ans存放s展开的字符串(初始为空)，用整型变量i从0开始遍历s(将i设计为全局变量)，一边遍历一边展开。采用递归法求解，设f(s)求字符串s解码后的字符串。

(1) 递归出口： 对于不包含数字和括号的字符串s，直接连接到ans中。例如，s="abc"，则ans="abc"。

(2) 递归体： 依题意，s是一个合法的字符串，分为以下几种情况。

① s="k［encoded_string］"（以字符'］'结尾），其中encoded_string是一个合法的字符串，先提取整数k，再调用f(encoded_string)求出小问题的结果，则ans为k个f(encoded_string)的连接。例如s="3［a］"，则ans="aaa"。

② s="s1…sn"，其中si是合法的子串，则ans=f(s1)+…+f(sn)。例如，s="abc3［cd］xyz"，则ans="abc"+"cdcdcd"+"xyz"="abccdcdcdxyz"。

对应的递归程序如下： 


1class Solution:

2def decodeString(self, s: str) > str:          			#求解算法

3self.i=0                                							#类变量i从0开始遍历s

4return self.unfold(s)

5

6def unfold(self,s):                                         		#递归算法

7ans=""

8while self.i<len(s) and s［self.i］!='］':     			#处理到'］'为止

9if s［self.i］>='a' and s［self.i］<='z':       			#遇到字母

10ans+=s［self.i］; self.i+=1

11else:

12k=0

13while self.i<len(s) and s［self.i］>='0' and s［self.i］<='9': 

14k=k*10+ord(s［self.i］)-ord('0');self.i+=1 #数字符转为整数k

15self.i+=1                       						#数字字符后面为'［'，则跳过该'［'

16tmp=self.unfold(s)                              		#求子串解码结果tmp

17self.i+=1                               					#后面是一个'］'，跳过该'］'

18while k>0:                                      			#连接tmp字符串k次

19ans+=tmp;k-=1

20return ans                                             			#s处理完毕返回ans



上述程序提交时通过，执行用时为32ms，内存消耗为15MB。

3．5递推式计算
递归算法的执行时间可以用递推式(也称为递归方程)来表示，这样求解递推式对算法分析来说极为重要。本节介绍几种求解简单递推式的方法，对于更复杂的递推式，可以采用数学上的生成函数和特征方程求解。

3．5．1直接展开法

求解递推式最自然的方法是将其反复展开，即直接从递归式出发，一层一层地往前递推，直到达到最前面的初始条件为止，就得到了问题的解。

【例35】求解梵塔问题的递归算法如下，分析移动n盘片的时间复杂度。


1def Hanoi(n,x,y,z):

2if n==1:

3print("将盘片%d从%c搬到%c"%(n,x,z))

4else:

5Hanoi(n-1,x,z,y)

6print("将盘片%d从%c搬到%c"%(n,x,z))

7Hanoi(n-1,y,x,z)



解设调用Hanoi(n，x，y，z)的执行时间为T(n)，由其执行过程得到以下求执行时间的递归关系(递推关系式)。

T(n)=1当n=1时

T(n)=2T(n-1)+1当n>1时

则
T(n)=2［2T(n-2)+1］+1=22T(n-2)+1+21
=23T(n-3)+1+21+22
=…
=2n-1T(1)+1+21+22+…+2n-2
=2n-1=O(2n)
所以移动n盘片的时间复杂度为O(2n)。

3．5．2递归树方法

递归树方法是直接展开法的一种图形表述，用递归树求解递推式的基本过程是先展开递推式，构造对应的递归树，然后把每一层的时间进行求和，从而得到算法执行时间的估计，再用时间复杂度形式表示。

【例36】分析以下递推式的时间复杂度： 

T(n)=1当n=1时

T(n)=2T(n/2)+n2当n>1时

解对于T(n)画出一个结点如图3．12(a)所示，将T(n)展开一次的结果如图3．12(b)所示，再展开T(n/2)的结果如图3．12(c)所示，以此类推，构造的递归树如图3．13所示。从中看出在展开过程中子问题的规模逐步缩小，当到达递归出口时，即当子问题的规模为1时递归树不再展开。



图3．12展开两次的结果


显然在递归树中第1层的问题规模为n，第2层的问题规模为n/2，以此类推，当展开到第k+1层时，其规模为n/2k=1，所以递归树的高度为log2n+1。

第1层有一个结点，其时间为n2，第2层有两个结点，其时间为2(n/2)2=n2/2，以此类推，第k层有2k-1个结点，每个子问题的规模是(n/2k-1)2，其时间为2k-1(n/2k-1)2=n2/2k-1。叶子结点的个数为n，其时间为n。将递归树每一层的时间加起来，可得： 
T(n)=n2+n2/2+…+ n2/2k-1+…+n=O(n2)



图3．13一棵递归树


【例37】分析以下递推式的时间复杂度： 

T(n)=1当n=1时

T(n)=T(n/3)+T(2n/3)+n当n>1时

解构造的递归树如图3．14所示，不同于图3．13所示的递归树中所有叶子结点在同一层，这棵递归树的叶子结点的层次可能不同，从根结点出发到达叶子结点有很多路径，最左边的路径是最短路径，每走一步问题的规模减小为原来的1/3(问题规模变小的速度相对较快)，最右边的路径是最长路径，每走一步问题的规模减小为原来的2/3(问题规模变小的速度相对较慢)。

最坏的情况是考虑右边最长的路径。设右边最长路径的长度为h(指路径上经过的分支线的数目)，则有n(2/3)h=1，求出h=log3/2n。

因此这棵递归树有log3/2n+1层，每层结点的数值和为n，所以T(n)≤n(log3/2n+1)=O(nlog3/2n)=O(nlog2n)，即该递推式的时间复杂度是O(nlog2n)。



图3．14一棵递归树


3．5．3主方法

主方法提供了求解如下形式递推式的一般方法： 

T(1)=c

T(n)=aT(n/b)+f(n)当n>1时

其中a≥1，b>1为常数，n为非负整数，T(n)表示算法的执行时间，该算法将规模为n的原问题分解成a个子问题，每个子问题的大小为n/b，f(n)表示分解原问题和合并子问题的解得到答案的时间。例如，对于递推式T(n)=3T(n/4)+n2，有a=3，b=4，f(n)=n2。

主方法的求解对应如下主定理。

主定理： 设T(n)是满足上述定义的递推式，T(n)的计算如下。

① 若对于某个常数ε>0，有f(n)=O(nlogba-ε)，称为f(n)多项式地小于nlogba(即f(n)与nlogba的比值小于或等于n-ε)，则T(n)=Θ(nlogba)。

② 若f(n)=Θ(nlogba)，即f(n)多项式的阶等于nlogba，则T(n)=Θ(nlogbalog2n)。

③ 若对于某个常数ε>0，有f(n)=O(nlogba+ε)，称为f(n)多项式地大于nlogba(即f(n)与nlogba的比值大于或等于nε)，并且满足af(n/b)≤cf(n)，其中c<1，则T(n)=Θ(f(n))。 

主定理涉及的3种情况都是拿f(n)与nlogba作比较，递推式解的渐近阶由这两个函数中的较大者决定。情况①是函数nlogba的阶较大，则T(n)=Θ(nlogba)； 情况③是函数f(n)的阶较大，则T(n)=Θ(f(n))； 情况②是两个函数的阶一样大，则T(n)=Θ(nlogbalog2n)，即以n的对数作为因子乘上f(n)与T(n)的同阶。

此外有一些细节不能忽视，情况①中f(n)不仅必须比nlogba的阶小，而且必须是多项式地比nlogba小，即f(n)必须渐近地小于nlogba与n-ε的积； 情况③中f(n)不仅必须比nlogba的阶大，而且必须是多项式地比nlogba大，即f(n)必须渐近地大于nlogba与nε的积，同时还要满足附加的“正规性”条件，即af(n/b)≤cf(n)，该条件的直观含义是a个子问题的再分解和再合并所需要的时间最多与原问题的分解和合并所需要的时间同阶，这样T(n)就由f(n)确定，也就是说如果不满足正规性条件，采用这种递归分解和合并求解的方法是不合适的，即时间性能差。

当然还有一点很重要，即上述3类情况并没有覆盖所有可能的f(n)。在情况①和②之间有一个间隙，即f(n)小于但不是多项式地小于nlogba。类似地，在情况②和③之间也有一个间隙，即f(n)大于但不是多项式地大于nlogba。如果函数f(n)落在这两个间隙之一中，或者虽然有f(n)=O(nlogba+ε)，但是正规性条件不满足，那么主方法将无能为力。

【例38】采用主定理求以下递推式的时间复杂度： 

T(n)=1当n=1时

T(n)=4T(n/2)+n当n>1时

解这里a=4，b=2，nlogba=n2，f(n)=n=O(nlogba-ε)，ε=1，即f(n)多项式地小于nlogba，满足情况①，所以T(n)=Θ(nlogba)=Θ(n2)。

【例39】采用主方法求以下递推式的时间复杂度： 

T(n)=1当n=1时

T(n)=3T(n/4)+nlog2n当n>1时

解这里a=3，b=4，f(n)=nlog2n，nlogba=nlog43=O(n0．793)，显然f(n)的阶大于n0．793(因为f(n)=nlog2n>n1>n0．793)，如果能够证明主定理中的情况③成立则按该情况求解。对于足够大的n，af(n/b)=3(n/4)log2(n/4)=(3/4)nlog2n-3n/2≤(3/4)nlog2n=cf(n)，这里c=3/4，满足正规性条件，则有T(n)=Θ(f(n))=Θ(nlog2n)。

【例310】采用主定理和直接展开法求以下递推式的时间复杂度： 

T(n)=1当n=2时

T(n)=2T(n/2)+(n/2)2当n>1时

解采用主定理，这里a=2，b=2，nlogba=nlog22=n，f(n)=n2/4，f(n)多项式地大于nlogba。对于足够大的n，af(n/b)=2f(n/2)=2(n/2/2)2=n2/8≤cn2/4=cf(n)，c≤1/2即可，也就是说满足正规性条件，按照主方法的情况③，有T(n)=Θ(f(n))=Θ(n2)。

采用直接展开法求解，不妨设n=2k+1，即n2k=2。
T(n)=2Tn2+n22=22Tn22+n224+n22=22Tn22+n223+n222
=222Tn23+n226+n223+n222=23Tn23+n224+n223+n222
=…=2kTn2k+n22k+1+n22k+…+n222
=n2×2+n212k+1+12k+…+122=n+n212-1n=n22=Θ(n2)
两种方法得到的结果是相同的。如果递推式如下： 

T(1)=c

T(n)=aT(n/b)+cnk当n>1时

其中a、b、c、k都是常量，可以这样简化主定理： 

① 若a>bk，则T(n)=Θ(nlogba)。

② 若a=bk，则T(n)=Θ(nklogbn)。

③ 若a<bk，则T(n)=Θ(nk)。

以上介绍的递推式求解方法将在第4章有关分治法算法的分析中大量用到。

习题3


扫一扫



练习题




扫一扫



自测题