算法导论14.5 Exercises 答案

发表于 更新于 分类于 阅读次数： 本文字数： 681 阅读时长 ≈ 1 分钟

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

因此，计算总和次数为

\(\begin{aligned} \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)\\ &=\Theta(n^3) \end{aligned}\)

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

\(\star\) 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\)取遍的值在区间\([\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循环的时间复杂度为\(\Theta(n)\)。再算上外部关于\(l\)的for循环，最终这个程序的时间复杂度为\(\Theta(n^2)\)。