算法分析与设计5.ppt

《算法分析与设计5.ppt》由会员分享，可在线阅读，更多相关《算法分析与设计5.ppt（16页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、陈卫东华南师范大学计算机科学系Algorithms:Design Techniques and Analysis 算法设计算法设计技巧与分析技巧与分析12/31/20220 Chapter 5 InductionnIntroductionnRadix SortnInteger ExponentiationnEvaluating Polynomials nGenerating PermutationsnFinding the Majority Element12/31/20221 Introductionn递归算法的基本模式（求解问题）n递归算法的 优点n例1 选择排序n例2 直接插入排序12/

2、31/20222递归算法的基本模式（求解问题）递归算法的基本模式（求解问题）1.n=1,f(1)(直接求解)；2.若f(k)（kn）可求，则 利用f(1)、f(n-1)得f(n)。注：一般来说，求f(k)（k1,利用f(1)、f(n-1)求得f(n)；注：关键步骤是由f(1)、f(n-1)得到f(n)。其正确性可使用归纳法归纳法来证明。12/31/20224递归算法的特点递归算法的特点递归算法的优点：1.读写简明；2.算法的正确性易于用数学归纳法来证；3.算法的复杂性往往可利用递归关系来分析缺点：1.算法的执行流程不易理解；2.递归调用往往需要额外的时空开销12/31/20225例例1 选择排

3、序选择排序n算法的基本框架：Ain排序排序 若若ni,将将Ain中中最小元素找出，并换至最小元素找出，并换至Ai处；处；Ai+1n排序排序;n算法递归调用图算法递归调用图n算法的时空复杂性分析算法的时空复杂性分析12/31/20226例例2 直接插入排序直接插入排序n算法的基本框架：A1i排序排序 若若i1,A1i-1排序排序;将将Ai插入到插入到A1i-1中的适当位置处；中的适当位置处；n算法递归调用图算法递归调用图n算法的时空复杂性分析算法的时空复杂性分析12/31/20227Radix Sort（基数排序）基数排序）n问题：问题：要要求求对对 n个个数数的的序序列列L=a1,a2,an进

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

5、奇数，则xn=x(xm)2 nAlgorithm 5.4 EXPRECnAlgorithm 5.5 EXPn算法的时空复杂度算法的时空复杂度：(log n)12/31/20229Evaluating Polynomials(多项式求值多项式求值)n问题：问题：求下列实系数多项式的值：求下列实系数多项式的值：Pn(x)=anxn+an-1xn-1+a1x+a0n算法思想（Horners rule）Pn(x)=xPn-1(x)+a0nAlgorithm 5.6 HORNERn算法的时空复杂性分析算法的时空复杂性分析 时间复杂度：(n)12/31/202210Generating Permutati

6、ons(生成排列生成排列)n问题：问题：要求产生要求产生1,2,n的所有排列。的所有排列。n算法算法1n算法思想算法思想 12,3,n的排列的排列，21,3,n的排列的排列，n1,2,n-1的排列的排列。nAlgorithm 5.7 PERMUTATIONS1n算法时间复杂度算法时间复杂度:(nn!)12/31/202211Generating Permutations(生成排列生成排列)n算法算法2n算法思想算法思想 n n ，n。nAlgorithm 5.8 PERMUTATIONS2n算法时间复杂度算法时间复杂度:(nn!)12/31/202212Finding the Majority

7、 Element(找主元素找主元素)n问题问题 序列序列A1.n中是存在主元素？若有请找出来。中是存在主元素？若有请找出来。注注：A中中主主元元素素是是指指在在A中中出出现现次次数数多多于于 n/2 次次的元素。的元素。n算法算法1：穷举法（：穷举法（the brute-force method）n时间复杂度时间复杂度:(n2)n算法算法2：排序法：排序法n时间复杂度时间复杂度:(n log n)n算法算法3：找中元素法（：找中元素法（finding the median）n时间复杂度时间复杂度:(n)12/31/202213Finding the Majority Element(找主元素找

8、主元素)n算法算法4：n算法思想算法思想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.nAlgorithm 5.9 MAJORITYn算法时间复杂度算法时间复杂度:(n)12/31/202214思考题：思考题：nP155-158 5.1 要求：时间复杂度为(n),空间复杂度为O(n)。5.8 5.9 5.18 5.23 5.24 5.3112/31/202215