算法导论 14.5 Exercises 答案

14.5-1

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)$，那么可以发现需要进行 $j-i+1$ 次循环才能完成。

因此，计算总和次数为

$\begin{array}{rl}\sum _{l=1}^n\sum _{i=1}^{n-l+1}(i+l-1)-i+1& =\sum _{l=1}^n\sum _{i=1}^{n-l+1}l\\ & =\sum _{l=1}^{n}l\cdot (n-l+1)\\ & =\mathrm{\Theta }(n^3)\end{array}$

最终，程序 OPTIMAL-BST 的时间复杂度仍然为 $\mathrm{\Theta }(n^3)$，只是常数有所增大而已。

$\star$ 14.5-4

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$ 取遍的值在区间 $[\text{root}[i,j-1],\text{root}[i+1,j]]$。到了下一轮迭代，也就是求取 $w[i+1,j+1]$ 时，那么此时 $r$ 取遍的区间在于 $[\text{root}[i+1,j],\text{root}[i+2,j]]$。可以发现这两个区间，恰好是首尾相接的，只有 $\text{root}[i,j+1]$ 被使用了两次。

因此，关于 $i$ 的 for 循环，其内部关于 $r$ 的 for 循环区间是两两首位相接的，因此关于 $i$ 的 for 循环的时间复杂度为 $\mathrm{\Theta }(n)$。再算上外部关于 $l$ 的 for 循环，最终这个程序的时间复杂度为 $\mathrm{\Theta }(n^2)$。