算法分析与设计5

1、2020/7/15,0,陈卫东 华南师范大学计算机科学系,Algorithms :Design Techniques and Analysis 算法设计技巧与分析,2020/7/15,1,Chapter 5 Induction,Introduction Radix Sort Integer Exponentiation Evaluating Polynomials Generating Permutations Finding the Majority Element,2020/7/15,2,Introduction,递归算法的基本模式（求解问题） 递归算法的 优点 例1 选择排序 例2 直接

2、插入排序,2020/7/15,3,递归算法的基本模式（求解问题）,1. n=1, f(1) (直接求解)； 2. 若f(k)（kn）可求，则 利用f(1)、f(n-1)得f(n)。 注：一般来说，求f(k)（kn）比求f(n)容易。若有办法由f(1)、f(n-1)得到f(n)即可。 归纳原理,2020/7/15,4,递归算法的基本模式（求解问题）,递归算法的框架： f(n) n=1, f(1) (直接求解)； n1, 利用f(1)、f(n-1)求得f(n)； 注：关键步骤是由f(1)、f(n-1)得到f(n)。 其正确性可使用归纳法来证明。,2020/7/15,5,递归算法的特点,递归算法的优

3、点： 1. 读写简明； 2. 算法的正确性易于用数学归纳法来证； 3. 算法的复杂性往往可利用递归关系来分析 缺点： 1. 算法的执行流程不易理解； 2. 递归调用往往需要额外的时空开销,2020/7/15,6,例1 选择排序,算法的基本框架： Ain排序 若ni, 将Ain中最小元素找出，并换至Ai处； Ai+1n排序; 算法递归调用图 算法的时空复杂性分析,2020/7/15,7,例2 直接插入排序,算法的基本框架： A1i排序 若i1, A1i-1排序; 将Ai插入到A1i-1中的适当位置处； 算法递归调用图 算法的时空复杂性分析,2020/7/15,8,Radix Sort（基数排序）

4、,问题： 要求对 n个数的序列L=a1, a2 , , an进行排序，其中每个数恰好由k位数字组成，每位数字均取自0,1,9。 算法思想：对于k使用归纳法。 例子 Algorithm 5.3 RADIXSORT 算法的时空复杂性分析 时间复杂度： (kn) 空间复杂度： (n),2020/7/15,9,Integer Exponentiation(求整数次幂),问题： 求实数x的n次幂，即xn ，其中n为一个非负整数。 算法思想 计算xn 计算xm ； / m=n/2 若n是偶数，则xn =(xm)2, 若n是奇数，则xn =x(xm)2 Algorithm 5.4 EXPREC Algori

5、thm 5.5 EXP 算法的时空复杂度： (log n),2020/7/15,10,Evaluating Polynomials(多项式求值),问题： 求下列实系数多项式的值： Pn(x)=anxn+ an-1xn-1 + + a1x + a0 算法思想（Horners rule） Pn(x)= xPn-1(x) + a0 Algorithm 5.6 HORNER 算法的时空复杂性分析 时间复杂度： (n),2020/7/15,11,Generating Permutations(生成排列),问题： 要求产生1,2,n的所有排列。 算法1 算法思想 12,3,n的排列， 21,3,n的排列，

6、 n1,2,n-1的排列。 Algorithm 5.7 PERMUTATIONS1 算法时间复杂度: (nn!),2020/7/15,12,Generating Permutations(生成排列),算法2 算法思想 n n ， n。 Algorithm 5.8 PERMUTATIONS2 算法时间复杂度: (nn!),2020/7/15,13,Finding the Majority Element(找主元素),问题 序列A1.n中是存在主元素？若有请找出来。 注：A中主元素是指在A中出现次数多于n/2次的元素。 算法1：穷举法（the brute-force method） 时间复杂度:

7、(n2) 算法2：排序法 时间复杂度: (n log n) 算法3：找中元素法（finding the median） 时间复杂度: (n),2020/7/15,14,Finding the Majority Element(找主元素),算法4： 算法思想 Observation 5.1 If two different elements in the original sequence are removed, then the majority in the original sequence remains the majority in the new sequence. Algorithm