计算机算法基础课后答案.doc

计算机算法分析—习题课 第四章：2 、3、5、6、10、11、23 P99-2 在下列情况下求解4.1节的递归关系式T(n)= ()2(/2) () gnnTnfn??? 足够小＋否则 当①g(n)=O(1)和f(n)=O(n)； ②g(n)=O(1)和f(n)=O(1)。 P99-2递推表达式 设n=2k则: T(n)=T(2k)=2T(2k-1)+f(2k) =2(2 T(2k-2)+f(2k-1)) +f(2k) =22T(2k-2)+21f(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(1)和f(n)=O(n)时 不妨设g(n)=a，f(n)=bn，则： T(n)=T(2k) = 2ka+ 2k-1*2b+2k-2*22b+…+20*2kb =2ka+kb2k =an+bnlog2n=O(nlog2n) 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) P99-3 ??根据2.2节开始所给出的二分检索策略，写一个二分检索的递归过程。 Procedure BINSRCH(A, low, high, x, j) integer mid if low≤highthen mid←?(low+high)/2 ? if x=A(mid) then j←mid; endif if xA(mid) then BINSRCH(A, mid+1, high, x, j); endif if xA(mid) then BINSRCH(A, low, mid-1, x, j); endif else j←0; endif end BINSRCH P99-5 ??作一个“三分”检索算法，它首先检查n/3处的元素是否等于某个x的值，然后检查2n/3处的元素。这样，或者找到x，或者把集合缩小到原来的1/3。分析此算法在各种情况下的计算复杂度。 Procedure ThriSearch(A, x, n, j) integer low, high, p1, p2 low←1; high←n while low≤highdo p1←?(high+2low)/3 ? p2←?(2high+low)/3 ? case :x=A(p1): j←p1; return :x=A(p2): j←p2; return :xA(p1): high←p1-1 :xA(p2): low ←p2+1 :else: low←p1+1; high←p2-1 end case repeat j←0 end ThriSearch 实例运行 { 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 } 361 时间复杂度 ??成功: ??O(1),O(log3(n)),O(log3(n)) ??最好，平均，最坏 ??失败: ??O(log3(n)),O(log3(n)),O(log3(n)) ??最好，平均，最坏 P99-6 对于含有n个内部结点的二元树，证明 E=I+2n 其中，E，I分别为外部和内部路径长度。 证明：数学归纳法 当n=1时，易知E=2，I=0，所以E=I+2n成立； 假设n≤k(k0)时，E=I+2n成立； 此时新树内部结点为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)吗？ ??最好情况： ??对有序文件进行排序 ??分析 ??归并的次数不会发生变化----log(n)次 ??归并中比较的次数会发生变化（两个长n/2序列归并） ??最坏情况 ??两个序列交错大小 ??需要比较n-1次 ??最好情况 ??一个序列完全大于/小于另一个序列 ??比较n/2次 ??差异都是线性的，不改变复杂性的阶 ??最好情况也是nlog(n), 平均复杂度nlog(n)。 P99-11 ??写一个“由底向上”的归并分类算法，从而取消对栈空间的利用。 ??见《数据结构》---第九章P238 算法MPass（R，n，1e