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