《计算机算法基础》第三版,课后习题答案

4.2在下列情况下求解递归关系式

T(n)= g(n)

2T(n/2) f(n)n 足够小 否则

当①n=2kg( n)=0 (1)和 f(n)=0(n); ② n=2kg( n)=0 (1)和 f(n)=0 (1)。 解：

T( n)二T(2k)=2 T(2k-1)+f(2k)=2(2 T(2k-2)+f(2k-1)) +f(2k) =22T(2k-2)+21f(2k-1)+ f(2k)

_

5 5

=2kT (1) +2k-1f (2) +2k-2f

(22)+,+20f(2k)kk-1k-220k=2g( n)+ 2f (2)+2f (2)+,+2f (2)①当 g(n)=0 (1)和 f(n)=0(n)时，

1 / 38

不妨设g(n)=a, f(n)=bn, a, b为正常数。则

T( n)二T(2k)二 2ka+ 2k-1*2b+2k2*22b+,+20*2kb =2ka+kb2k

二an+bnlog

2n=0( nlog 2n) ②当g(n)=0 (1)和 f(n)=0 (1)时，

不妨设g(n)二c, f(n)二d, c, d为正常数。则 T( n)二T(2k)二c2k+ 2k-1d+2k-d+,+20d=c2k+d(2k-1) =(c+d) n-d=0( n)

4.3根据教材中所给出的二分检索策略，写一个二分检索的递归过程。 Procedure BINSRCH(A, low, high, x, j) in teger mid if low < high then mid J (low high)/2 if x=A(mid) the n j

J

mid; en dif

if x>A(mid) then BINSRCH(A, mid+1, high, x, j); en dif x

end BINSRCH

2 / 38

4.5作一个三分”检索算法。它首先检查n/3处的元素是否等于某个x的 值，然后检查2n/3处的元素；这样，或者找到x,或者把集合缩小到原来的1/

3。\分析此算法在各种情况下的计算复杂度。 Procedure ThriSearch(A, x, n, j) in teger low, high, p1, p2 low J1; high —n while low < high do

p1 J (2low high)/3 ; p2 — (low 2high)/3 case:x=A(p1):

j J p1; return:x=A(p2): j J p2; return:xA(p2): low J p2+1:else:

low J p1 + 1; high J p2l

end case repeat j J0

end ThriSearch T(n)= g(n)

T(n/3) f(n)n 足够小 否则

3 / 38