算法设计技巧与分析 归纳技术(第5章)

0第二部分基于递归的技术递归

——是将问题分解为一个或者多个与原问题结构相同的子问题，并由这些子问题的解得到原问题解的过程。三种情形归纳法，或尾递归

第五章归纳法子问题无重叠的情形

第六章分治法

子问题有重叠的情形（用空间换时间）

第七章动态规划1

第五章归纳引言基数排序（RadixSort）求整数次幂多项式求值产生排列找主元素（MajorityElement）2

引言数学归纳法的基本模式

（用于证明问题）递归算法的基本模式

（用于求解问题）递归算法的特点：算法的正确性证明已嵌入在算法 的描述中。例1选择排序（SelectionSort）例2插入排序（InsertionSort）3数学归纳法的基本模式(用于证明问题)1.n=1,f(1)……成立；2.假设k<n结论成立，即f(k)……成立。

利用f(1)、…、f(n-1)得证f(n)…也成立。3.综上所述，对于所有的n≥1，都有f(n)……成立。

归纳原理4递归算法的基本模式(用于求解问题)1.n=1,f(1)…(直接求解)；

2.(递归)求解f(k)…（k<n），

并利用f(1)、…、f(n-1)得f(n)…

注：一般来说，求f(k)（k<n）比求f(n)要容易，关键在于要有办法由f(1)、…、f(n-1)得到f(n)

。

归纳原理5递归算法的框架：

f(n){n=1,f(1)…(直接求解)；

n>1,(递归)求解f(k)…（k<n）并利用f(1)、…、f(n-1)求得f(n)…；

}

注：关键步骤是由f(1)、…、f(n-1)得到f(n)。其正确性可使用归纳法来证明。递归算法的基本模式(用于求解问题)6优点：1.读写简明；2.算法的正确性易于用数学归纳法来证；3.算法的复杂性往往可利用递归关系来分析缺点：1.算法的执行流程不易理解；2.递归调用往往需要额外的时空开销递归算法的特点7例1选择排序（Selectionsort

）8例1选择排序（Selectionsort

）复杂度

C(n):表示元素比较的次数。 显然n=1时,C(1)=0； 过程sort第一次被调用时i=1,数组中有n个元素，需要n-1次比较； 后面对A[2…n]进行排序，也即sort(i+1)的递归调用。 故有：

9例2插入排序（Insertionsort

）10例2插入排序（Insertionsort

）复杂度

考虑一下插入排序的复杂度采用递归算法应该如果表示？11基数排序（RadixSort）问题

要求对n个数的序列L={a1,a2,…,

an}进行排序，其中每个数恰好由k位数字组成，即每位数具有dkdk-1…d1形式，di均取自{0,1,…,9}。算法思想:

对于k使用归纳法，即建立10个表L0,L1,…,L9，将L中的数据按每位的数填到对应的表中。可以有两种思路：

1、从高位到低位进行填表

2、从低位到高位进行填表(基数排序)12基数排序（RadixSort）算法工作如下 首先根据d1位，把数分到10个表L0,L1,…,L9中，这样，d1=0的数分到表L0中，d1=1的数分到表L1中，等等。然后，表被用L0,L1,…,L9的顺序接起来。再后来，把它们按照d2分到10张表中，按顺序接起来。以此类推，在把它们按d分到表中并按顺序接起来后，所有的数就排好了序。实例13基数排序（RadixSort）14基数排序（RadixSort）复杂度时间复杂度：

(kn)

根据某一位数字把数分到表中的方法做了k遍，每一遍的代价是(n)时间，此算法的时间是(kn)。如果k是常数，运行时间就是(n)。空间复杂度：

(n)

因为算法需要10张表来存放所有的n个数据，也就是这些表全部的大小时(n)。15求整数次幂问题

求实数x的n次幂，即xn

，其中n为一个非负整数。算法思想计算xn

{计算xm；//

m=

n/2

若n是偶数，则xn=(xm)2,

若n是奇数，则xn=x(xm)2}16求整数次幂17求整数次幂

对算法EXPREC进行改进，可以导出迭代的方法。令n的二进制数字为dkdk-1…d0。从y=1开始，从左到右扫描二进制数字，如果当前的二进制数字为0，就对y平方；如果它是1，就对y平方并乘上x。于是有算法EXP。18求整数次幂时间复杂度：

(logn)

假定每次乘法的时间是常数，那么这两个版本的算法的运行时间是(logn)。19多项式求值问题

求下列实系数多项式的值：

Pn(x)=anxn+an-1xn-1+…+

a1x

+

a0算法思想（Horner’srule）

如果设 则有 Pn(x)=xPn-1(x)

+

a020多项式求值时间复杂度：

(n)

易见，算法HORNER的代价是n次乘法和n次加法。即时间复杂度是

(n)。21产生排列（GeneratingPermutations）问题

要求产生1,2,…,n的所有排列。算法1思想

1[2,3,…,n的排列]，

2[1,3,…,n的排列]，……，

n[1,2,…,n-1的排列]。22产生排列（GeneratingPermutations）23产生排列（GeneratingPermutations）时间复杂度:

(nn!)24产生排列（GeneratingPermutations）25产生排列（GeneratingPermutations）算法2思想

n

[

…

]

[

]

n

[

…

]，……，

[

…

]n。26产生排列（GeneratingPermutations）27产生排列（GeneratingPermutations）时间复杂度:

(nn!)28产生排列（GeneratingPermutations）

令m!h(m)=f(m)，那么29找主元素（FindingtheMajorityElement）问题

序列A[1..n]中是存在主元素？若有请找出来。A中主元素是指在A中出现次数多于

n/2

次的元素。算法1——穷举法时间复杂度:

(n2)算法2——排序时间复杂度:

(nlogn)算法3——找中值时间复杂度:

(n)30找主元素（FindingtheMajorityElement）算法4算法思想命题5.1如果删去原序列中的两个不同元素，则原序列中的主元素仍然在剩下的序列中.A