算法导论4.2 Exercises 答案

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

4.2-1

\(\begin{aligned} S_{1} &= B_{12} - B_{22}=[8]-[2]=[6]\\ S_{2} &= A_{11} + A_{12}=[1]+[3]=[4]\\ S_{3} &= A_{21} + A_{22}=[7]+[5]=[12]\\ S_{4} &= B_{21} - B_{11}=[4]-[6]=[-2]\\ S_{5} &= A_{11} + A_{22}=[1]+[5]=[6]\\ S_{6} &= B_{11} + B_{22}=[6]+[2]=[8]\\ S_{7} &= A_{12} - A_{22}=[3]-[5]=[-2]\\ S_{8} &= B_{21} + B_{22}=[4]+[2]=[6]\\ S_{9} &= A_{11} - A_{21}=[1]-[7]=[-6]\\ S_{10} &= B_{11} + B_{12}=[6]+[8]=[14]\\ \\ P_{1} &= A_{11} \cdot S_{1}=[1]\cdot [6]=[6] \\ P_{2} &= S_{2} \cdot B_{22}=[4]\cdot [2]=[8] \\ P_{3} &= S_{3} \cdot B_{11}=[12]\cdot [6]=[72] \\ P_{4} &= A_{22} \cdot S_{4}=[5]\cdot[-2]=[-10] \\ P_{5} &= S_{5} \cdot S_{6}=[6]\cdot [8]=[48] \\ P_{6} &= S_{7} \cdot S_{8}=[-2]\cdot [6]=[-12] \\ P_{7} &= S_{9} \cdot S_{10}=[-6]\cdot [14]=[-84]\\ \\ C_{11} &= P_{5} + P_{4} - P_{2} + P_{6}=[48]+[-10]-[8]+[-12]=[18]\\ C_{12} &= P_{1} + P_{2}=[6]+[8]=[14]\\ C_{21} &= P_{3} + P_{4}=[72]+[-10]=[62]\\ C_{22} &= P_{5} + P_{1} - P_{3} - P_{7}=[48]+[6]-[72]-[-84]=[66]\\ \end{aligned}\)

因此计算结果为\(\left[\begin{aligned} 18 && 14\\62&&66\end{aligned}\right]\)。

4.2-2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
Strassen(A, B, n)
  Let C be a new n × n matrix.
  if n == 1
  // Base case.
    c11 = a11 * b11
    return C
  // Divide.
  partition A, B, and C into n/2 × n/2 submatrices A11, A12, A21, A22; B11, B12, B21, B22; and C11, C12, C21, C22; respectively
  S1 = B12 − B22
  S2 = A11 + A12
  S3 = A21 + A22
  S4 = B21 − B11
  S5 = A11 + A22
  S6 = B11 + B22
  S7 = A12 − A22
  S8 = B21 + B22
  S9 = A11 − A21
  S10 = B11 + B12
  P1 = Strassen(A11, S1, n)
  P2 = Strassen(S2, B22, n)
  P3 = Strassen(S3, B11, n)
  P4 = Strassen(A22, S4, n)
  P5 = Strassen(S5, S6, n)
  P6 = Strassen(S7, S8, n)
  P7 = Strassen(S9, S10, n)
  // Conquer.
  C11 = P5 + P4 - P2 + P6
  C12 = P1 + P2
  C21 = P3 + P4
  C22 = P5 + P1 - P3 - P7
  return C

4.2-3

如果矩阵的大小\(n\)是\(3\)的幂，将它划分成\(3\times3\)部分计算，如果计算乘法的次数为\(k\)，那么运行时间有递推式：\(T(n)=k T(n/3)+\Theta(n^2)\)。

那么根据主定理的第一个条件，有\(T(n)=\Theta(n^{\log _3 k})\)。为了快于Strassen算法，需要满足\(\log_3k<\lg 7\)。可以计算得到：\(k=21\)。

4.2-4

通过计算，得到：

\(\begin{aligned} &\log_{68} 132464 \approx 2.7951285\\ &\log_{70} 143640 \approx 2.7951227\\ &\log_{72} 155424 \approx 2.7951474\\ \end{aligned}\)

可以发现，第二个效果最好。

4.2-5

程序输入MULTIPLY-COMPLEX输入四个数\(a,b,c,d\)分别表示复数\(a+bi,c+di\)。

输出两个数表示乘法计算结果的实部和虚部。

1
2
3
4
5
6
7
MULTIPLY-COMPLEX(a, b, c, d)
  A = (a + b) * (c + d)
  B = a * c
  C = b * d
  e = B - C
  f = A - B - C
  return (e, f)

其中有：

\(\begin{aligned} e &= B-C= ac-bd\\ f &= A-B-C=ac+ad+bc+bd-ac-bd=ad+bc \end{aligned}\)

4.2-6

假设这个程序MATRIX-SQUARE(A, n)可以以\(\Theta(n^{\alpha})\)的时间复杂度求矩阵的平方，那么可以用来设计程序MATRIX-MULTIPLY2(A, B, n)来以\(\Theta(n^{\alpha})\)来计算矩阵乘法。伪代码如下：

1
2
3
4
5
6
7
MATRIX-MULTIPLY2(A, B, n)
  C = A + B
  A2 = MATRIX-SQUARE(A, n)
  B2 = MATRIX-SQUARE(B, n)
  C2 = MATRIX-SQUARE(C, n)
  D = (C2 - A2 - B2) / 2
  return D

\(D=((A+B)^2-A^2-B^2)=(A^2+2AB+B^2-A^2-B^2)/2=AB\)

可以发现，这个程序仅仅执行了\(3\)次程序MATRIX-SQUARE，其余步骤都是执行固定次数的矩阵加法和标量乘法。因此执行的时间复杂度仍为\(\Theta(n^{\alpha})\)。