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

华科大

上机实验 书上121页 5。2 5。3 书上151 6。1 6。3 6。6 他说搞懂这几题和实验就没问题了

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

g(n)n足够小

T(n)=

否则 2T(n/2) f(n)

当①n=2k g(n)= O(1)和f(n)= O(n);

k

②n=2g(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)

2k-21k-1k

=2T(2)+2 f(2)+ f(2) =

=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← (low high)/2

if x=A(mid) then j←mid; endif

if x>A(mid) then BINSRCH(A, mid+1, high, x, j); endif if x<A(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

Word文档免费下载Word文档免费下载:《计算机算法基础》第三版_课后习题答案 (共11页,当前第1页)

你可能喜欢

  • 计算机基础答案
  • 算法设计与分析期末考试题
  • 递归算法
  • 高中物理图像专题
  • 算法设计技巧与分析

《计算机算法基础》第三版_课后习题答案相关文档

最新文档

返回顶部