算法-第6章-变治法(李静).ppt

* * * * * * * * * * * * * * * * * * * * * * 7 6 5 8 9 2 8 6 5 7 9 2 8 6 5 7 9 2 8 6 5 7 2 9 8 2 5 7 6 9 * * 算法 HeapBottomUp(H[1…n]) {//用自底向上算法构造一个堆 for(i=n/2;i=1;i--) { k=i; v=H[k]; heap=false; while(!heap 2*k=n) { j= 2*k; if (jn) //存在两个孩子 if (H[j]H[j+1]) j++; //取其中较大的一个孩子 if (v=H[j])//用较大的孩子进行比较 heap= true; else { H[k] = H[j]; k=j;}//将孩子的值给k节点 } H[k] = v; } } * * 最差情况下的算法效率： 设n=2k-1，即树为满树，每一层上节点最多且高度h=k-1 最坏情况下每个位于第i层的键都会移动到叶子层h中。因为移动到下一层要进行两次比较，所以位于第i层的键总共需要2(h-i)次比较： * * 8 2 5 7 6 9 10 8 2 5 7 6 9 10 8 2 5 7 6 9 10 插入操作所需的键值比较次数≤log2n，所以插入的效率属于O(logn) * * 从堆中删除一个元素 只考虑一种最重要的情况：删除根键 根键和堆最后一个键K交换 堆规模减1（删除了一个元素） 树的“堆化”：K沿树向下筛选，验证沿途节点是否满足堆的要求，不满足就将其与较大孩子节点交换，直到满足为止 * * 6 2 5 9 8 1 6 2 5 1 8 9 6 2 5 8 1 6 2 5 1 8 6 2 1 5 8 * * 堆删除的效率 删除的效率取决于交换和堆的规模减1后，树的”堆化“所需的键值比较次数 因为是沿树向下比较，所以它所需的键值比较次数不可能超过堆的高度的两倍。 所以删除的效率 ≤ 2log2n, 属于O(logn) * * 堆排序 J.W.J.Williams发明的堆排序算法分两步走： 构造堆：为一个给定的数组构造一个堆 删除最大键：对剩下的堆应用n-1次根删除操作 效率： 构造堆：O(n) 删除最大键： * * 霍纳法则 * * 霍纳法则 霍纳法则是一个很好的“改变表现”技术的例子 * * 系数 x = 3 2 2 -1 3×2+(-1)=5 3 3×5+3=18 1 3×18+1=55 -5 3×55－5=160 霍纳法则 * * 算法 Horner(p[0…n],x) { //用霍纳法则求一个多项式在一个给定点的值 p = p[n]; for(i=n-1;i =0;i--) p = x*p+p[i]; return p; } * * 霍纳法则 霍纳法则还有一些有用的副产品：该算法在计算P(x)在某一点x0上的值时所产生的中间数字，恰好可以作为P(x)除以x-x0的商的系数，而算法的最后结果，除了等于P(x)以外，还等于这个除法的余数。 这种被称为综合除法。 * * 二进制幂 运用基于“改变表现”的思想，使用指数n的二进制表示计算an： 从左到右处理二进制串 从右到左处理二进制串 设n=bl…bi…b0是在二进制系统中，表示一个正整数n的比特串。所以可以把n通过下面多项式表示： * * 从左到右二进制幂 用霍纳法则计算二进制多项式p(2) //当n≥1，第一个数字总是1 p=1; for(i=l-1;i=0;i--） p=2*p+bi； 相对于an=ap(2) ap=a1; for(i=l-1;i=0;i--） ap=a2*p+bi * * 算法 LRBExp(a,b(n)) {//从左到右二进制幂算法计算an product = a; for(i=l-1;i=0;i--){ product×=product; if(bi==1) product ×= a; } return product; } * * 从右到左二进制幂 因此可以用各项： 的积来计算an * * 算法 RLBExp(a,b(n)) {//从右到左二进制幂算法计算an term=a; //初始化an if(b0==1) product = a; else product = 1; for(i=1;il;i++) { term*=term; if (bi==1) product*=term; } return product; }