2010-2011-2《算法分析》ppt-5变治法.ppt

《2010-2011-2《算法分析》ppt-5变治法.ppt》由会员分享，可在线阅读，更多相关《2010-2011-2《算法分析》ppt-5变治法.ppt（58页珍藏版）》请在装配图网上搜索。

1、变治法,基本思想,变换！ （1）把问题的实例变得更容易求解。 （2）对实例进行求解。 主要类型： （1）实例简化 （2）改变表现 （3）问题转化,预排序,在问题求解之前，先进行排序，然后在求解问题。 例1 检验数组中元素的唯一性 （1）蛮力法 ，扫描统计，O(n2) （2）先排序，再扫描统计，O(nlogn),预排序,例2 模式统计 在一个给定的序列中找到出现次数最多的一个模式。 比如：英文单词 （1）蛮力法 ，扫描统计，O(n2) （2）先排序，再扫描统计，O(nlogn),预排序,例3 查找问题： 在一个数组中是否存在某个给定的数。 （1）蛮力法，O(n) （2）先排序，后查找， 排序：O

2、(nlogn)，查找：O(log2n) 合计：O(nlogn),高斯消去法,二元联立方程： a11x+a12y=b1 a21x+a22y=b2 a11x+a12y=b1 (a21x+a22y)*(a11/a21)=b2*(a11/a21) a11x+a12y=b1 a11x +(a22 * a11/a21) y=b2*(a11/a21),高斯消去法,一般的n个方程的n元联立方程组： a11x1+ a12x2 + + a1nxn = b1 a21x1+ a22x2 + + a2nxn = b2 an1x1+ an2x2 + + annxn = bn,高斯消去法,a11x1+ a12x2 + +

3、a1nxn = b1 a22x2 + + a2nxn = b2 annxn = bn,高斯消去法,初等变换： （1）交换方程组中两个方程的位置 （2）把一个方程替换为它的非零倍。 （3）把一个方程替换为它和另一个方程倍 数之间的和或差。 举例：p156,高斯消去法,GaussElimination(A1n,1n,b1n) for j=1 to n Aj,n+1=bj for i=1 to n-1 for j=i+1 to n for k=i to n+1 Aj,k=Aj,k-AI,k*Aj,i/Ai, I ,高斯消去法,上面代码的问题： （1） 可能有系数是0 （2）最内的循环存在重复计算现象

4、，效率低。 （3）误差累计，有除法，计算机只能表示小数点后面的有限位数,BetterGaussElimination(A1n,1n,b1.n) for i=1 to n Ai,n+1=bi for i=1 to n-1 pivotrow=i for j=i+1 to n if |Aj,i|Apivotrow,i| pivotrow=j for k=i to n+1 swap(Ai,k,Apivotrow,k) for j=i+1 to n temp=Ai,k/Ai,i for k=i to n+1 Aj,k=Aj,k-Ai,k*temp ,高斯消去法,时间复杂度：O(n3) 其他应用： （1）

5、LU分解 （2）计算矩阵的逆 （3）计算矩阵的行列式,平衡查找树,AV L树： G.M.Adelson-Velsky 和E.M.Landis 定义：一棵AVL树是一棵二叉查找树，其中每个节点的平衡因子定义为该节点左子树和右子树的高度差，这个平衡因子要么是0，要么是+1，或者-1 P163,AV L树的调整,（1）右单转 （2）左单转 （3）左右双转 （4）右左双转 P164,排序,分析排序！,排序的时间复杂度分析,排序的最好复杂度为什么是：O(n log n)? 有3个互不相等元素组成的序列： k1，k2，k3 对此3个元素进行排序，唯一的方法是两两进行比较。 比较的结果两种：大于，小于。,排

