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

变治法,基本思想,变换！（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(nlogn)，查找：O(log2n)合计：O(nlogn),高斯消去法,二元联立方程：a11x+a12y=b1a21x+a22y=b2a11x+a12y=b1(a21x+a22y)*(a11/a21)=b2*(a11/a21)a11x+a12y=b1a11x+(a22*a11/a21)y=b2*(a11/a21),高斯消去法,一般的n个方程的n元联立方程组：a11x1+a12x2+a1nxn=b1a21x1+a22x2+a2nxn=b2an1x1+an2x2+annxn=bn,高斯消去法,a11x1+a12x2+a1nxn=b1a22x2+a2nxn=b2annxn=bn,高斯消去法,初等变换：（1）交换方程组中两个方程的位置（2）把一个方程替换为它的非零倍。（3）把一个方程替换为它和另一个方程倍数之间的和或差。举例：p156,高斯消去法,GaussElimination(A1n,1n,b1n)forj=1tonAj,n+1=bjfori=1ton-1forj=i+1tonfork=iton+1Aj,k=Aj,k-AI,k*Aj,i/Ai,I,高斯消去法,上面代码的问题：（1）可能有系数是0（2）最内的循环存在重复计算现象，效率低。（3）误差累计，有除法，计算机只能表示小数点后面的有限位数,BetterGaussElimination(A1n,1n,b1.n)fori=1tonAi,n+1=bifori=1ton-1pivotrow=iforj=i+1tonif|Aj,i|Apivotrow,i|pivotrow=jfork=iton+1swap(Ai,k,Apivotrow,k)forj=i+1tontemp=Ai,k/Ai,ifork=iton+1Aj,k=Aj,k-Ai,k*temp,高斯消去法,时间复杂度：O(n3)其他应用：（1）LU分解（2）计算矩阵的逆（3）计算矩阵的行列式,平衡查找树,AVL树：G.M.Adelson-Velsky和E.M.Landis定义：一棵AVL树是一棵二叉查找树，其中每个节点的平衡因子定义为该节点左子树和右子树的高度差，这个平衡因子要么是0，要么是+1，或者-1P163,AVL树的调整,（1）右单转（2）左单转（3）左右双转（4）右左双转P164,排序,分析排序！,排序的时间复杂度分析,排序的最好复杂度为什么是：O(nlogn)?有3个互不相等元素组成的序列：k1，k2，k3对此3个元素进行排序，唯一的方法是两两进行比较。比较的结果两种：大于，小于。,排序的时间复杂度分析,两两比较结果，形成一颗比较二叉树，二叉树的高度就是比较的次数。,排序的时间复杂度分析,因为k1，k2，k3互不相等，它们之间只可能有下列6种关系：k1k2k3；k1k3k2；k3k1k2；k2k1k3；k2k3k1；k3=n!k=log2n!由此得到下述结论：任何一个借助“比较”进行分类的算法，在最坏情况下所需的比较次数至少为log2n!。,排序的时间复杂度分析,根据Stirling公式:n!=(2n)1/2(n/e)nlog2n!=log2(2n)1/2(n/e)n=n(log2n-log2e)+1/2log2n+1/2log22)=O(nlog2n),排序的时间复杂度分析,也就是说任何排序法在最坏情况下所需要的比较次数不的少于O(nlog2n)。,堆排序,堆是一个几乎完全的二叉树每一个节点都满足：如果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变成了键值大于它父节点键值的元素，这样不符合堆的特性，其他节点符合堆的条件，需要调整。把Hi沿着从Hi到根节点的唯一一条路径，把Hi移到合适它的位置上，每次向上移动一步，都把Hi和它当前的父节点比较。例子：P75,图4.1-图4.2,堆排序,C代码：voidSift-up(intj,intHn)intdone=0,k=j,temp;if(j=1)return;doif(HkHk/2)temp=Hk/2;Hk/2=Hk;Hk=temp;elsedone=1;k=k/2;while(k=1|done);,堆排序,为什么这样调整后，满足堆的条件？,堆排序,Sift-down:假定对于某个i图4.3,堆排序,C代码：voidSift-down(intj,intHn)intdone=0,k=j,temp;if(jn)return;dok=k*2;if(k+1Hk)k=k+1;if(Hk/2n|done);,堆排序,在堆中插入一个元素x，先把堆的大小假加1，然后将x添加到堆最下面的最右边，然后调整堆。由于堆的元素个数为n，则堆的高度为logn，所以在堆中插入一个元素的时间是：O(logn),堆排序,C代码：voidinsert(intHn,intx,intNewHn+1)intj;for(j=0;j0;j-)Sift-down(A,j);,堆排序,计算算法MakeHeap的运行时间：T是一个完全二叉数，设它的高是k=logn,对于数的第j层的一个节点，它重复执行Sift-down的次数最多是k-j。因此，在第j层上正好有2j个节点，所以，循环执行的总次数上界是：,堆排序,用堆的思想对数组An进行排序，步骤：1、首先把An变成堆。2、交换An与A13、用Sift-down调整A1n-1,堆排序,C:VoidHeapSort(intAn)intj,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(logn),因此，堆排序时间复杂度：O(nlogn)空间复杂度：O(1),多项式求值,假设有n+2个实数，a0,a1,an和x的序列，求多项式的值：直接方法，一项一项求，乘法次数：n+(n-1)+(n-2)+1=n(n+1)/2,多项式求值,Horner规则：假设已知，那么，求：,多项式求值,doubleHorner(doublex,doublean+1)doublep=an;intj;for(j=0;j=0;j-)p=p*p;ifb(j)=1thenp=p*a;returnp;,二进制幂,从右至左二进制幂见P179,问题化简,求最小公倍数：（M，N）可以把M,N的所有公共质因数的积乘以M的不在N中的质