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

6.4．①证明算法OBST的计算时间是O(n2)。

②在已知根R(i, j)，0≤i < j≤4的情况下写一个构造最优二分检索树T的算法。证明这样的树能在O(n)时间内构造出来。

解：① 将C中元素的加法看做基本运算，则算法OBST的时间复杂性为：

nn?mnn?m??(R(i?1,j)?R(i,j?1)?1)???(R(i?1,i?m)?R(i,i?m?1)?1)?m?2i?0m?2i?0n?m?2(R(n?m?1,n)?R(0,m?1)?n?m?1)?O(n2)

② Procedure BuildTree(m, n, R, Root)

integer R(n,n), k

TreeNode Root, LR, RR k←R(m,n)

if k≠0 then data(Root)←k,

BuileTree(m, k-1, R, LR), BuileTree(k, n, R, RR)

left(Root)←LR, right(Root)←RR

else data(Root)←m, left(Root)←null, right(Root)←null, endif

end BuildTree

时间复杂性分析：T(n)=c+T(k)+T(n-k-1)，此递推式保证算法的时间复杂性为O(n)，也可从递归的角度出发，递归的次数正是结点的个数，而每次递归时间复杂性为常数，所以算法的时间复杂度也为O(n)。

6.8．给出一个使得DKNAP(算法6.7)出现最坏情况的例子，它使得|Si|=2i, 0≤i

解：取(P1,P2,?,Pi,?)=(W1,W2,?,Wi,?)=(20,21,?,2i-1,?)

P和W取值相同，使支配原则成立，也就是说不会因为支配原则而删除元素；只要说明不会出现相同元素被删除一个的情形，即可知是最坏的情况。可用归纳法证明此结论。

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库《计算机算法基础》第三版_课后习题答案(3)在线全文阅读。