第六章 变治法.ppt

LingJie/GDUT 第6章 变治法 首先是”变“， 将问题的实例变形，变得更容易求解；然后是”治“，对问题的实例进行求解。 Divide and Conquer, Decrease and Conquer, Transform and Conquer 变治法有三个变形: （1）实例化简——同样问题 （2）改变表现——同样实例 （3）问题化简——另一问题 第6章 变治法-基本类型 （1）实例化简——同样问题 6.1 预排序 6.2 高斯消去法 6.3 平衡查找树—AVL树 （2）改变表现——同样实例 6.3 2-3树 6.4 堆和堆排序 6.5 霍纳法则和二进制幂 （3）问题化简——另一问题 6.1 预排序 列表是有序的话，许多关于列表的问题更容易求解。 因此很多问题需要先排序，则该问题的时间效率依赖于排序算法的效率。 回忆前面所学的排序算法： 插入排序最差Θ(n2) 平均 Θ(n2) 最优 Θ(n) 快速排序最差Θ(n2) 平均Θ(1.38nlog2n) 最优Θ(nlog2n) 合并排序最差Θ(nlog2n) 选择排序 Θ(n2) 冒泡排序 Θ(n2) 6.1 预排序 例1、检验数组中元素的唯一性 蛮力法如何做？时间效率是多少？ 如果先排序，则如何检查元素的唯一性？ 只需检查相互紧挨的元素。 PresortElementUniqueness(A[0..n-1]) //先对数组排序再验证唯一性 //输入：数组A //输出：若A没有相等的元素，返回“true”,否则返回“false”. 对数组排序； for i=0 to n-2 do if A[i]=A[i+1] return false return true 6.1 预排序 例2、模式计算 模式：指数组列表中出现次数最多的值。 如{5,1,5,7,6,5,7}中5是模式 所能想到的求模式的方法? 采用排序的思想，先排序后计算相邻接次数最多的等值元素。 时间效率如何？ 6.1 预排序 思考：预排序还可以用在什么方面？ 查找 分析顺序查找和先排序再查找的时间效率 如果要在同一个列表中进行多次查找，在排序上花费时间是值得的？ 6.2 Gauss消去法 科学计算中通常需要解多个变量的方程组，这些方程组当中最简单的是线性方程组，也就是变量的次数均为1次的。 求解线性方程的方法 有利用高斯消元的直接法以及迭代法。 体现的变治的思想： 将方程组变成一个具有特殊性质的方程组(上三角矩阵) 6.2 Gauss消去法 一般的线性方程组是指如下形式的方程组： 6.2 Gauss消去法 分消元过程和回代过程。消元过程将原方程组变为上三角方程组，回代过程得到方程组的解。 6.2 Gauss消去法 6.2 Gauss消去法-伪代码 GaussElimination(A[1..n], b[1..n]) // 输入：系数矩阵A及常数项 b // 输出：方程组的增广矩阵等价的上三角矩阵 for i=1 to n do A[i][n+1] =b[i] for j= i+1 to n do for k = i to n+1 do A[j][k] = A[j][k] – A[i][k]*A[j][i]/A[i][i] 6.2 Gauss消去法-效率分析 基本操作：乘法 执行次数：易见，三重循环 C(n)∈Θ(n3) 6.2.1 Gauss消去法-LU分解 高斯消去法的现代商业实现是以LU分解为基础的。 6.2.1 Gauss消去法-LU分解 记原方程组为 A X =b， A=LU 则原方程组为LUX=b 其求解转化为两个三角形方程组的求解： LY=b —— 下三角方程组 UX=Y ——上三角方程组 6.2.1 Gauss消去法-LU分解 6.2.1 LU分解 一旦的到矩阵A的LU分解，无论对于什么样的右边向量b，我们都可以对方程组Ax=b求解，每次求一个。 LU分解不需要额外的存储空间 6.2.2 矩阵求逆 逆矩阵的定义： 如何求逆矩阵？ 转化为求n个线性方程AXj =bj 6.2.2 矩阵的行列式 n阶矩阵的行列式的计算由递归公式定义： 例如n=3的情形如下： 6.2.2