6、序的时间复杂度分析,两两比较结果，形成一颗比较二叉树，二叉树的高度就是比较的次数。,排序的时间复杂度分析,因为k1，k2，k3互不相等，它们之间只可能有下列6种关系：k1k2k3；k1 k3 k2；k3k1k2；k2k1k3；k2k3 k1；k3k2k1 为什么是6种结果？N个元素是几种结果？,排序的时间复杂度分析,二叉树的性质：叶子数量（记为U）和树高度(记为H)的关系。 H=log 2 U 就是说：有U个叶子的二叉树至少有H 高度。 而比较二叉数的叶子数为 : N! 所以它的高度至少是: log 2 N!,排序的时间复杂度分析,建立一个模型：即有一个含有m= n!个元素的集合A ，甲从中任

7、取一个，让乙来猜，但允许乙提出k个“是”或“非”问题。问在最坏情况下k应该是多少？ 乙提出第1个“是”或“非”问题，可将集合A分为A1（1）和A2（1）两个子集合，其中必有一个集合（设为A1（1） ），它包含的元素个数（用A1（1）来表示）不少于，即 A1（1） m/2,排序的时间复杂度分析,若甲所取的元素正好在A1（1），乙提出第2个“是”或“非”问题后将集合A1（1）分为A2（1）和A2（2），其中之一设为A2（1）有 A1（2）A1（1） m /2 2 依此类推有 A1（k） m /2 k k必须足够大，使得 m / 2 k 1,排序的时间复杂度分析,则已可在最坏情况下通过k次提问题找到

8、所要寻找的元素，即猜到A取得元素，这里“是”或“非”问题相当于作一次比较结果两种状态。 2k=n! k=log2n! 由此得到下述结论： 任何一个借助“比较”进行分类的算法，在最坏情况下所需的比较次数至少为log2n!。,排序的时间复杂度分析,根据Stirling公式: n!=(2n)1/2(n/e)n log2n!= log2(2n)1/2(n/e)n= n(log2 n-log2e)+1/2log2 n+1/2log22) =O(n log2 n),排序的时间复杂度分析,也就是说任何排序法在最坏情况下所需要的比较次数不的少于O(n log2n)。,堆排序,堆是一个几乎完全的二叉树每一个节点

9、都满足：如果v和p(v)分别是节点和它的父节点，那么p(v)=v. 堆方便如下两个运算：插入元素和寻找最大元素。 堆的特征：沿着每条从根到叶子的路径，元素的值以非升序排列。 堆可以用数组这个数据结构实现。,堆排序,H10=15,12,11,7,6,5,4,2,1,0,父节点在数组中的下标与子节点下标的关系？,堆排序,假如个节点的地址入n,则它的“父亲”节点的地址应为n/2。它的左”儿子”节点的地址”儿子”为2n,右“儿子”节点的地址为2n+1。,堆排序,堆的运算： Sift-up 假定对于某个i1,Hi变成了键值大于它父节点键值的元素，这样不符合堆的特性，其他节点符合堆的条件，需要调整。 把H

10、i沿着从Hi到根节点的唯一一条路径，把Hi移到合适它的位置上，每次向上移动一步，都把Hi和它当前的父节点比较。 例子：P75,图 4 .1 -图4.2,堆排序,C代码： void Sift-up( int j, int Hn) int done=0,k=j,temp; if( j=1) return ; do if (HkHk/2) temp=Hk/2;Hk/2=Hk; Hk=temp; else done=1; k=k/2; while(k=1| done); ,堆排序,为什么这样调整后，满足堆的条件？,堆排序,Sift-down: 假定对于某个i图4.3,堆排序,C代码： void Sif

11、t-down( int j, int Hn) int done=0,k=j,temp; if( jn ) return ; do k=k*2; if(k+1Hk ) k=k+1; if (Hk/2n| done); ,堆排序,在堆中插入一个元素x，先把堆的大小假加1，然后将x添加到堆最下面的最右边，然后调整堆。 由于堆的元素个数为n，则堆的高度为log n，所以在堆中插入一个元素的时间是：O( log n),堆排序,C代码： void insert(int Hn,int x,int NewHn+1) int j; for (j=0;jn;j+) NewHj=Hj; NewHn=x; Sift-

