资源描述：
《算法设计与分析-变治法.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第6章变治法首先是”变“，将问题的实例变形，变得更容易求解；思考：和分治与减治的区别然后是”治“，对问题的实例进行求解。变治法有三个变形:（1）实例化简——同样问题（2）改变表现——同样实例（3）问题化简——另一问题1（1）实例化简——同样问题6.1预排序6.2高斯消去法6.3平衡查找树—AVL树（2）改变表现——同样实例6.32-3树6.4堆和堆排序6.5霍纳法则和二进制幂（3）问题化简——另一问题6.626.1预排序列表是有序的话，许多关于列表的问题更容易求解。因此很多问题需要先排序，则该问题的时间效率依赖于排序算法的效率。回忆前面所学的排序算法：插入排
2、序最差Θ(n2)平均Θ(n2)最优Θ(n)快速排序最差Θ(n2)平均Θ(1.38nlog2n)最优Θ(nlog2n)合并排序最差Θ(nlog2n)选择排序Θ(n2)冒泡排序Θ(n2)3例1、检验数组中元素的唯一性蛮力法如何做？时间效率是多少？如果先排序，则如何检查元素的唯一性？只需检查相互紧挨的元素。PresortElementUniqueness(A[0..n-1])//先对数组排序再验证唯一性//输入：数组A//输出：若A没有相等的元素，返回“true”,否则返回“false”.对数组排序；fori=0ton-2doifA[i]=A[i+1]return
3、falsereturntrue整个过程时间效率是多少？4预排序例2、模式计算模式：指数组列表中出现次数最多的值。如{5,1,5,7,6,5,7}中5是模式所能想到的求模式的方法：用辅助列表列出所有元素及其出现频率。时间效率如何分析？采用排序的思想先排序后计算相邻接次数最多的等值元素。时间效率如何分析？5思考：预排序还可以用在什么方面？查找分析顺序查找和先排序再查找的时间效率如果要在同一个列表中进行多次查找，在排序上花费时间是值得的。课堂练习：采用合并排序为预排序，折半查找，要做多少次查找才能使得对一个由n个元素构成的数组所做的预排序是有意义的。6预排序的其他
4、应用：对点排序，拓扑排序课堂练习：P153476.2Gauss消去法科学计算中通常需要解多个变量的方程组，这些方程组当中最简单的是线性方程组，也就是变量的次数均为1次的。求解线性方程的方法有利用高斯消元的直接法以及迭代法。体现的变治的思想：将方程组变成一个具有特殊性质的方程组(上三角矩阵)81、高斯消元法一般的线性方程组是指如下形式的方程组：9高斯消元法分消元过程和回代过程。消元过程将原方程组变为上三角方程组，回代过程得到方程组的解。10高斯消元法举例：11高斯消元法的伪代码GaussElimination(A[1..n],b[1..n])//输入：系数矩阵
5、A及常数项b//输出：方程组的增广矩阵等价的上三角矩阵fori=1tondoA[i][n+1]=b[i]fori=1ton-1doforj=i+1tondofork=iton+1doA[j][k]=A[j][k]–A[i][k]*A[j][i]/A[i][i]12高斯消元法的效率分析基本操作：乘法执行次数：易见，三重循环C(n)∈Θ(n3)132、LU分解法高斯消去法的现代商业实现是以LU分解为基础的。14系数矩阵为下三角矩阵L，由主对角线上的1以及在高斯消去过程中行的乘数构成上三角矩阵U是消去的结果可观察出两个矩阵的乘积LU等于A15记原方程组为AX=bA
6、=LU则原方程组为LUX=b其求解转化为两个三角形方程组的求解：LY=b——下三角方程组UX=Y——上三角方程组16LU分解法与LY=b,UX=Y对应的方程组如下：易得：(y1,y2,y3)=(1,3,-2),(x1,x2,x3)=(1,0,-1)17评价1一旦的到矩阵A的LU分解，无论对于什么样的右边向量b，我们都可以对方程组Ax=b求解，每次求一个。2LU分解不需要额外的存储空间183、计算矩阵的逆逆矩阵的定义：求矩阵A的逆矩阵，如何转换19计算矩阵的逆求矩阵A的逆矩阵，转化为求解n个方程组AXj=bj其中，bj是单位矩阵的第j列，而Xj则是逆矩阵的第j
7、列。203、计算矩阵的行列式n阶矩阵的行列式的计算由递归公式定义：其中，n=1时，detA=a11，若j为奇数，sj=1，若j为偶数，sj=-1例如n=3的情形如下：21计算矩阵行列式按照定义计算高阶行列式是不可能的。可利用高斯消元法：矩阵A的行列式=消元后上三角矩阵的行列式=对角线上元素之乘积。例如，上式中detA=2·3·2=1222课堂练习：考虑高斯消去法的反向替换的运行时间效率类型是多少？236.3平衡查找树二叉查找树是一种重要的数据结构看书p162-163，思考下列问题：1二叉查找树的特点是？2在平均情况下，查找，插入，删除的效率是？3最差情况是一
8、种什么情况？4最差情况效率是多少？24把一个集合变换
