算法导论14.2 Exercises 答案

发表于 更新于 分类于 阅读次数： 本文字数： 1.7k 阅读时长 ≈ 2 分钟

14.2-1

假设这六个矩阵分别为\(A_1,A_2,\dots,A_6\)，那么这\(6\)个矩阵的最优链乘方式为：

\[(A_1A_2)((A_3A_4)(A_5A_6))\]

仅需进行\(2010\)次乘法。

14.2-2

1
2
3
4
5
6
7
8
MATRIX-CHAIN-MULTIPLY(A, s, i, j)
  if i == j
    return A[i]
  if i + 1 == j
    return RECTANGULAR-MATRIX-MULTIPLY(A[i], A[j])
  a = MATRIX-CHAIN-MULTIPLY(A, s, i, s[i, j])
  b = MATRIX-CHAIN-MULTIPLY(A, s, s[i, j] + 1, j)
  return RECTANGULAR-MATRIX-MULTIPLY(a, b)

14.2-3

假设\(\exists c\ge 0,P(n)\ge c\cdot 2^n\)，那么有

\(\begin{aligned} P(n)&=\sum_{k=1}^{n-1} P(k) \cdot P(n-k)\\ &\ge \sum_{k=1}^{n-1} c2^k \cdot c2^{n-k}\\ &=\sum_{k=1}^{n-1} c^22^n\\ &=(n-1)c^2 2^n\\ &\ge c\cdot 2^n \end{aligned}\)

因此有\(P(n)=\Omega(2^n)\)。

14.2-4

将每个子问题视为图上的顶点：\(\forall 1\le i\le j\le n,v_{i,j}\)。那么这些顶点个数一共有\(\dfrac{n(n+1)}{2}\)个。

考虑所有节点\(v_{i,j}\)，那么有

  • 如果\(i=j\)，那么这时\(v_{i,j}\)没有出边，因为没有子问题。
  • 如果\(i< j\)，那么这时\(\forall k,i\le k< j\)，我们都需要解决子问题\((i,k),(k+1,j)\)时的情况，因此各有两条有向边：\((v_{i,j},v_{i,k}),(v_{i,j},v_{k+1,j})\)。

最终，这个子问题图的边数为：

\[\sum_{i=1}^n\sum_{j=i}^n 2(j-i)=\dfrac{n^3-n}{3}\]

14.2-5

由于这里是计算\(R(i,j)\)的总和次数，那么我们可以换另外一种角度思考：计算\(m[i',j']\)时，有多少个其它表项被访问过，可以设其为\(S(i',j')\)？

如果计算\(m[a,b]\)时访问了表项\(m[c,d]\)，那么这次访问为\(R(c,d)\)贡献了\(1\)，为\(S(a,b)\)也贡献了\(1\)，两者是对等的。因此有

\[\sum_{i=1}^n\sum_{j=i}^n R(i,j)=\sum_{i'=1}^n\sum_{j'=i'}^n S(i',j')\]

简化了问题后，摘录MATRIX-CHAIN-ORDER的代码，可以看到只有在第\(9\)行访问了两次非m[i, j]的元素：m[i, k], m[k + 1,]。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
MATRIX-CHAIN-ORDER(p, n)
  let m[1 : n, 1 : n] and s[1 : n − 1, 2 : n] be new tables
  for i = 1 to n // chain length 1
    m[i, i] = 0
  for l = 2 to n // l is the chain length
    for i = 1 to n − l + 1 // chain begins at Ai
      j = i + l − 1 // chain ends at Aj
      m[i, j] = ∞
      for k = i to j − 1 // try Ai:kAk+1:j
        q = m[i, k] + m[k + 1, j] + pi−1pk pj
        if q < m[i, j]
        m[i, j] = q // remember this cost
        s[i, j] = k // remember this index
  return m and s

因此，有

\(\begin{aligned} \sum_{i=1}^n\sum_{j=i}^n R(i,j)&=\sum_{i'=1}^n\sum_{j'=i'}^n S(i',j')\\ &=\sum_{l=2}^n\sum_{i=1}^{n-l+1} 2\cdot((i+l-1)-1-i+1)\\ &=\sum_{l=2}^n\sum_{i=1}^{n-l+1} 2(l-1)\\ &=\sum_{l=2}^n(n-l+1)\cdot 2(l-1)\\ &=\dfrac{n^3-n}{3} \end{aligned}\)

14.2-6

考虑使用归纳法证明。

  • 当\(n=1\)时，不需要括号来对表达式进行括号化，原结论成立。

  • 当\(n=2\)时，仅需要一对括号才能将表达式\(A_1A_2\)完全括号化，得到\((A_1A_2)\)。

  • 当\(n>2\)时，假设对于\(k=1,2,\dots,n-1\)均成立。那么我们可以将元素表达式\(A_1,A_2,A_3,\dots,A_{n-1},A_n\)分成两个不为空的表达式：\(A_1A_2,\dots,A_k\)和\(A_{k+1},A_{k+2},\dots,A_n\)。那么按照假设，前一部分需要\(k-1\)个括号，后一部分需要\(n-k-1\)个括号。那么接下来再将这两部分元素进行括号化，仍然需要一个括号。因此最终需要\((k-1)+(n-k-1)+1=n-1\)个括号。

因此，原结论成立。