《计算机算法基础》课后答案

计算机算法分析—习题课 第四章：2 、3 、5 、6 、1 0 、1 1 、2 3 P99-2 在下列情况下求解4.1节的递归关系式T(n)= ()2(/2) () g n n Tn fn ⎧⎨⎩ 足够小＋否则 当①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 +bn lo g2n =O(n lo g2n ) 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 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(lo g3(n )),O(lo g3(n )) က最好，平均，最坏 က失败: ကO(lo g3(n )),O(lo g3(n )),O(lo g3(n )) က最好，平均，最坏 P99-6 对于含有n 个内部结点的二元树，证明 E=I+2n 其中，E，I分别为...