算法分析习题课--第4章

1、算法分析习题课第4章作业 第四章：2 、3、 5、 6、10、11、23P99 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-1

2、f(2)+2k-2f(22)+20f(2k) g(n)=O(1)和f(n)=O(n)当当g(n)=O(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) =c1*(n/2) * log(n

3、/2)=n2 f(n) = c2 * n T(n) = 2T(n/2) + f(n) =c1*nlogn+c2*n=(c1+c2)*nlogn = c*nlogn猜想也可以运用技巧 T(1) = 1 T(n) = 2*T(n/2) + n T(n)/n = T(n/2)/(n/2) +1 n=2K T(n)/n = k T(n) = nlogng(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)

4、证明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) 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 BINSRCHP99-5 作一个作一个“三分三分”检索算法，它首检索算法，它首先检查先检查n/3处

5、的元素是否等于某个处的元素是否等于某个x的值，然后检查的值，然后检查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

6、:xA(p2): low p2+1:else: lowp1+1; highp2-1end case repeatj0end ThrSearch实例运行1p1 (high+2low)/3 p2 (2high+low)/3 /round1，231，2 三元查找树的高度? 数学归纳法 递推关系式实例运行 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 3，694，51，27，8H(n)=H(n/3)+1H(2)=1H(1)=1时间复杂性 以比较为基本运算， 查找成功，内结点，次数=路径长度+1， 查找失败，外结点，次数=路径长度最好平均平均成功O(1)?O(log3(n)O(lo

7、g3(n)失败O(log3(n)O(log3(n)O(log3(n) 观察：只与外部结点相邻的内结点 有3个外部结点 有2个外部结点，增加1个虚拟的外部结点，结果是I(n)不变，E(n)增加三元比较树的E(n) 和 I(n)d E(n1) = E(n) 3d 3 + d = E(n) 2d 3 I(n1) = I(n) d 2I(n 1) = 2I(n) 2d E(n1) 2I(n 1) + 3 = E(n) 2I(n) E(1) 2I(1) = 3 E(n) 2I(n) = 3n 路径总长度的关系：I(n)= E (n) 3n/2三分是否比二分更好？361425798H(n)H(n/3)H(

8、n)=H(n/3)+2H(2)=2H(1)=1树高度接近树高度接近2log3nP99 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，而且它的两个儿子都为叶结点（根据二元扩展树的定义，一定存在这样的结点x，且设该结点的层数为h），将结点x及其左右子结点（外结点）从原树中摘除（x替换为外结点）。X此时新树内部结点为k个，则满足：Ek=Ik+2k（1）考察原树的外部路径长度和内部路径长度：Ek+1= Ek-h+

9、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)吗？吗？ 最好情况：最好情况： 对有序文件进行排序对有序文件进行排序 分析分析 归并的次数不会发生变化归并的次数不会发生变化-log(n)次次 归并中比较的次数会发生变化（两个长归并中比较的次数会发生变化（两个长n/2序序列归并）列归并

10、） 最坏情况最坏情况 两个序列交错大小两个序列交错大小 需要比较需要比较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 + 1

11、do Merge(R, i, i + len - 1, i + 2*len - 1, X); i i + 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 MPassprocedure 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;

12、repeatend MSortP99-23 通过手算证明（4.9）和(4.10)式确实能得到C11,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 +A12B21P=(A11+A22)(B11+B22)T=(A11+A12)B22Q=(A21+A22)B11U=(A2

13、1-A11)(B11+B12)R=A11(B12-B22)V=(A12-A22)(B21+B22)S=A22(B21-B11)P=(A11+A22)(B11+B22)T=(A11+A12)B22Q=(A21+A22)B11U=(A21-A11)(B11+B12)R=A11(B12-B22)V=(A12-A22)(B21+B22)S=A22(B21-B11)C12=R+T= A11B12-A11B22 +A11B22+A12B22= A11B12 +A12B22C21=Q+S= A21B11+A22B11 +A22B21-A22B11= A21B11 +A22B21C22=P+R-Q+U=(A11+A22)(B11+B22)+A11(B12+B22)-(A21+A22)B11 +(A21-A11)(B11+B12)= A11B11+A