算法导论4.1 Exercises 答案

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

4.1-1

令\(n'=2^{\lceil\lg n\rceil}\)。那么不难发现，有\(\dfrac{1}{2}<\dfrac{n}{n'}\le 1\)成立。

为矩阵\(A,B\)补\(0\)到\(n'\)的大小，那么可以得到新矩阵\(A',B'\)。也就是说，对于矩阵\(A'\)中的新元素\(a_{ij}'\)，有：

\(a_{i,j}'= \left \{\begin{aligned} &a_{i,j} & & \text{if}\quad i\le n \land j\le n \\ &0 & & \text{if}\quad i> n \lor j> n \\ \end{aligned}\right.\)

矩阵\(B'\)同理。

递推式仍然为\(T'(n)=8T'(n/2)+\Theta(1)\)。

由于传统算法MATRIX-MULTIPLY-RECURSIVE的时间复杂度是\(T(n)=\Theta(n^3)\)，因此\(\exists c_1,c_2,n_0\in \mathbb{R}^{+},\forall n'\ge n_0,0\le c_1n'^3\le f(n')\le c_2n'^3\)。回代\(n\)，得到\(0\le \dfrac{c_1}{8}\cdot n^3\le f(n)\le c_2n^3\)。因此\(T'(n)=\Theta(n^3)\)。

4.1-2

使用这个程序作为子程序计算\(kn \times n\)和\(n\times kn\)大小的矩阵相乘需要花费\(\Theta(k^2n^3)\)的时间。如果是\(n \times kn\)和\(kn\times n\)大小的矩阵相乘，则需要花费\(\Theta(kn^3)\)的时间。

4.1-3

由于涉及到矩阵的复制操作，因此每次调用都会有\(\Theta(n^2)\)的操作时间。

因此运行时间的递推式就写成\(T(n)=8T(n/2)+\Theta(n^2)\)。

根据主定理，\(a=8,b=2,\log _b a=3\).

因此根据第一个条件，\(T(n)=\Theta(n^3)\)。

4.1-4

1
2
3
4
5
6
7
8
9
10
11
12
MATRIX-ADD-RECURSIVE(A, B, C, n)
  if n == 1
  // Base case.
    c11 = c11 + a11 + b11
    return
  // 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
   // Conquer.
  MATRIX-ADD-RECURSIVE(A11, B11, C11, n/2)
  MATRIX-ADD-RECURSIVE(A12, B12, C12, n/2)
  MATRIX-ADD-RECURSIVE(A21, B21, C21, n/2)
  MATRIX-ADD-RECURSIVE(A22, B22, C22, n/2)

如果使用的方法是直接基于索引的计算，那么运行时间的递推式就写成\(T(n)=4T(n/2)+\Theta(1)\)。

根据主定理，\(a=4,b=2,\log _b a=2\).

因此根据第一个条件，\(T(n)=\Theta(n^2)\)。

如果使用的方法是直接基于索引的计算，那么运行时间的递推式就写成\(T(n)=4T(n/2)+\Theta(n^2)\)。

因此根据第二个条件，得到\(k=0\)，最终\(T(n)=\Theta(n^{2}\lg ^1 n)=\Theta(n^2 \lg n)\)。