12、up(NewH,n); ,堆排序,要从大小为n的堆中删除元素Hk，可先用Hn替换Hk，然后将堆大小减1，并利用函数Sift-up或Sift-down调整堆。显然，删除一个元素的时间是O( log n).,堆排序,void delete(int Hn,int j,int newHn-1) int x=Hj,y=Hn-1,k; for(k=0;k=x) Sift-up(newH,j); else Sift-down(newH,k); ,堆排序,给出一个有n个元素的数组A1n，要创建一个包含这些元素的堆是：从空的堆开始，不断插入每一个元素，直到A完全被转移到堆中为止。 因为插入第j 个元素用时 O(

13、log j)，因此，用这种方法创建堆的时间复杂性为： O(n log n) 但是，存在一种能在(n)的时间内，用n 个元素建立一个堆。,堆排序,堆排序,堆排序,堆排序,void MakeHeap(int An) int j; for (j=n/2;j0;j-) Sift-down(A,j); ,堆排序,计算算法MakeHeap的运行时间： T是一个完全二叉数，设它的高是k=log n, 对于数的第j层的一个节点，它重复执行Sift-down的次数最多是k-j。 因此，在第j 层上正好有 2 j 个节点，所以，循环执行的总次数上界是：,堆排序,用堆的思想对数组An进行排序，步骤： 1、首先把An

14、变成堆。 2、交换An与A1 3、用Sift-down调整A1n-1,堆排序,C: Void HeapSort(int An) int j,temp; MakeHeap(A); for(j=n;j=2;j-) temp=A0;A0=Aj;Aj=temp; Sift-down(1,Aj-1); ,堆排序,时间复杂度： 建立堆用O(n), Sift-down运行用O(log n),因此，堆排序时间复杂度： O(n log n) 空间复杂度：O(1),多项式求值,假设有n+2个实数，a0,a1,an 和x 的序列，求多项式的值： 直接方法，一项一项求，乘法次数： n+(n-1)+(n-2)+1=n(

15、n+1)/2,多项式求值,Horner规则： 假设已知， 那么，求 ：,多项式求值,double Horner(double x,double an+1) double p=an; int j; for(j=0;jn;j+) p=x*p+an-1-j; return p; 复杂度：n次乘法，n次加法。,二进制幂,求an ? 1）暴力法:a*a*a 2）n=(bkbib0)2 ,其中bi =0/1, bk =1 n= bk *2k+ bk-1 *2k-1+ + b0 *20 如果给定右边的表达式，如何求n? P178 3） an = a bk *2k+ bk-1 *2k-1+ + b0 *20,

16、二进制幂,a13 =a1*23+1*22+0*21+1 /Horner规则 =a(1*22+1*21+0 )*21+1 =a(1*21+1)*21+0 )*21+1 =a(1*21+1)*21+0 21 * a /计算过程 =a(1*21+1)*21 *2 * a =a(1*21+1) 22 * a =a2 * a 22 * a /5次乘法,二进制幂,LeftRightBinaryExponentiantion(a,b(n) p=a; for(j=k;j=0;j-) p=p*p; if b(j)=1 then p=p*a; return p; ,二进制幂,从右至左二进制幂见P179,问题化简,求最小公倍数： （M，N） 可以把M,N的所有公共质因数的积乘以M的不在N中的质因数。 Lcm(m,n)=m*n/gcd(m,n),计算图中的路径数量,1）得到图的邻接矩阵A。 2）计算Ak 3）得到长度为k的路径数,线性规划,例子:P 183， 投资问题 一般描述： 使 c1x1+cnxn 最大化 约束条件是： ai1x1+ainxn =0 x可以是实数,整数规划问题,x是整数 比如：背包问题,农夫，狼，羊，白菜的问题,P186,