算法导论 14.5 Exercises 答案

14.5-1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
CONSTRUCT-OPTIMAL-BST(root, i, j, fa)
if i == j - 1
name = "d" + i
else
name = "k" + root[i, j]
if fa == 0
print name + "is the root"
else if j < fa
print name + "is the left child of" + " k" + fa
else
print name + "is the right child of" + " k" + fa
if j >= i
CONSTRUCT-OPTIMAL-BST(root, i, root[i, j] - 1, root[i, j])
CONSTRUCT-OPTIMAL-BST(root, root[i, j] + 1, j, root[i, j])

14.5-2

这棵树的结构如图所示,最终最优开销为 3.12

14.5-3

如果直接计算 w(i,j),那么可以发现需要进行 ji+1 次循环才能完成。

因此,计算总和次数为

l=1ni=1nl+1(i+l1)i+1=l=1ni=1nl+1l=l=1nl(nl+1)=Θ(n3)

最终,程序 OPTIMAL-BST 的时间复杂度仍然为 Θ(n3),只是常数有所增大而已。

14.5-4

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
OPTIMAL-BST(p, q, n)
let e[1 : n + 1, 0 : n], w[1 : n + 1, 0 : n], and root[1 : n, 1 : n] be new tables
for i = 1 to n + 1 // base cases
e[i, i − 1] = qi−1 // equation (14.14)
w[i, i − 1] = qi−1
// 为了避免出错,只有一个非根节点时同样单独处理。
for i = 1 to n
e[i, i] = qi-1 + pi + qi
w[i, i] = e[i, i] + qi-1 + qi
root[i, i] = i
for l = 2 to n
for i = 1 to n − l + 1
j = i + l − 1
e[i, j] = ∞
w[i, j] = w[i, j − 1] + pj + qj // equation (14.15)
// 修改之处。
for r = root[i, j - 1] to root[i + 1, j] // try all possible roots r
t = e[i, r − 1] + e[r + 1, j] + w[i, j] // equation (14.14)
if t < e[i, j] // new minimum?
e[i, j] = t
root[i, j] = r
return e and root

对于修改之处的 for 循环,当求取 w[i,j] 的值时,r 取遍的值在区间 [root[i,j1],root[i+1,j]]。到了下一轮迭代,也就是求取 w[i+1,j+1] 时,那么此时 r 取遍的区间在于 [root[i+1,j],root[i+2,j]]。可以发现这两个区间,恰好是首尾相接的,只有 root[i,j+1] 被使用了两次。

因此,关于 ifor 循环,其内部关于 rfor 循环区间是两两首位相接的,因此关于 ifor 循环的时间复杂度为 Θ(n)。再算上外部关于 lfor 循环,最终这个程序的时间复杂度为 Θ(n2)