《计算机算法基础+》完整第三版课后习题答案.doc
文本预览下载声明
上机实验?书上121页?5。2?5。3?书上151?6。1?6。3?6。6他说搞懂这几题和实验就没问题了
当①n=2k g(n)= O(1)和f(n)= O(n);
②n=2k g(n)= O(1)和f(n)= O(1)。
解: T(n)=T(2k)=2 T(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)=a,f(n)=bn,a,b为正常数。则
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)=c,f(n)=d,c,d为正常数。则
T(n)=T(2k)=c2k+ 2k-1d+2k-2d+…+20d=c2k+d(2k-1)
=(c+d)n-d= O(n)
4.3根据教材中所给出的二分检索策略,写一个二分检索的递归过程。
Procedure BINSRCH(A, low, high, x, j)
integer mid
if low≤high then
mid←
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
4.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≤high do
p1← ; p2←
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
T(n)=
g(n)= O(1) f(n)= O(1)
成功:
O(1), O(log3(n)), O(log3(n))
最好, 平均, 最坏
失败:
O(log3(n)), O(log3(n)), O(log3(n))
最好, 平均, 最坏
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及其左右子结点(外结点)从原树中摘除,生成新二元扩展树。此时新二元扩展树内部结点为k个,则满足Ek=Ik+2k,考察原树的外部路径长度为Ek+1= Ek-(h-1)+2h,内部路径长度为Ik+1=Ik+(h-1),所以Ek+1= Ik+2k+h+1= Ik+1+2k+2= Ik+1+2(k+1),
综合①②③知命题成立。
4.10过程MERGESORT的最坏情况时间是O(nlogn),它的最好情况时间是什么?能说归并分类的时间是Θ(nlogn)吗?
最好情况:是对有序文件进行排序。
分析:在此情况下归并的次数不会发生变化----log(n)次
归并中比较的次数会发生变化(两个长n/2序列归并)
最坏情况
两个序列交错大小,需要比较n-1次
显示全部