《算法分析习题课第4章方案ppt课件.ppt》由会员分享，可在线阅读，更多相关《算法分析习题课第4章方案ppt课件.ppt（35页珍藏版）》请在三一办公上搜索。
1、算法分析习题课第4章,作业,第四章：2 、3、 5、 6、10、11、23,P99 4.2,解题思路,猜想T(n)是多少？从特殊情况入手，使用试探或蛮力法解开方程题目给出的是 O()表示的界，结论也应该是类似的界证明猜想,蛮力法,设n=2k则:T(n)=T(2k)=2T(2k-1)+f(2k)=2(2 T(2k-2)+f(2k-1) +f(2k)=22T(2k-2)+21 f(2k-1)+ f(2k)=2kT(1)+2k-1f(2)+2k-2f(22)+20f(2k)=2kg(n)+ 2k-1f(2)+2k-2f(22)+20f(2k),g(n)=O(1)和f(n)=O(n),当g(n)=O(
2、1)和f(n)=O(n)时不妨设g(n)=a，f(n)=bn+c，则：T(n)=T(2k)= 2ka+ 2k-1*2b+2k-2*22b+20*2kb + c*(2k-1+2k-2+20) =2ka+kb2k +(2k-1)c=(a+c)n c + bnlog2n = O(nlog2n),证明T(n)= O(nlogn),n足够小时，T(n)=g(n)=O(1)=O(nlogn) 显然成立假设n=n1时， T(n/2) =n2 f(n) = c2 * nT(n) = 2T(n/2) + f(n) =c1*nlogn+c2*n=(c1+c2)*nlogn = c*nlogn,猜想也可以运用技巧,
3、T(1) = 1T(n) = 2*T(n/2) + nT(n)/n = T(n/2)/(n/2) +1n=2K T(n)/n = kT(n) = nlogn,g(n)=O(1)和f(n)=O(1),当g(n)=O(1)和f(n)=O(1)时，不妨设g(n)=c，f(n)=d，则：T(n)=T(2k)=c2k+2k-1d+2k-2d+20d=c2k+d(2k-1)=(c+d) n-d=O(n),证明T(n)= O(n),n足够小时，T(n)=g(n)=O(1)=O(n) 显然成立假设n=n1时， T(n/2) =n2 f(n) = c2 T(n) = 2T(n/2) + f(n) =c1*n+c
4、2 =O(n),P99-3,根据4.2节开始所给出的二分检索策略，写一个二分检索的递归过程。,Procedure BINSRCH(A, low, high, x, j)integer mid; if (low high) then j0; return; endif mid (low+high)/2 if x=A(mid) then jmid; endif / 教材case 更简洁直观if xA(mid) then BINSRCH(A, mid+1, high, x, j);endifend BINSRCH,P99-5,作一个“三分”检索算法，它首先检查n/3处的元素是否等于某个x的值，然后检
5、查2n/3处的元素。这样，或者找到x，或者把集合缩小到原来的1/3。分析此算法在各种情况下的计算复杂度。,Procedure TriSearch(A, x, n, j)integer low, high, p1, p2;low1; highn;while lowhigh dop1 (high+2low)/3 p2 (2high+low)/3 /roundcase:x=A(p1): jp1; return:x=A(p2): jp2; return:xA(p2): low p2+1:else: lowp1+1; highp2-1end case repeatj0end ThrSearch,实例运行
6、,p1 (high+2low)/3 p2 (2high+low)/3 /round,三元查找树的高度?数学归纳法递推关系式,实例运行 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 ,H(n)=H(n/3)+1H(2)=1H(1)=1,时间复杂性,以比较为基本运算，查找成功，内结点，次数=路径长度+1，查找失败，外结点，次数=路径长度,观察：只与外部结点相邻的内结点有3个外部结点有2个外部结点，增加1个虚拟的外部结点，结果是I(n)不变，E(n)增加,三元比较树的E(n) 和 I(n),d,E(n1) = E(n) 3d 3 + d = E(n) 2d 3I(n1) = I
7、(n) d 2I(n 1) = 2I(n) 2d E(n1) 2I(n 1) + 3 = E(n) 2I(n)E(1) 2I(1) = 3E(n) 2I(n) = 3n路径总长度的关系：I(n)= E (n) 3n/2,三分是否比二分更好？,3,H(n),H(n/3),H(n)=H(n/3)+2H(2)=2H(1)=1,树高度接近2log3n,P99 4.6,对于含有n个内部结点的二元树，证明E=I+2n其中，E，I分别为外部和内部路径长度。证明：数学归纳法当n=1时，易知E=2，I=0，所以E=I+2n成立；假设n=k(k0)时，E=I+2n成立；,则当n=k+1时，确定某个内结点x，而且它
8、的两个儿子都为叶结点（根据二元扩展树的定义，一定存在这样的结点x，且设该结点的层数为h），将结点x及其左右子结点（外结点）从原树中摘除（x替换为外结点）。,此时新树内部结点为k个，则满足：Ek=Ik+2k（1）考察原树的外部路径长度和内部路径长度：Ek+1= Ek-h+2(h+1) （2）Ik+1=Ik+h（3）综合（1）（2）（3）式：Ek+1= Ik+2k+h+2 = Ik+1- h+2k+h+2= Ik+1+2(k+1)故命题成立。,P99-10,过程MERGESORT的最坏情况时间是O(nlogn)，它的最好情况时间是什么？能说归并分类的时间是(nlogn)吗？,最好情况：对有序文件进
9、行排序分析归并的次数不会发生变化-log(n)次归并中比较的次数会发生变化（两个长n/2序列归并）最坏情况两个序列交错大小需要比较n-1次最好情况一个序列完全大于/小于另一个序列比较n/2次差异都是线性的，不改变复杂性的阶最好情况也是nlog(n), 平均复杂度nlog(n)。,P99-11,写一个“由底向上”的归并分类算法，从而取消对栈空间的利用。,procedure MPass(R, n, len, X)integer n, len, i;i 1;while i n 2 * len + 1do Merge(R, i, i + len - 1, i + 2*len - 1, X); i i
10、+ 2*len;repeatif i+len1 n then Merge(R, i, i+len-1, n, X）else for j = i to n do X(j)R(j)endifend MPass,rocedure MSort(R, n)/ 直接两路合并排序 算法，X是辅助文件，其记录结构与R相同integer len, n;len1;while len n doMPass(R, n, len, X);len2 * len;MPass(X, n, len, R);len2 * len;repeatend MSort,P99-23,通过手算证明（4.9）和(4.10)式确实能得到C11,
11、C12,C21和C22的正确值。,C11=P+S-T+V=(A11+A22)(B11+B22) +A22(B21-B11) -(A11+A12)B22 +(A12-A22)(B21+B22)=A11B11+A22B11+A11B22+A22B22 +A22B21-A22B11 -A11B22-A12B22 +A12B21+ A12B22-A22B21-A22B22=A11B11 +A12B21,C12=R+T= A11B12-A11B22 +A11B22+A12B22= A11B12 +A12B22C21=Q+S= A21B11+A22B11 +A22B21-A22B11= A21B11 +A
12、22B21,C22=P+R-Q+U=(A11+A22)(B11+B22)+A11(B12+B22)-(A21+A22)B11 +(A21-A11)(B11+B12)= A11B11+A22B11+A11B22+A22B22+ A11B12-A11B22- A21B11-A22B11 +A21B11 +A21B12-A11B11-A11B12=A22B22+A21B12,人有了知识，就会具备各种分析能力，明辨是非的能力。所以我们要勤恳读书，广泛阅读，古人说“书中自有黄金屋。”通过阅读科技书籍，我们能丰富知识，培养逻辑思维能力；通过阅读文学作品，我们能提高文学鉴赏水平，培养文学情趣；通过阅读报刊，我们能增长见识，扩大自己的知识面。有许多书籍还能培养我们的道德情操，给我们巨大的精神力量，鼓舞我们前进。,
