计算机算法基础课后答案

计算机算法分析—习题课

第四章：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 x>A(mid) then

BINSRCH(A, mid+1, high, x, j); endif

if x

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(p2): low ←p2+1 :else: low←p1+1; high←p2-1 end case repeat